Quick Sort
Wählt ein Pivot, partitioniert in kleiner und größer, sortiert beide Seiten rekursiv.
- Vergleiche 0
- Tauschvorgänge 0
- Pivots gesetzt 0
- sortierte Indizes 0
- aktiver Bereich
- Pivot
- Vergleich
- Tausch
- sortiert
Pseudocode
1 quickSort(lo, hi)
2 if lo >= hi: return
3 pivot = a[hi]
4 i = lo - 1
5 for j from lo to hi - 1
6 if a[j] <= pivot
7 i = i + 1
8 swap a[i], a[j]
9 swap a[i + 1], a[hi]
10 p = i + 1
11 quickSort(lo, p - 1)
12 quickSort(p + 1, hi)
Schritt-Log
- 1Start.
Funktionsweise, Laufzeit und Speicher
Quick Sort wählt ein Pivot-Element (hier in der Lomuto-Variante das letzte Element der Range) und partitioniert das Array so, dass alle Werte links vom Pivot kleiner oder gleich dem Pivot sind und alle Werte rechts davon größer. Ein Zeiger i merkt sich die Grenze des "kleinen" Bereichs: ein zweiter Zeiger j läuft durch alle Elemente, und sobald a[j] <= pivot ist, wird a[j] nach vorne in den kleinen Bereich getauscht. Am Schluss wird das Pivot zwischen die beiden Teile geschoben. Damit steht das Pivot an seiner endgültigen Position, die beiden Teile werden rekursiv sortiert. Bei einer guten Pivot-Wahl halbiert sich die Range in jedem Schritt, was zu O(n log n) Laufzeit im Average und Best Case führt. Im Worst Case (z. B. bereits sortierte Eingabe und schlechtes Pivot) entartet die Rekursion zu einer Liste und die Laufzeit fällt auf O(n^2). Quick Sort arbeitet in-place, benötigt aber O(log n) Stack-Speicher für die Rekursion. Stabil ist der Algorithmus nicht, weil Tauschvorgänge über Distanz die Reihenfolge gleicher Werte verschieben können.
Komplexität
- Best Case
- O(n log n)
- Average Case
- O(n log n)
- Worst Case
- O(n2)
- Zusatz-Speicher
- O(log n)
Wann verwenden?
Default-Sortierer in den meisten Standardbibliotheken, oft als Introsort-Variante mit Heap-Sort als Sicherheitsnetz. In der Praxis schneller als Merge Sort, weil er in-place arbeitet und cachefreundlich auf den Speicher zugreift. Geeignet, wenn Speicher knapp ist und Stabilität nicht gebraucht wird.
Häufige Fragen
Was ist der Unterschied zwischen der Partition nach Lomuto und nach Hoare?
Lomuto nimmt das letzte Element als Pivot und schiebt mit einem einzigen Zeiger alle kleineren Werte nach vorn, danach steht das Pivot an seiner endgültigen Stelle. Hoare läuft mit zwei Zeigern von beiden Enden aufeinander zu und tauscht Paare, die auf der falschen Seite stehen. Hoare braucht im Mittel etwa ein Drittel der Tauschvorgänge, Lomuto ist leichter zu verstehen und wird hier gezeigt.
Warum ist Quick Sort im schlechtesten Fall quadratisch?
Ist das Pivot jedes Mal der kleinste oder größte Wert, etwa bei schon sortierter Eingabe und dem letzten Element als Pivot, teilt die Partition das Array in einen leeren und einen um eins kürzeren Teil. Die Rekursion wird dann n Ebenen tief, und die Vergleiche summieren sich zu O(n^2). Ein zufälliges Pivot oder der Median aus drei Werten machen diesen Fall sehr unwahrscheinlich.
Ist Quick Sort stabil?
Nein. Die Partition tauscht Elemente über weite Entfernungen, dabei können gleiche Werte ihre ursprüngliche Reihenfolge verlieren. Wer Stabilität braucht, nimmt Merge Sort oder Timsort.