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

16.6.11 Aufgabe 11

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 16.12 (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 16.12 (rechts)).

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

Abbildung 16.12: Typische Hamster-Landschaft zu den Aufgaben 11, 12 und 13

Zum Sortieren verwendet werden soll der sogenannte Bubblesort-Algorithmus . Dieser funktioniert
auf folgende Art und Weise: Die Kacheln der Zeile werden von rechts nach links durchlaufen. Dabei
werden jeweils benachbarte Kacheln miteinander verglichen. Ist die Anzahl an Körnern auf der
rechten Kachel kleiner als die Anzahl an Körnern auf der linken Kachel, werden die entsprechenden
Körnerhaufen getauscht. Diese Durchläufe durch die Zeile von rechts nach links werden solange
wiederholt, bis in einem Durchlauf keine Vertauschung stattgefunden hat. Dann ist die Zeile sortiert.
Durch die fortlaufenden Vertauschungen wird im ersten Durchlauf der kleinste Körnerhaufen ganz
nach links transportiert. Im zweiten Durchlauf wird der zweitkleinste Körnerhaufen an seine korrekte
Position gebracht, usw.

16.6.12 Aufgabe 12

Die Ausgangssituation in dieser Aufgabe ist dieselbe wie in Aufgabe 11: Es soll eine Körnerrei-
he sortiert werden. Nur diesmal soll zum Sortieren nicht der Bubblesort-, sondern der sogenannte
Selectionsort-Algorithmus eingesetzt werden. Dieser funktioniert folgendermaßen:

• Suche den kleinsten Körnerhaufen. Tausche ihn gegen den Körnerhaufen in der ersten Spalte.
• Suche den zweitkleinsten Körnerhaufen. Tausche ihn gegen den Körnerhaufen in der zweiten
Spalte.
• Suche den drittkleinsten Körnerhaufen. Tausche ihn gegen den Körnerhaufen in der dritten
Spalte.
• ...
• Suche den (n-1)kleinsten Körnerhaufen. Tausche ihn gegen den Körnerhaufen in der (n-1)sten
Spalte. n ist dabei die Anzahl an Kacheln der Zeile.
Die Zeile des Territorium besteht also aus einem sortierten linken Teil, der in jedem Schritt um
eine Kachel wächst, und einem unsortierten rechten Teil, der entsprechend schrumpft. D.h. bei der
Suche nach dem x -kleinsten Körnerhaufen muss nur noch der unsortierte rechte Teil der Zeile ab
der x -ten Kachel durchsucht werden, da die linken x -1 Kacheln bereits sortiert sind. Genauer gesagt,
muss in jedem Schritt jeweils der kleinste Körnerhaufen des unsortierten Teils gesucht und mit dem
Körnerhaufen der ersten Kachel des unsortierten Teils vertauscht werden.