Algorithmen3Lerneinheiten22minStand18.06.2026

Quicksort.

Quicksort sortiert ein Array, indem es ein Pivot-Element wählt und alle Werte $\leq$ 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^2)$ 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 ( $\leq$ 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.

Pivot wählen (z.B. das letzte Element)
Partitionieren: alle Werte $\leq$ Pivot nach links, alle Werte $>$ Pivot nach rechts (Lomuto-Konvention; gleiche Werte landen also im linken Bereich $\leq$ 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 ( $< \text{Pivot}$ , $= \text{Pivot}$ , $> \text{Pivot}$ in drei Bereichen) deutlich effizienter (Dutch National Flag, in der Praxis von vielen modernen Quicksort-Implementierungen verwendet).
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.

[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].

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.

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

✅ 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

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.

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:

Stell ein Array mit zufälliger Eingabe ein → ~n·log₂(n) Vergleiche, schön schnell
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.

Lade Visualisierung...

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.

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.

Lade Visualisierung...

Anmelden, um den Fortschritt zu speichern.

Nächster Schritt

Wenn du fertig bist: jetzt üben.

Aktives Abrufen festigt Wissen schneller als nochmal lesen.

Fachliche Qualität

S-Tier · GoldstandardZuletzt geprüft am 18.05.2026

Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.

Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen

Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).

Teil 1·Erklärung

Erklärung

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 degenerieren. Du lernst hier die (Pivot, Partition, ), die zwei Partitions-Schemata ( vs ) und (zwei Pointer von außen), warum mit Average / Worst-Case Speicher (Rekursionsstack), warum Quicksort ist (Standard-In-Place-Varianten), warum den Worst Case bei sortierten Eingaben vermeiden, und konkrete Praxisbeispiele (Java Dual-Pivot Quicksort für primitive , C++ mit Introsort = Quicksort + Heapsort-Fallback).

Zur KategorieAlgorithmen.Mehr Themen entdeckenZum Themen-Hub.

[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].

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

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

Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).

Teil 1·Erklärung

Erklärung

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²)

Pivot ist immer das Min/Max

Quicksort.

Die Idee in 3 Schritten

Visualisierung der Partition

Implementierung

Komplexität: zwei Gesichter

Eigenschaften

Wann sinnvoll?

Quicksort live (mit Worst-Case-Demo)

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

Wenn du fertig bist: jetzt üben.

Erklärung

Quicksort.

Die Idee in 3 Schritten

Visualisierung der Partition

Implementierung

Komplexität: zwei Gesichter

Eigenschaften

Wann sinnvoll?

Quicksort live (mit Worst-Case-Demo)

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

Wenn du fertig bist: jetzt üben.

Erklärung

Die Idee in 3 Schritten

Visualisierung der Partition

Implementierung

Komplexität: zwei Gesichter

Eigenschaften

Wann sinnvoll?

Interaktiv

Quicksort live (mit Worst-Case-Demo)

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

Quiz