Mit Google fortfahren
Quicksort einfach erklärt: Ablauf und Laufzeit
Quicksort sortiert eine Folge, indem es ein Vergleichselement auswählt, die übrigen Elemente daran aufteilt und die entstehenden Teilfolgen nach demselben Prinzip sortiert. Entscheidend sind also drei Ideen: Pivot wählen, partitionieren, rekursiv weitermachen.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Wie zerlegt Quicksort ein Sortierproblem?
Stell dir vor, du möchtest Zahlen der Größe nach ordnen. Du wählst zunächst eine Zahl als Vergleichsgröße. Diese Zahl heißt Pivot.
Pivot und Partitionierung
Das Pivot ist das Vergleichselement eines aktuellen Teilproblems. Beim Partitionieren werden kleinere Werte auf die eine Seite und größere Werte auf die andere Seite verteilt. Gleiche Werte müssen nach einer festgelegten Regel ebenfalls erhalten bleiben.
Quicksort folgt dem Prinzip Teile und herrsche:
- Wähle im aktuellen Bereich ein Pivot.
- Partitioniere die Werte in „kleiner“, „gleich“ und „größer“.
- Sortiere den kleineren und den größeren Bereich rekursiv. Rekursiv bedeutet: Das Verfahren ruft sich für kleinere Teilprobleme selbst auf.
- Setze die sortierten Bereiche und die gleichen Werte zusammen.
- Beende einen Zweig, sobald er höchstens ein Element enthält. Das ist der Basisfall.
Es gibt verschiedene Quicksort-Varianten. Manche erzeugen neue Teillisten. Andere vertauschen Werte direkt im vorhandenen Array. Deshalb können Tauschfolge und Grenzen unterschiedlich aussehen, obwohl die Grundidee gleich bleibt.
Nach einer korrekten Partitionierung liegen alle Werte des linken Bereichs unter dem Pivotwert und alle Werte des rechten Bereichs darüber. Gleiche Werte werden nach der gewählten Variante eindeutig behandelt.
So sortierst du eine Folge vollständig
Wir verwenden hier die übersichtliche Variante mit drei Teillisten. Sie zeigt die Rekursion klar, ist aber nicht in place.
Sortiere [6, 8, 2, 5, 9, 1, 7, 3, 4]. Als Pivot dient jeweils das erste Element eines Teilbereichs.
Erste Zerlegung mit Pivot 6
- kleiner:
[2, 5, 1, 3, 4] - gleich:
[6] - größer:
[8, 9, 7]
Linken Bereich sortieren
Für [2, 5, 1, 3, 4] ist 2 das Pivot:
- kleiner:
[1] - gleich:
[2] - größer:
[5, 3, 4]
Für [5, 3, 4] ist 5 das Pivot. Links entsteht [3, 4], rechts bleibt der Bereich leer. Der Bereich [3, 4] wird mit Pivot 3 zu [3, 4]. Damit ist der gesamte linke Bereich [1, 2, 3, 4, 5].
Rechten Bereich sortieren
Für [8, 9, 7] ist 8 das Pivot:
- kleiner:
[7] - gleich:
[8] - größer:
[9]
Damit ist der rechte Bereich [7, 8, 9].
Zusammensetzen
[1, 2, 3, 4, 5] + [6] + [7, 8, 9] ergibt [1, 2, 3, 4, 5, 6, 7, 8, 9].
Bei Duplikaten darf kein Wert verschwinden. Für [4, 2, 4, 1] und Pivot 4 entstehen daher [2, 1], [4, 4] und eine leere größere Liste.
Warum liefert Quicksort die richtige Reihenfolge?
Eine Korrektheitsbegründung beantwortet zwei Fragen: Endet das Verfahren, und ist sein Ergebnis dann wirklich sortiert?
1. Der Basisfall ist korrekt. Eine leere Folge und eine Folge mit einem Element sind bereits sortiert.
2. Die Partitionierung schafft Ordnung zwischen den Bereichen. Nach dem Aufteilen ist jeder Wert im kleineren Bereich kleiner als der Pivotwert. Jeder Wert im größeren Bereich ist größer. Gleiche Werte stehen im Gleichheitsbereich.
3. Die Teilprobleme werden kleiner. Mindestens die Pivotelemente liegen nicht mehr in den rekursiv zu sortierenden Bereichen. Deshalb erreicht jeder Rekursionszweig schließlich den Basisfall.
4. Die Rekursion sortiert beide Seiten. Sind der kleinere und der größere Bereich korrekt sortiert, ist auch ihre Zusammensetzung korrekt:
sortiert(kleiner) + gleich + sortiert(größer).
An jeder Grenze gilt die richtige Größenbeziehung. Daher ist die gesamte Folge aufsteigend sortiert.
Bei einer In-Place-Variante sehen die Teilbereiche und Rekursionsgrenzen anders aus. Die Begründung bleibt aber gleich: Die Partitionierungsregel muss gelten, die rekursiven Bereiche müssen kleiner werden und der Basisfall muss erreichbar sein.
Wie beeinflusst das Pivot die Laufzeit?
Die Laufzeitkomplexität beschreibt, wie der Rechenaufwand mit der Eingabegröße $n$ wächst. Die Landau-Notation $O(\ldots)$ betrachtet dabei das dominante Wachstum, nicht eine konkrete Zeit in Millisekunden.
Ausgewogene Zerlegung
Teilt das Pivot die Werte immer ungefähr in zwei gleich große Bereiche, entstehen etwa $\log_2 n$ Rekursionsebenen. Über alle Teilbereiche einer Ebene werden insgesamt ungefähr $n$ Elemente bearbeitet.
$$T(n)=O(n\log n)$$
Dies ist der Best Case. Auch der durchschnittliche Fall wird mit $O(n\log n)$ eingeordnet.
Extrem ungleiche Zerlegung
Ist das Pivot immer der kleinste oder größte Wert, entstehen Teilprobleme der Größen $n-1$ und 0. Dann werden nacheinander ungefähr $n-1, n-2, \ldots, 1$ Vergleiche benötigt:
$$(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$$
Damit wächst der Aufwand quadratisch:
$$T(n)=O(n^2)$$
Bei acht verschieden großen, bereits sortierten Werten und einer Regel „erstes Element als Pivot“ sind es in diesem Modell
$$\frac{8\cdot7}{2}=28$$
Vergleiche.
Pivotqualität beeinflusst die Balance der Partitionen. Diese Balance bestimmt Rekursionstiefe, Laufzeit und Bedarf des Aufrufstapels.
Als Pivot kommen zum Beispiel das erste, letzte, mittlere oder ein zufälliges Element infrage. Eine geeignetere Strategie kann sehr ungleiche Partitionen unwahrscheinlicher machen. Sie garantiert jedoch nicht für jede Eingabe eine perfekte Halbierung.
Welche Eigenschaften musst du bei der Auswahl beachten?
In place bedeutet, dass die Partitionierung Werte direkt im vorhandenen Array vertauscht, statt für die Bereiche neue Listen anzulegen. Trotzdem braucht Quicksort Speicher für den Aufrufstapel, der die noch nicht beendeten rekursiven Aufrufe verwaltet.
- Bei ausgewogenen und durchschnittlichen Zerlegungen liegt die Rekursionstiefe typischerweise in $O(\log n)$.
- Im Worst Case kann sie $n$ erreichen.
- Die leicht verständliche Drei-Listen-Variante ist nicht in place, weil sie neue Listen erzeugt.
Quicksort ist in üblichen In-Place-Varianten nicht stabil. Ein stabiler Sortieralgorithmus bewahrt die ursprüngliche Reihenfolge von Datensätzen mit gleichem Sortierschlüssel. Durch weite Vertauschungen kann Quicksort diese Reihenfolge ändern.
Die Einträge 7a und 7b haben beide den Sortierschlüssel 7, aber unterschiedliche Zusatzinformationen. In [7a, 8, 7b, 2, 6] kann eine In-Place-Partitionierung 7a mit 2 tauschen. Danach steht 7b vor 7a. Die Werte sind nach dem Schlüssel weiterhin sortierbar, doch die ursprüngliche Reihenfolge der beiden Siebener ist verloren.
Für die Auswahl eines Sortierverfahrens reicht die Durchschnittslaufzeit allein deshalb nicht aus. Du musst auch Pivotstrategie, mögliche Eingabeformen, Speicherbedarf und die geforderte Stabilität beachten.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Quicksort
- Ablauf: Pivot wählen, partitionieren, rekursiv sortieren
- Korrektheit: Basisfall, kleinere Teilprobleme, geordnete Grenzen
- Pivotwahl: bestimmt die Balance der Partitionen
- Laufzeit: durchschnittlich $O(n\log n)$, schlimmstenfalls $O(n^2)$
- Speicher: In-Place-Datenhaltung plus Aufrufstapel
- Stabilität: übliche In-Place-Varianten sind nicht stabil