Arbeitsblatt: Teile und Herrsche
Quicksort
Quicksort ist um einiges schneller als Sortieren durch Auswählen, besonders für große Mengen von Elementen. Es handelt sich sogar um eine der besten Methoden, die heute bekannt sind. Und so funktioniert es:
1. Wähle ein zufälliges Element aus und platziere es auf der einen Seite der Waage.
2. Danach vergleichst du alle anderen Elemente mit dem soeben Gewählten. Diejenigen, die leichter sind als das Element legst du links hin, die anderen rechts, und das Element selbst zum Schluss in die Mitte. (Beachte: Es kann vorkommen, dass sehr viel weniger Elemente auf einer Seite sind, als auf der anderen.)
3. Wiederhole die obigen zwei Anweisungen für die beiden Teile. Das Objekt, welches du zuvor in die Mitte gestellt hast, musst du jedoch nicht mehr wiegen. Es bleibt in der Mitte stehen.
4. Auf die entstehenden Untergruppen wenden wir wiederum die ersten zwei Anweisungen an, bis alle Elemente verarbeitet wurden und es demzufolge keine zwei Elemente zum Vergleichen gibt. Nun sind die Elemente aufsteigend angeordnet.
Wie oft hast du bei dieser Methode die Waage benutzt?
Du solltest festgestellt haben, dass Quicksort effizienter arbeitet als Sortieren durch Auswählen, außer du hast bei jedem Schritt immer das aktuell schwerste Element gewählt. Wenn du jedes Mal zufällig das mittlere Gewicht gewählt hast, hast du 14 Mal die Waage benutzt, was wesentlich besser ist, verglichen zu den 28 Vergleichen bei Sortieren durch Auswählen. Auf jeden Fall kann Quicksort nie schlechter sein als Sortieren durch Auswählen. Möglicherweise kann es aber viel besser sein!
Bubblesort: Diese Methode sortiert die Elemente, indem sie immer wieder durch die Liste durchgeht und alle benachbarten Elemente tauscht, die falsch herum da stehen. Die Liste ist sortiert, sobald es keine Vertauschungen benachbarter Elemente mehr gibt. Diese Methode ist nicht sonderlich schnell, es gibt jedoch Menschen, die diese Methode einfacher verstehen als die anderen Methoden.
Mergesort: Dies ist eine andere Methode, die das Prinzip ‚Teile und Herrsche‘ verwendet (wie Quicksort). Zuerst wird die Liste zufällig in zwei Teile der gleichen Größe aufgeteilt (oder fast der gleichen Größe, falls es eine ungerade Anzahl Elemente gibt). Die beiden Hälften werden sortiert und wieder zusammengefügt. Das Zusammenfügen zweier Listen ist einfach: Wir suchen wiederholt das leichteste Element und nehmen es aus der Menge raus, bis keine Elemente mehr übrig sind. In der Abbildung unten steht eine 40g Büchse und eine 60g Büchse zur Auswahl. Wir fügen als nächstes also die 40g Büchse ein. Wie aber erhalten wir zwei sortierte Teile? Einfach, wir wenden Mergesort auf die beiden Teile an! Irgendwann erhalten wir Teile, die nur eine Büchse enthalten. Eine solche Menge ist bereits sortiert.
