Ein komplexeres Sortierverfahren
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 vielen Jahren mal geschrieben und im Juni 2019 noch einmal kurz überarbeitet habe.
Wenn ich mal Zeit und Lust habe, werde ich diese Seite zum Quicksort ausbauen und auch über Optimierungen des Quicksorts sprechen, im Augenblick schaffe ich das aber nicht.
Eine recht umfangreiche lehrbuchartige Darstellung des Quicksorts in mehreren Kapiteln: Überblick, Implementation, Analyse.
Hier ist vor allem der Pseudocode der Funktion teile(links,rechts) hoch interessant. Mit diesem Pseudocode kann man schön einen unsortierten Array in zwei Partitionen zerlegen.
Eine sehr schön gemachte Seite, auf der der QS anschaulich dargestellt wird.