UniProMax/Algorithmen/quicksort

Quicksort

Der schnellste der Klassiker im Average Case: O(n log n), in-place, partitioniert um einen Pivot. Bei sortiertem Input rutscht er aber auf O(n²) ab.

3LerneinheitenVoraussetzungen:Mergesort

Relevant für:Informatik(Klausurniveau)Wirtschaftsinformatik(Grundlagen)Data Science(Grundlagen)

Sprache wählen

Sprache

Lerneinheit 1 von 3java + python

Quicksort

Der zwiespältige Sortieralgorithmus. Im Average Case der schnellste der drei Klassiker, im Worst Case kann er aber zu O(n²) degenerieren.

Die Idee in 3 Schritten

Pivot wählen (z.B. das letzte Element)
Partitionieren: alle Werte kleiner als Pivot nach links, alle größeren nach rechts
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
[2, 1, 3, | 4 | 5, 8, 9, 7]
       ↑      ↑
       <4     ≥4

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

Implementierung

java// snippet

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);
}

Java: Lomuto-Partitionsschema. Pivot ist das letzte Element, i markiert die Grenze zwischen kleineren und größeren Werten.

Komplexität: zwei Gesichter

Fall	Komplexität	Wann?
Best Case	$O(n \log n)$	Pivot landet immer in der Mitte
Average Case	$O(n \log n)$	Zufällige Eingabe
Worst Case	$O(n^2)$	Pivot ist immer das Min/Max

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.

Lösung: Randomisierte Pivot-Wahl oder Median-of-Three (nimm den Median aus erstem, mittlerem und letztem Element). Damit wird der Worst Case fast unmöglich.

Eigenschaften

✅ In-Place: braucht nur O(log n) Stack-Platz für die Rekursion
✅ Schnell in der Praxis: oft 2-3× schneller als Mergesort wegen guter Cache-Lokalität
❌ 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. Die meisten Programmiersprachen nutzen eine Quicksort-Variante für primitive Datentypen:

Java: Arrays.sort(int[]) nutzt Dual-Pivot Quicksort
C++: std::sort nutzt Introsort (Quicksort + fällt bei drohendem n²-Verhalten auf Heapsort zurück)

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

VorkenntnisMergesort Baut darauf aufSortier-Vergleich