Overview
Pivot wählen, Array partitionieren, rekursiv sortieren – im Durchschnitt O(n log n).
Analogy
Bücher sortieren: wähle eine Leitkarte, lege alle kleineren links und größeren rechts davon ab.
Step-by-step
- Wähle Pivot (z.B. letztes Element).
- Partition: Zeiger i startet vor Array, j durchläuft Array; wenn arr[j]<=pivot: i++, tausche arr[i] und arr[j].
- Tausche Pivot an Position i+1.
- Rekursiv auf linke (0..i) und rechte (i+2..n-1) Teilarrays anwenden.
Visual
[3,6,8,10,1,2,1] Pivot=1: Partition→[1,1,8,10,3,2,6]→rekursiv→sortiert
Common mistakes
- Immer letztes/erstes Element als Pivot: bei sortiertem Input O(n²) – Median-of-Three verwenden.
- 3-Wege-Partition vergessen bei vielen Duplikaten.
Practice questions
- Quick-Sort mit Median-of-Three Pivot-Wahl implementieren.
- 3-Wege-Partition (Dutch National Flag) für Arrays mit vielen Duplikaten implementieren.
Time
O(n log n) Durchschnitt, O(n²) worst-case