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
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(n^2) - 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.