Zerlegen am Pivot
- Pivot:ein Vergleichselement aus dem Bereich, hier das letzte (
a[rechts]). - Teilen:den Bereich zerlegen: Werte ≤ Pivot nach links, größere nach rechts, das Pivot dazwischen — dort steht es endgültig. Kostet \(n - 1\) Vergleiche.
- Herrschen:die Teile links und rechts vom Pivot rekursiv sortieren.
- Zusammenführen:entfällt — die Teile liegen schon in der richtigen Reihenfolge nebeneinander.
- Basisfall:Abbruchbedingung: ein Bereich mit höchstens einem Element (
links ≥ rechts) ist sortiert. - In-place:nur Tauschen innerhalb der Reihung, keine Hilfsreihung — aber nicht stabil.
static void quicksort(int[] a, int links, int rechts) {
if (links < rechts) { // sonst: Basisfall, 0 oder 1 Element
int p = zerlege(a, links, rechts); // Pivot steht danach an Index p
quicksort(a, links, p - 1); // kleinere Werte sortieren
quicksort(a, p + 1, rechts); // größere Werte sortieren
}
}
static int zerlege(int[] a, int links, int rechts) {
int pivot = a[rechts]; // Pivot: letztes Element
int grenze = links; // a[links..grenze-1] <= pivot
for (int k = links; k < rechts; k++) {
if (a[k] <= pivot) {
tausche(a, grenze, k);
grenze++;
}
}
tausche(a, grenze, rechts); // Pivot an seine Endposition
return grenze;
}
static void tausche(int[] a, int x, int y) {
int hilf = a[x];
a[x] = a[y];
a[y] = hilf;
}
Beispiel a = {41, 7, 63, 25, 88, 12, 36}, Aufruf zerlege(a, 0, 6) mit Pivot 36:
| k | a[k] | a[k] ≤ 36 | Tausch | grenze | Reihung danach |
|---|---|---|---|---|---|
| 0 | 41 | falsch | — | 0 | 41, 7, 63, 25, 88, 12, 36 |
| 1 | 7 | wahr | a[0] ↔ a[1] | 1 | 7, 41, 63, 25, 88, 12, 36 |
| 2 | 63 | falsch | — | 1 | 7, 41, 63, 25, 88, 12, 36 |
| 3 | 25 | wahr | a[1] ↔ a[3] | 2 | 7, 25, 63, 41, 88, 12, 36 |
| 4 | 88 | falsch | — | 2 | 7, 25, 63, 41, 88, 12, 36 |
| 5 | 12 | wahr | a[2] ↔ a[5] | 3 | 7, 25, 12, 41, 88, 63, 36 |
| — | Pivot | — | a[3] ↔ a[6] | 3 | 7, 25, 12, 36, 88, 63, 41 |
- Ergebnis:Rückgabe 3 nach 6 Vergleichen; weiter mit
quicksort(a, 0, 2)undquicksort(a, 4, 6).
Der Pivot entscheidet
Sortiere die Karten des aktuellen Bereichs in die Körbe „≤ Pivot“ und „> Pivot“: Karte anklicken, dann Korb anklicken — oder Karte mit Tab wählen und mit ← bzw. → einsortieren. Rechts wächst und schrumpft der Aufrufstapel. Vergleiche die Eingaben „zufällig“ und „sortiert“ und beide Pivot-Regeln.
Halte fest: Jede Zerlegung kostet einen Vergleich pro Karte und setzt das Pivot endgültig. Liegt das Pivot immer am Rand, wird jeder Bereich nur um eins kleiner — dann gibt es \(\frac{n(n-1)}{2}\) Vergleiche und der Aufrufstapel wird n − 1 Aufrufe tief.
Herleitung:Ungünstigster Fall: Das Pivot ist das größte (oder kleinste) Element, ein Teil ist leer, der andere hat \(n - 1\) Elemente.
Für den Rest gilt wieder dasselbe.
\(V(1) = 0\): ein einzelnes Element ist sortiert.
Quadratisch wie Selectionsort. Im günstigen Fall halbiert das Pivot jeden Bereich — dann gilt wie bei Mergesort \(V(n)\approx n\log_2 n\).
Quicksort: am Pivot zerlegen, beide Teile rekursiv sortieren · günstig und im Mittel \(\approx n\log_2 n\), ungünstigster Fall \(\frac{n(n-1)}{2}\) Vergleiche · in-place, nicht stabil.
Allgemeine Hinweise
Sortiert ist der schlimmste Fall
Mit dem letzten Element als Pivot ist eine bereits sortierte Reihung am ungünstigsten: Jedes Pivot ist das Maximum, der rechte Teil bleibt leer, die Rekursion wird n − 1 Aufrufe tief.
Pivot klug wählen
Das mittlere Element oder der Median aus erstem, mittlerem und letztem Element entschärft vorsortierte Daten. Man tauscht es vor dem Zerlegen an die letzte Stelle — der Rest von zerlege bleibt gleich.
p gehört zu keinem Teil
Die Aufrufe lauten quicksort(a, links, p - 1) und quicksort(a, p + 1, rechts). Wer p mitnimmt, sortiert das fertige Pivot erneut — im ungünstigen Fall endlos.