Quicksort

Quicksort ist einer der meistgenutzten Sortieralgorithmen. Er wählt ein Pivotelement, teilt die Liste in die Werte, die kleiner als das Pivotelement sind, und den Rest, und sortiert beide Seiten genauso. Er ist in der Praxis schnell und braucht keine zusätzliche Liste, aber wie schnell, hängt vom Pivotelement ab.

Balken, um einen Pivot-Balken partitioniert: kleinere Balken auf der einen Seite, größere auf der anderen, das Pivotelement dazwischen
Balken, um einen Pivot-Balken partitioniert: kleinere Balken auf der einen Seite, größere auf der anderen, das Pivotelement dazwischen

Die Idee

Wählen Sie einen Wert als Pivotelement. Ordnen Sie die Liste so um, dass jeder Wert, der kleiner als das Pivotelement ist, davor steht und jeder andere dahinter. Dieses Umordnen heißt Partitionierung, und danach steht das Pivotelement genau dort, wo es in der sortierten Liste hingehört. Die beiden Seiten sind nun unabhängige Probleme: Sortieren Sie jede mit Quicksort. Eine Seite mit einem oder keinem Wert ist bereits sortiert.

Die Partitionierung, Schritt für Schritt

Die App verwendet die Lomuto-Partitionierung. Das Pivotelement wird ans Ende des Teils verschoben. Eine Markierung beginnt am Anfang: Alles davor ist kleiner als das Pivotelement. Jeder andere Wert wird mit dem Pivotelement verglichen; ist er kleiner, wird er zur Markierung getauscht, und die Markierung rückt einen Platz weiter. Am Ende wird das Pivotelement zur Markierung getauscht. Nehmen Sie 5, 1, 4, 2, 8 mit dem letzten Wert als Pivotelement: Alle vier Werte sind kleiner als 8, also bleibt 8 am Ende. Der Teil 5, 1, 4, 2 wird um 2 partitioniert, was 1, 2, 4, 5 ergibt, und 4, 5 um 5. Das sind 8 Vergleiche, 2 Vertauschungen und 3 Partitionierungen.

Gute und schlechte Pivotelemente

Würde jedes Pivotelement in der Mitte landen, halbierte jede Partitionierung das Problem, und die Sortierung bräuchte etwa n log₂ n Vergleiche. Bei einer zufälligen Liste sind die Pivotelemente selten perfekt, aber meist gut genug: Bei 40 zufälligen Werten zählt die App etwa 190 Vergleiche. Der schlimmste Fall tritt ein, wenn das Pivotelement immer der kleinste oder größte Wert ist. Mit dem letzten Wert als Pivotelement passiert genau das bei einer Liste, die schon sortiert oder umgekehrt ist: Jede Partitionierung entfernt nur das Pivotelement, und die Sortierung braucht n(n − 1)/2 Vergleiche, 780 bei 40 Werten.

Das Pivotelement wählen

Ein zufälliges Pivotelement macht den schlimmsten Fall bei jeder Eingabe äußerst unwahrscheinlich, weil keine bestimmte Reihenfolge es austricksen kann. Der Median aus drei, der mittlere Wert aus erstem, mittlerem und letztem Element, ist billig und kommt mit sortierten und umgekehrten Listen gut zurecht. Probieren Sie beides in der App an einer sortierten Liste aus: Die Vergleiche sinken von 780 auf etwa 150. Viele gleiche Werte sind ein anderes Problem: Sie landen alle auf derselben Seite des Pivotelements. Eine Drei-Wege-Partitionierung, die die Werte gleich dem Pivotelement in einem mittleren Teil sammelt, behebt das.

Geschichte und Einsatz

Tony Hoare erfand Quicksort 1959 und veröffentlichte ihn 1961. Seine eigene Partitionierung sucht von beiden Enden aus und braucht weniger Vertauschungen; die einfachere Lomuto-Variante, die hier gezeigt wird, wurde durch Lehrbücher bekannt. Quicksort sortiert in-place, und seine innere Schleife ist sehr kurz, daher ist er in der Praxis meist schneller als Mergesort, allerdings nicht stabil. Introsort, das Sortierverfahren der C++-Standardbibliothek, führt Quicksort aus und wechselt zu Heapsort, wenn die Partitionierungen zu ungleich werden, sodass sein schlimmster Fall bei n log n bleibt.

Tony Hoare, der Quicksort 1959 erfand und 1961 veröffentlichte.
Tony Hoare, der Quicksort 1959 erfand und 1961 veröffentlichte.

Selbst ausprobieren

Öffnen Sie die App und drücken Sie „Schritt“. Der Teil, der partitioniert wird, ist schattiert, das Pivotelement hat eine eigene Farbe, und die gestrichelte Linie markiert das Ende des linken Teils, also der Werte, die kleiner als das Pivotelement sind. Jedes Pivotelement wird grün, sobald es seinen endgültigen Platz erreicht. Wählen Sie eine sortierte Liste und den letzten Wert als Pivotelement, wechseln Sie dann zum Median aus drei und vergleichen Sie die Zähler.

Häufig gestellte Fragen

Welche Zeitkomplexität hat Quicksort?

O(n log n) im Mittel und mit guten Pivotelementen, O(n²) im schlimmsten Fall. Er sortiert in-place; die Rekursion braucht O(log n) zusätzlichen Speicher, wenn die kleinere Seite zuerst sortiert wird.

Was ist der Unterschied zwischen der Lomuto- und der Hoare-Partitionierung?

Lomuto nutzt eine Markierung und läuft von links nach rechts; das ist leicht nachzuvollziehen und wird in dieser App gezeigt. Hoare läuft von beiden Enden aufeinander zu und tauscht Paare, die auf der falschen Seite stehen; das braucht im Mittel etwa dreimal weniger Vertauschungen.

Warum ist Quicksort langsam, wenn viele Werte gleich sind?

Werte gleich dem Pivotelement landen alle auf derselben Seite, daher wird eine Liste mit wenigen verschiedenen Werten ungleich geteilt, und eine Liste gleicher Werte ist so schlecht wie der schlimmste Fall. Eine Drei-Wege-Partitionierung, die die Werte gleich dem Pivotelement in der Mitte sammelt, verhindert das.

Ist Quicksort stabil?

Nein. Vertauschungen während einer Partitionierung verschieben Werte über große Entfernungen, daher können gleiche Werte ihre Reihenfolge ändern.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Quicksort ausprobieren