Quicksort

Quicksort ist ein vergleichsbasierter Sortieralgorithmus, der nach dem Divide-and-Conquer-Prinzip (Teile und Herrsche) arbeitet. Er wurde 1960 von Tony Hoare entwickelt und gilt als einer der in der Praxis schnellsten Sortieralgorithmen. Das Grundprinzip lässt sich in drei Schritte gliedern:

1. Pivot-Wahl: Wähle ein Element aus der Liste als Pivotelement.
2. Partitionierung: Teile die restlichen Elemente in zwei Teillisten – eine mit Elementen kleiner als das Pivot und eine mit Elementen größer als das Pivot.
3. Rekursion: Sortiere beide Teillisten rekursiv mit demselben Verfahren.

Der Algorithmus terminiert, wenn eine Teilliste nur noch ein oder kein Element enthält – diese ist trivialerweise sortiert.

Die Wahl des Pivotelements hat entscheidenden Einfluss auf die Effizienz des Algorithmus:

• Erstes/letztes Element: Einfach zu implementieren, aber bei bereits sortierten Listen entsteht der Worst Case.
• Zufälliges Element (Randomized Quicksort): Vermeidet systematische Worst-Case-Szenarien; im Mittel sehr effizient.
• Median-of-Three: Der Median aus erstem, mittlerem und letztem Element wird gewählt. Dies liefert in der Praxis häufig gute Ergebnisse und vermeidet extreme Ungleichverteilungen.

Bei der Partitionierung werden die Elemente um das Pivot herum angeordnet. Zwei gängige Varianten sind:

• Lomuto-Partitionierung: Ein Index i durchläuft die Liste von links. Elemente kleiner als das Pivot werden nach vorne getauscht. Am Ende wird das Pivot an seine endgültige Position gesetzt.
• Hoare-Partitionierung: Zwei Zeiger laufen von beiden Enden aufeinander zu und tauschen Elemente, die auf der falschen Seite stehen. Dies ist in der Praxis effizienter, da weniger Vertauschungen stattfinden.

Der folgende Pseudocode zeigt Quicksort mit Lomuto-Partitionierung:

algorithmus quicksort(A, links, rechts):
    wenn links < rechts:
        p = partition(A, links, rechts)
        quicksort(A, links, p - 1)
        quicksort(A, p + 1, rechts)

algorithmus partition(A, links, rechts):
    pivot = A[rechts]
    i = links - 1
    für j = links bis rechts - 1:
        wenn A[j] ≤ pivot:
            i = i + 1
            tausche A[i] mit A[j]
    tausche A[i + 1] mit A[rechts]
    gib (i + 1) zurück

public static void quicksort(int[] arr, int lo, int hi) {
    if (lo < hi) {
        int p = partition(arr, lo, hi);
        quicksort(arr, lo, p - 1);
        quicksort(arr, p + 1, hi);
    }
}

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

Die Laufzeit von Quicksort hängt maßgeblich von der Pivot-Wahl ab:

• Best Case: O(n · log n) – Das Pivot teilt die Liste stets in zwei gleich große Hälften. Die Rekursionstiefe beträgt log n, auf jeder Ebene wird O(n) Arbeit verrichtet.
• Average Case: O(n · log n) – Bei zufälliger Pivot-Wahl ergibt sich im Mittel eine logarithmische Rekursionstiefe.
• Worst Case: O(n²) – Tritt auf, wenn das Pivot stets das kleinste oder größte Element ist (z. B. bei bereits sortierter Liste und Wahl des ersten Elements). Die Rekursionstiefe wird n.

Speicherverbrauch: Quicksort arbeitet in-place (kein zusätzliches Array nötig), benötigt aber O(log n) Speicher auf dem Call-Stack (Rekursion). Im Worst Case kann der Stack O(n) tief werden.

Beide Algorithmen nutzen Divide-and-Conquer, unterscheiden sich aber wesentlich:

• Laufzeit: MergeSort hat immer O(n · log n) – auch im Worst Case. Quicksort kann im Worst Case auf O(n²) degenerieren.
• Speicher: MergeSort benötigt O(n) zusätzlichen Speicher (für das Zusammenfügen). Quicksort arbeitet in-place.
• Stabilität: MergeSort ist stabil (gleiche Elemente behalten ihre relative Reihenfolge). Quicksort ist nicht stabil.
• Praxis: Quicksort ist in der Praxis oft schneller als MergeSort, da es weniger Speicherzugriffe benötigt und cache-freundlicher ist.

Abitur-Tipp: Im Abitur wird häufig verlangt, Quicksort an einem konkreten Zahlenbeispiel Schritt für Schritt durchzuführen. Übe das Partitionierungsverfahren mit kleinen Arrays (5–8 Elemente). Achte darauf, die Pivot-Wahl und die Aufteilung in Teillisten klar zu dokumentieren. Ein Vergleich mit MergeSort hinsichtlich Laufzeit, Speicher und Stabilität ist ein Klassiker in Abiturklausuren.