ℹ️ Quick Sort – Erklärung
Idee (Lomuto-Partition) — Quick Sort wählt ein Element als Pivot(hier: letztes Element). Alle Elemente ≤ Pivot wandern nach links, alle > Pivot nach rechts. Das Pivot landet anschließend an seiner finalen Position. Dann werden linke und rechte Teilbereiche rekursiv sortiert.
Komplexität — Durchschnitt O(n log n), Worst-Case (bereits sortiertes Array mit letztem Element als Pivot) O(n²). Praktisch sehr schnell wegen guter Cache-Lokalität.
Eigenschaften
- Stabil: Nein – Tausche können gleiche Elemente umordnen.
- In-place: Ja – O(log n) Stack-Speicher, kein Hilfsarray.
1 / 33
Eingabe-ArrayKlick = bearbeiten · Rechtsklick = löschen
10
80
30
90
40
50
70
+
Start: Array mit 7 Elementen. Quick Sort wählt ein Pivot-Element und partitioniert: alle kleineren Elemente links, alle größeren rechts.
⇄ In-Place Array—Ein Array, alle Tausche finden direkt darin statt
10
.
80
.
30
.
90
.
40
.
50
.
70
.
★ Partition-Baum (Divide & Conquer)—Jede Zeile = eine Rekursionstiefe · Lücken = bereits platzierte Pivots
10
80
30
90
40
50
70
10
30
40
50
90
80
10
30
40
90
10
30
10
★ Pivot (aktiv)≤ Pivot> PivotScan-ZeigerPivot platziertFertig sortiert