Quicksort.

Quicksort sortiert ein Array, indem es ein Pivot-Element wählt und alle Werte ≤ Pivot nach links, Werte > Pivot nach rechts partitioniert. Dann werden beide Teile rekursiv sortiert. In vielen In-Memory-Szenarien einer der schnellsten Klassiker (abhängig von Pivotstrategie, Implementierung und Speicherlayout), kann aber bei ungünstiger Pivot-Wahl auf O(n²) degenerieren. Du lernst hier die drei Schritte (Pivot, Partition, Rekursion), die zwei Partitions-Schemata Lomuto (<= vs >) und Hoare (zwei Pointer von außen), warum In-Place mit O(log n) Average / O(n) Worst-Case Speicher (Rekursionsstack), warum Quicksort nicht stabil ist (Standard-In-Place-Varianten), warum Random-Pivot oder Median-of-Three den Worst Case bei sortierten Eingaben vermeiden, und konkrete Praxisbeispiele (Java Dual-Pivot Quicksort für primitive Arrays, C++ std::sort mit Introsort = Quicksort + Heapsort-Fallback).

Was du in der Klausur können musst:

• Idee in 3 Schritten: Pivot wählen, Partitionieren (≤ Pivot links, > Pivot rechts), beide Teile rekursiv quicksorten
• Komplexität: O(n log n) im Average-Case, O(n²) im Worst-Case (z.B. sortierte Eingabe mit Pivot = letztes Element)
• In-Place bezüglich Array: ja, aber Rekursionsstack braucht O(log n) im Average/Best Case und O(n) im Worst Case beim gezeigten Lomuto-Schema
• Stabil: nein, gleiche Werte können ihre Reihenfolge ändern

In Klausuren ist die häufigste Falle: gegeben eine sortierte Eingabe, zeige dass Quicksort O(n²) hat wenn das Pivot immer das letzte Element ist. Lösung in der Praxis: Median-of-Three oder zufälliges Pivot.

Die Idee in 3 Schritten

1. Pivot wählen (z.B. das letzte Element)
2. Partitionieren: alle Werte ≤ Pivot nach links, alle Werte > Pivot nach rechts (Lomuto-Konvention; gleiche Werte landen also im linken Bereich ≤ Pivot-Wert, der Pivot selbst landet danach an der finalen Position zwischen beiden Bereichen). Achtung bei vielen Duplikaten: mit naivem Lomuto landen alle gleichen Werte links und Partitionen werden stark unbalanciert. Hier ist 3-Wege-Partitionierung (< Pivot, = Pivot, > Pivot in drei Bereichen) deutlich effizienter (Dutch National Flag, in der Praxis von vielen modernen Quicksort-Implementierungen verwendet).
3. Rekursion: Quicksort auf die linke und rechte Hälfte

Anders als Mergesort wird nicht blind in der Mitte geteilt, sondern um den Pivot herum. Wenn der Pivot ungefähr in der Mitte landet, ergibt sich die schöne logarithmische Tiefe.

Visualisierung der Partition

[5, 2, 8, 1, 9, 3, 7, 4]   Pivot = 4 (letztes Element)
            ↓ partitionieren (Lomuto, ≤ pivot links)
[2, 1, 3, | 4 | 5, 8, 9, 7]
       ↑      ↑
       ≤4     >4

Dann Quicksort rekursiv auf [2,1,3] und [5,8,9,7].

Implementierung

public static void quickSort(int[] arr, int lo, int hi) {
    if (hi - lo <= 1) return;
    int pivot = arr[hi - 1];
    int i = lo;
    for (int j = lo; j < hi - 1; j++) {
        if (arr[j] <= pivot) {
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            i++;
        }
    }
    int tmp = arr[i]; arr[i] = arr[hi - 1]; arr[hi - 1] = tmp;
    quickSort(arr, lo, i);
    quickSort(arr, i + 1, hi);
}

def quick_sort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr)
    if hi - lo <= 1:
        return
    pivot = arr[hi - 1]
    i = lo
    for j in range(lo, hi - 1):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi - 1] = arr[hi - 1], arr[i]
    quick_sort(arr, lo, i)
    quick_sort(arr, i + 1, hi)

Komplexität: zwei Gesichter

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, und der Rekursionsstack wird O(n) tief. Genau gerechnet: (n-1) + (n-2) + dots + 1 = n(n-1)/2 Vergleiche, also ≈ n²/2.

Lösung: Randomisierte Pivot-Wahl liefert erwartete Laufzeit O(n log n), der Worst Case bleibt theoretisch möglich, ist in der Praxis aber sehr unwahrscheinlich. Median-of-Three (Median aus erstem, mittlerem und letztem Element) reduziert typische schlechte Muster wie sortierten Input, garantiert aber allein keinen O(n log n)-Worst-Case.

Eigenschaften

• ✅ In-Place bezüglich Array. Rekursionsstack: O(log n) im Average/Best Case, O(n) im Worst Case beim Lomuto-Schema. Mit Tail-Call-Optimierung und "rekursiv zuerst auf die kleinere Partition" lässt sich der Stack auf O(log n) begrenzen.
• ✅ In der Praxis schnell: oft schneller als Mergesort, vor allem wegen guter Cache-Lokalität. Der konkrete Faktor hängt von Implementierung, Daten und Hardware ab.
• ❌ 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. Einige Standardbibliotheken nutzen Quicksort-Varianten oder hybride Verfahren, nicht "die meisten Sprachen", aber prominente Beispiele:

Praxis-Hinweis (nicht durch ALGORITHMS-Trusted-Sources gedeckt, aber gut zu wissen):

• Java: Arrays.sort(int[]) und andere primitive Arrays nutzen Dual-Pivot Quicksort. Arrays.sort(Object[]) nutzt dagegen ein stabiles, adaptives Mergesort/Timsort-artiges Verfahren. Quelle: OpenJDK-Doku.
• C++: std::sort ist kein naiver Quicksort, sondern typischerweise Introsort (Quicksort + Fallback auf Heapsort bei drohendem n²-Verhalten). Dadurch wird O(n log n) im Worst Case garantiert. Quelle: ISO-C++-Standard-Komplexitätsanforderung an std::sort.

Im Sortier-Vergleich-Topic kannst du selbst sehen wie Quicksort bei sortiertem Input ins quadratische Verhalten abrutscht.

Quicksort live (mit Worst-Case-Demo)

Beobachte wie Quicksort um den Pivot herum partitioniert. Der Pivot ist immer das letzte Element des aktuellen Bereichs (Lomuto-Schema).

Achte auf den großen Aha-Moment:

1. Stell ein Array mit zufälliger Eingabe ein → ~n·log₂(n) Vergleiche, schön schnell
2. Schalt um auf Sortiert → Quicksort braucht plötzlich fast n²/2 Vergleiche, fast wie Bubblesort!

Bei sortiertem Input ist der letzte Wert immer das Maximum. Die Partition liefert 0 Elemente links und n−1 rechts: maximale Unbalance.

Faustregel zum Mitnehmen: Quicksort hat zwei Gesichter. In der Praxis nutzt man randomisierte Pivots oder Median-of-Three, damit der Worst Case quasi nie eintritt. Aber wissen muss man, dass er existiert.

---

Code-Stepper: Lomuto-Partition Zeile für Zeile

Die Partition ist das Herzstück von Quicksort und in Klausuren der häufigste Stolperfall. Wir zeigen einen kompletten Partition-Lauf auf [4, 2, 5, 1, 3] mit Pivot 3 (letztes Element, Lomuto-Schema). Achte auf die Invariante: alles links von i+1 ist <= pivot, alles zwischen i+1 und j-1 ist > pivot.