Mergesort
Der Mergesort ist eigentlich ein recht einfaches Sortierverfahren, das deutlich schneller ist als die drei Sortierverfahren, die wir in der Stufe EF kennengelernt haben.
- Der Array wird zunächst in zwei möglichst gleich große Hälften aufgeteilt. Jede Hälfte wird dann sortiert. Anschließend werden die beiden Hälften wiedervereinigt, so dass der ganze Array sortiert ist.
Aber wie wird jede dieser Hälften sortiert? Ganz einfach: - Jede Hälfte wird zunächst in zwei möglichst gleich große Hälften aufgeteilt, im Grunde also in Viertel. Jedes Viertel wird dann sortiert. Anschließend werden die beiden Viertel einer Hälfte wiedervereinigt, so dass die ganze Hälfte sortiert ist.
Aber wie wird jedes Viertel sortiert? Ganz einfach: - Jedes Viertel wird zunächst in zwei möglichst gleich große Hälften aufgeteilt, also in Achtel. Jedes Achtel wird dann sortiert. Anschließend werden die beiden Achtel wiedervereinigt, so dass das ganze Viertel sortiert ist.
Ich hoffe, Sie haben die Rekursion erkannt, die in dem Mergesort steckt.
- Wenn nun alle Hälften der Hälften der Hälften... sortiert sind, müssen die Hälften wieder zusammengebaut werden, bis am Ende der gesamte Array in recht schneller Zeit sortiert ist.
Weitere Einzelheiten zum Mergesort erfahren Sie auf der Seite "Mergesort".
Quicksort
Der Quicksort ist ein komplexeres Sortierverfahren, das in seiner Geschwindigkeit aber Maßstäbe setzt. Im Prinzip handelt es sich um ein rekursives binäres Verfahren. Die Zahl in der Mitte des Arrays - der sogenannte Median - wird als "sortiert" betrachtet, und dann werden alle Zahlen links dieses Medians, die größer sind als der Median, nach rechts "geschaufelt". Alle Zahl rechts des Medians, die kleiner sind als dieser, werden dagegen nach links "geschaufelt". Am Ende des ersten Durchgangs sind alle Zahlen links des Medians kleiner als dieser, und alle Zahlen rechts des Medians sind größer als dieser. Danach wird der linke Abschnitt in zwei neue Hälften unterteilt, ebenso der rechte, ähnlich wie beim Mergesort. Dann wiederholt sich das Ganze rekursiv.
Weitere Einzelheiten zum Quicksort finden Sie in dem Quicksort-Abschnitt des alten PDF-Skriptes, dass ich vor einigen Jahren mal geschrieben und im Juni 2019 noch einmal kurz überarbeitet habe.