Komplexität: zwei Gesichter
| Fall | Komplexität | Wann? |
|---|
| Best Case | O(n log n) | Pivot landet immer in der Mitte |
| Average Case | O(n log n) | Zufällige Eingabe |
| Worst Case | O(n²) | Pivot ist immer das Min/Max |
Worst Case in der Praxis: sortierter oder umgekehrt sortierter Input mit naiver Pivot-Wahl (immer letztes Element). Dann partitioniert Lomuto in 0 + (n-1) statt in zwei Hälften.
Lösung: Randomisierte Pivot-Wahl oder Median-of-Three (nimm den Median aus erstem, mittlerem und letztem Element). Damit wird der Worst Case fast unmöglich.
Eigenschaften
- ✅ In-Place: braucht nur O(log n) Stack-Platz für die Rekursion
- ✅ Schnell in der Praxis: oft 2-3× schneller als Mergesort wegen guter Cache-Lokalität
- ❌ Nicht stabil: Partitionierung kann gleiche Werte vertauschen
- ❌ Worst Case O(n²): wenn nicht abgesichert
Wann sinnvoll?
In der Praxis sehr verbreitet: wenn Stabilität nicht wichtig ist. Die meisten Programmiersprachen nutzen eine Quicksort-Variante für primitive Datentypen:
- Java:
Arrays.sort(int[]) nutzt Dual-Pivot Quicksort
- C++:
std::sort nutzt Introsort (Quicksort + fällt bei drohendem n²-Verhalten auf Heapsort zurück)
Im Sortier-Vergleich-Topic kannst du selbst sehen wie Quicksort bei sortiertem Input ins quadratische Verhalten abrutscht.
