Rekursion - Programmieren Spielend Gelernt mit dem Java-Hamster-Modell - page 342

Abbildung 17.10: Solitärspiel

dieser Kachel muss ebenfalls noch ein Korn enthalten. Dahinter muss sich jedoch eine körnerlose
Kachel (Kachel 3) befinden. Existiert eine solche Konfiguration (im Allgemeinen existieren mehrere
Alternativen, von denen sich der Hamster eine aussuchen kann), dann muss der Hamster das Korn
von Kachel 1 nach Kachel 3 transportieren und darf das Korn von Kachel 2 fressen. Gerät der
Hamster irgendwann in eine Situation, in der sich noch mehr als ein Korn im Territorium befindet,
in der er gemäß den vorgegebenen Regeln jedoch kein Korn mehr fressen kann, dann hat er sich
irgendwann für die falsche Alternative entschieden.

17.9.8 Aufgabe 8

Der Hamster steht mit Blickrichtung Ost ganz links in einem Territorium mit beliebig vielen Spalten
aber nur einer Zeile. Auf den einzelnen Kacheln dieser Zeile können beliebig große Körnerhaufen
liegen (siehe bspw. Abbildung 17.11 (links)). Der Hamster bekommt die Aufgabe, die Körnerhaufen
der Größe nach zu sortieren, d.h. zum Schluss soll auf der Kachel der ersten Spalte der kleinste
Körnerhaufen liegen und für jede weitere Spalte soll gelten, dass die Anzahl an Körnern auf der
jeweiligen Kachel größer oder gleich der Anzahl an Körnern auf der Kachel der vorherigen Spalte
ist (siehe Abbildung 17.11 (rechts)).

4 3 5 2 6 4 2 3 4 4 5 6

Abbildung 17.11: Typische Hamster-Landschaft zu Aufgabe 8

Zum Sortieren verwendet werden soll der sogenannte Quicksort-Algorithmus . Dieser funktioniert
auf folgende Art und Weise:
Quicksort zerlegt (man spricht auch von Partitionierung ) die zu sortierenden Körnerhaufen in zwei
Teile, die durch einen Referenz-Haufen - auch Pivot-Körnerhaufen genannt - getrennt werden. Alle
Körnerhaufen des linken Teils sind dabei kleiner oder gleich und alle Körnerhaufen des rechten Teils
größer oder gleich dem Pivot-Körnerhaufen. Das bedeutet gleichzeitig, dass der Pivot-Körnerhaufen
an seinem korrekten Platz steht. Anschließend wird Quicksort rekursiv für die beiden Teile aufgeru-
fen. Die Rekursion endet, wenn ein Teil nur noch aus einem Körnerhaufen besteht.