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

Etwas ausführlicher lässt sich das zugrunde liegende Prinzip des Algorithmus folgendermaßen skiz-
zieren:
1. Die zu sortierende Menge bestehe aus mehr als einem Körnerhaufen.
2. Dann wähle einen beliebigen Körnerhaufen - den sogenannten Pivot-Körnerhaufen .
3. Positioniere den Pivot-Körnerhaufen auf seine endgültige Kachel.
4. Sorge dabei dafür, dass alle Körnerhaufen links vom Pivot-Körnerhaufen kleiner oder gleich
diesem sind und
5. dass alle Körnerhaufen rechts vom Pivot-Körnerhaufen größer oder gleich diesem sind.
6. Rufe Quicksort rekursiv für den Teil links vom Pivot-Körnerhaufen auf.
7. Rufe Quicksort rekursiv für den Teil rechts vom dem Pivot-Körnerhaufen auf.
Eine einfache Strategie zur Implementierung der Partitionierung (Punkte 1 bis 5) ist folgende: Als
Pivot-Körnerhaufen wird willkürlich der rechte Körnerhaufen gewählt. Von links wird mit einem
Suchzeiger L nach einem Körnerhaufen gesucht, der größer als der Pivot-Körnerhaufen ist. Von
rechts wird mit einem Suchzeiger R nach einem Körnerhaufen gesucht, der kleiner als der Pivot-
Körnerhaufen ist. Diese beiden Körnerhaufen sind offensichtlich jeweils im falschen Teil und wer-
den daher getauscht. Mit dieser Suche und dem Austausch wird fortgefahren, bis sich die Suchzeiger
treffen bzw. kreuzen. Dann ist sicher gestellt, dass alle Körnerhaufen links vom Suchzeiger L klei-
ner oder gleich und alle Körnerhaufen rechts vom vom Suchzeiger R größer oder gleich dem Pivot-
Körnerhaufen sind. Als Kachel für den Pivot-Körnerhaufen wählt man abschließend die Kachel, auf
die der Suchzeiger L zeigt, und tauscht den entsprechenden Körnerhaufen (der ja größer oder gleich
dem Pivot-Körnerhaufen ist) mit dem Pivot-Körnerhaufen ganz rechts.
Vergleichen Sie diese Aufgabe auch mit den Aufgaben 11, 12 und 13 aus Kapitel 16.
17.9.9 Aufgabe 9
Die Ausgangssituation in dieser Aufgabe ist dieselbe wie in Aufgabe 8: Es soll eine Körnerrei-
he sortiert werden. Nur diesmal soll zum Sortieren nicht der Quicksort-, sondern der sogenannte
Mergesort-Algorithmus eingesetzt werden.
Die grundlegende Idee des MergeSort-Algorithmus ist die, dass die zu sortierenden Körnerhaufen
in zwei Teile zerlegt werden und diese durch rekursive Anwendung des Algorithmus sortiert und
anschließend gemischt werden. Die Rekursion endet, wenn ein Teil nur noch aus einem einzelnen
Körnerhaufen besteht. In diesem Fall ist er ja sortiert.
Mischen zweier sortierter Teile bedeutet, dass diese zu einem sortierten Teil verschmolzen werden.
Dazu werden die Teile zunächst in eine Hilfs-Zeile kopiert, d.h. das Territorium besteht hier nicht
aus einer, sondern aus zwei Zeilen. Anschließend werden die beiden kopierten Teile elementweise
durchlaufen. Der jeweils kleinere Körnerhaufen wird zurückkopiert. Zum Schluss muss dann noch
der Rest eines der beiden Teile zurückkopiert werden.
17.9.10 Aufgabe 10
Bei dem Spiel „Türme von Hanoi“ handelt es sich um ein mathematisches Knobel- und Geduldspiel.
Mal schauen, ob Sie bzw. der Hamster genügend Geduld und Sachverstand besitzen.