Quicksort

Kurz: Quicksort ist ein schnelles Sortierverfahren nach dem Prinzip „Teile und herrsche“: Es wählt ein Pivot-Element, teilt die Liste in kleinere und größere Werte und sortiert beide Teile rekursiv.

Genauer: Im Durchschnitt braucht Quicksort O(n log n) Schritte und sortiert meist direkt im vorhandenen Speicher. Im schlechtesten Fall (ungünstige Pivot-Wahl bei bereits sortierten Daten) sind es O(n²). Eine zufällige oder mittlere Pivot-Wahl vermeidet das in der Praxis.

Im Detail

def quicksort(liste):
    if len(liste) <= 1:
        return liste
    pivot = liste[len(liste) // 2]
    kleiner = [x for x in liste if x < pivot]
    gleich  = [x for x in liste if x == pivot]
    groesser = [x for x in liste if x > pivot]
    return quicksort(kleiner) + gleich + quicksort(groesser)
 
print(quicksort([7, 2, 9, 4, 1, 8, 3]))   # [1, 2, 3, 4, 7, 8, 9]

Idee

1. Pivot wählen (hier das mittlere Element).
2. Alle kleineren Werte nach links, alle größeren nach rechts.
3. Beide Teillisten mit demselben Verfahren sortieren (Rekursion).
4. Zusammensetzen – das Pivot steht bereits an der richtigen Stelle.

Eigenschaften

Merkmal	Wert
Durchschnitt	O(n log n)
Schlechtester Fall	O(n²)
Zusatzspeicher	O(log n) (in-place-Variante)
Stabil	nein

Viele Standardbibliotheken nutzen Quicksort-Varianten (z. B. Introsort in C++); Java sortiert Objekte mit TimSort (Mischung aus Mergesort und Insertionsort) und Zahlen mit Dual-Pivot-Quicksort.

Siehe auch: Mergesort, Bubblesort, Sortieren, Big-O-Notation