Schnellsortierung · Komplexitätsnotizen
Quelle: Schnellsortierung · Algorithmen
Algorithmusidee
Algorithmen- Pivot wählen -> partitionieren -> beide Hälften rekursiv sortieren
- In-place, nicht stabil
Komplexität
Algorithmen| Fall | Zeit | Speicher |
|---|---|---|
| Best | Θ(n log n) | O(log n) |
| Average | Θ(n log n) | O(log n) |
| Worst | Θ(n²) | O(n) |
Rekurrenz
Algorithmen- T(n) = 2·T(n/2) + Θ(n) ⇒ Θ(n log n)
Interviewkarten
Algorithmen- Q: Warum zufälliger Pivot? A: um Θ(n²) bei gegnerischen oder sortierten Eingaben zu vermeiden.



