ℹ️ Quick Sort – Explanation
Idea (Lomuto Partition)— Quick Sort picks an element as the pivot (here: the last element). All elements ≤ pivot move to the left, all > pivot to the right. The pivot then lands at its final position. The left and right sub-ranges are then sorted recursively.
Complexity — Average O(n log n), worst case (already-sorted array with last element as pivot) O(n²). Very fast in practice due to good cache locality.
Properties
- Stable: No – swaps can reorder equal elements.
- In-place: Yes – O(log n) stack memory, no auxiliary array.
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