Funktionsparameter - Programmieren Spielend Gelernt mit dem Java-Hamster-Modell - page 315

16.6.13 Aufgabe 13

Und nochmal wird der Hamster zum Sortieren aufgefordert. Die Ausgangssituation ist wiederum
dieselbe wie in Aufgabe 11. Der Sortieralgorithmus, der in dieser Aufgabe verwendet werden soll,
nennt sich Insertionsort . Er funktioniert folgendermaßen:
Der Hamster nimmt sich alle Kacheln von links nach rechts vor. Für jede Kachel i muss er dabei
folgendes tun:
• Friss den Körnerhaufen der Kachel in Spalte i und merke dir die Anzahl.
• Suche links von Spalte i die sogenannten Einfügekachel des Körnerhaufens. Die Suche startet
dabei bei Spalte i -1 ( Suchindex ) und läuft von rechts nach links. Es wird jeweils verglichen,
ob der Körnerhaufen am Suchindex kleiner oder gleich dem gefressenen und gemerkten Kör-
nerhaufen der Spalte i ist. Ist das nicht der Fall, wird der Körnerhaufen des Suchindex um eine
Kachel nach rechts verschoben. Wird ein solcher Körnerhaufen bei Spalte j gefunden, ist die
Kachel in Spalte j +1 die Einfügekachel. Wird überhaupt kein entsprechender Körnerhaufen
gefunden, ist die erste Spalte die Einfügekachel.
• Lege den gefressenen und gemerkten Körnerhaufen der Spalte i auf der Einfügekachel wieder
ab.

Die Zeile des Territoriums besteht also aus einem sortierten linken Teil, der in jedem Durchlauf um
eine Kachel wächst, und einem unsortierten rechten Teil, der entsprechend schrumpft. Betrachtet
wird in jedem Durchlauf die erste Kachel des unsortierten Teils, deren Körnerhaufen in den bereits
sortierten Teil einsortiert wird.

16.6.14 Aufgabe 14

Der Hamster steht mit Blickrichtung Ost in der linken oberen Ecke eines beliebig großen rechtecki-
gen Territoriums ohne innere Mauern. Auf den einzelnen Kacheln des Territoriums liegen beliebig
viele Körner (siehe bspw. Abbildung 16.13 (links)).

4 3 5 1 2 3

1 3 7 2 3 4 5 5

6 8 7 5 6 7 7 8

Abbildung 16.13: Typische Hamster-Landschaft zu Aufgabe 14

Der Hamster soll die Körnerhaufen so sortieren, dass ihre Größe von links nach rechts und von oben
nach unten wächst (siehe Abbildung 16.13 (rechts)). Welchen Sortieralgorithmus Sie zum Lösen
dieser Aufgabe benutzen, ist Ihnen überlassen.

16.6.15 Aufgabe 15

Der Hamster steht mit Blickrichtung Ost in der linken oberen Ecke eines innen mauerlosen Terri-
toriums mit beliebig vielen Spalten aber nur zwei Zeilen. Auf den einzelnen Kacheln befinden sich