Quicksort

Grundidee und Eigenschaften

Quicksort ist ein schneller, rekursiver Sortieralgorithmus nach dem Prinzip „Teile und herrsche“. Rekursion bedeutet, dass ein Verfahren sich selbst auf kleinere Teilprobleme anwendet. Quicksort ist im Allgemeinen nicht stabil: Die ursprüngliche Reihenfolge von Elementen mit gleichem Wert kann sich beim Sortieren ändern.

Zunächst wählt der Algorithmus ein Pivotelement, also einen Vergleichswert aus der zu sortierenden Liste. Beim Partitionieren wird die Liste so geteilt, dass kleinere Elemente in den linken und größere Elemente in den rechten Teil gelangen. Elemente, die dem Pivot entsprechen, können je nach Teilungsverfahren auf beide Teile verteilt werden. Nach der Teilung sind alle Elemente des linken Teils kleiner oder gleich den Elementen des rechten Teils.

Anschließend werden beide Teillisten wieder mit Quicksort sortiert. Enthält eine Teilliste höchstens ein Element, ist sie bereits sortiert und die Rekursion endet. Damit das Verfahren sicher terminiert, muss jede neue Teilliste mindestens ein Element kürzer als die Ausgangsliste sein. Dies lässt sich beispielsweise erreichen, indem das Pivot an seine endgültige Position zwischen den Teillisten gesetzt und nicht mehr in weitere Teilungen einbezogen wird.

Partitionierung und Ablauf

Die Partitionierung kann weitgehend innerhalb der vorhandenen Liste erfolgen: Elemente werden nicht in neue Teillisten kopiert, sondern an ihren Positionen vertauscht. Bei einem Aufruf quicksort(links, rechts) bezeichnen links und rechts den ersten und letzten Index des aktuellen Bereichs. Der erste Aufruf verwendet links = 0 und rechts = n−1.

Ist links < rechts, liefert die Funktion teile(links, rechts) die endgültige Position des Pivots als teiler. Danach werden die Bereiche von links bis teiler−1 und von teiler+1 bis rechts rekursiv sortiert.

In der dargestellten Teilungsvariante ist daten[rechts] das Pivot. Ein Index i sucht von links nach einem Element, das größer als das Pivot ist. Ein Index j sucht von rechts nach einem Element, das kleiner oder gleich dem Pivot ist. Solange sich die Suchrichtungen noch nicht getroffen haben, werden solche falsch eingeordneten Elemente vertauscht. Danach wird das Pivot an die gefundene Trennposition gesetzt. Links davon stehen nur Werte kleiner oder gleich dem Pivot, rechts davon größere Werte. Sobald beide Teilbereiche für sich sortiert sind, ist auch der gesamte Bereich sortiert.

Beispiele

Bei der Buchstabenfolge „einbeispiel“ dient das letzte Zeichen „l“ als Pivot. Die Suche von links findet zunächst ein Zeichen größer als „l“, die Suche von rechts eines kleiner oder gleich „l“. Durch wiederholtes Vertauschen entsteht vor dem abschließenden Pivottausch die Folge „e i e b e i i p s n l“. Anschließend wird „l“ an die Trennstelle gesetzt: „e i e b e i i l s n p“. Links von „l“ befinden sich nur Zeichen ≤ „l“, rechts nur Zeichen > „l“.

Das vollständige Beispiel sortiert „Quicksort“ ebenfalls durch wiederholte Teilung. Zuerst wird das letzte Zeichen „t“ als Pivot verwendet; danach werden die entstandenen Teilbereiche rekursiv verarbeitet. Teilbereiche mit nur einem Zeichen gelten bereits als sortiert. Das Endergebnis lautet „cikoQrstu“.

Laufzeit und Pivotwahl

Die Laufzeit hängt wesentlich davon ab, wie ausgewogen das Pivot die Liste teilt. Im Worst Case, also im schlechtesten Fall, ist das Pivot in jedem Schritt das kleinste oder größte Element. Das kann geschehen, wenn stets das letzte Element gewählt wird und die Liste bereits sortiert ist. Dann schrumpft der noch zu bearbeitende Bereich jeweils nur um ein Element. Die Zeitkomplexität beträgt O(n²), und die Zahl der Vergleiche ist n·(n+1)/2−1 = n²/2+n/2−1.

Im Best Case entstehen stets ungefähr gleich große Teillisten. Dann beträgt die asymptotische Laufzeit O(n·log(n)). Diese Größenordnung gilt auch im Average Case, dem durchschnittlichen Fall. Die längere Teilliste hat dort im Mittel die Länge (2/n)·∑ von i=n/2 bis n−1 über i = 3n/4−2/4; die Rekursionstiefe liegt deshalb in O(log(n)). Die durchschnittliche Vergleichszahl beträgt ungefähr 2·log(2)·(n+1)·log₂(n) ≈ 1,39·(n+1)·log₂(n).

Einfach gewählt werden kann das erste, letzte oder mittlere Element, doch dieser Ansatz kann ungünstig sein. Aus drei solchen Elementen lässt sich stattdessen der Median als Pivot wählen. Randomisiertes Quicksort verwendet ein zufälliges Element; dass dadurch bei jeder Teilung der Worst Case entsteht, ist extrem unwahrscheinlich. Der Median-of-medians-Algorithmus bestimmt einen Median in O(n) und kann für Quicksort insgesamt eine Worst-Case-Laufzeit von O(n·log(n)) garantieren.

Heapsort ist auch im Worst Case auf O(n·log(n)) beschränkt. Quicksort wird dennoch häufig eingesetzt, weil der Worst Case selten auftritt und seine innere Schleife nur wenige einfache Operationen enthält. Ob es im Mittel tatsächlich schneller als Heapsortvarianten ist, wird unterschiedlich beurteilt und ist laut Artikel weiterhin Forschungsgegenstand. Introsort verbindet eine vergleichbare mittlere Laufzeit mit einer garantierten oberen Schranke von O(n·log(n)) im Worst Case.

Speicherbedarf und Schutz vor tiefer Rekursion

Obwohl die Listenelemente innerhalb der Liste vertauscht werden, benötigt die rekursive Ausführung zusätzlichen Speicher auf dem Aufruf-Stack. Deshalb bezeichnet der Artikel Quicksort unter Berücksichtigung dieses Stacks nicht als vollständig in-place. Bei ausgewogenen Teilungen und im Durchschnitt beträgt die Rekursionstiefe und damit der Stapelbedarf O(log(n)). Im ungünstigsten Fall wächst sie auf O(n), was bei langen Listen einen Stapelüberlauf auslösen kann.

Gegenmaßnahmen sind eine ausgewogenere Pivotwahl, etwa der Median von drei Elementen, ein zufälliges Pivot und das Vermeiden sehr kleiner Teillisten. Endrekursionsbeseitigung ersetzt einen der beiden rekursiven Aufrufe durch eine Schleife: Die kürzere Teilliste wird rekursiv sortiert, während die längere iterativ weitergeteilt wird. Dadurch ist die Rekursionstiefe nicht größer als log(n).

Eine weitere Variante sortiert zuerst die kleinere Teilfolge rekursiv und danach auch die andere rekursiv. So bleiben höchstens O(log(n)) noch nicht sortierte Teilfolgen vorgemerkt. Da für jede zwei Indexgrenzen von jeweils O(log(n)) Speicherbedarf gespeichert werden, gibt der Artikel dafür insgesamt O(log²(n)) zusätzlichen Speicher an.

Varianten und Erweiterungen

Für verkettete Listen kann das erste Element einer Teilfolge als Pivot dienen. Zeiger2 durchläuft die Folge und sucht Werte kleiner als das Pivot; Zeiger1 markiert das Ende des Bereichs mit kleineren Elementen. Geeignete Knoten beziehungsweise ihre Inhalte werden vertauscht, und zuletzt kommt das Pivot zwischen beide Teilfolgen. Weitgehend sortierte Folgen oder viele gleiche Schlüssel können dabei zu einem Worst-Case-ähnlichen Verhalten führen. Für verkettete Listen wird daher häufig Mergesort bevorzugt, dessen Worst-Case-Laufzeit O(n·log(n)) beträgt. Balancierte Bäume wie B-Bäume oder AVL-Bäume verteilen die Sortierkosten bereits auf die Einfügeoperationen.

Iteratives Quicksort ersetzt die Rekursion durch einen kleinen Stack oder ein Array. Eine dargestellte Variante wählt das Pivot zufällig, bearbeitet zunächst einen Teil und legt die Grenze des anderen mit push auf den Stack; pop holt sie später zurück. Die zufällige Pivotwahl führt mit hoher Wahrscheinlichkeit zum Average Case. Der nötige Stapelspeicher ist mit ausreichender Sicherheit kleiner als 2·log₂(n). Läuft ein begrenzter Stack dennoch über, kann die Sortierung des verbleibenden Bereichs erneut begonnen werden.

Quicksort ist besonders effizient, solange Elemente über große Entfernungen vertauscht werden. Bei kurzen Teillisten wird es weniger effizient und nähert sich einer Komplexität von O(n²). Da die Partitionierung den Abstand der Elemente zu ihren endgültigen Positionen begrenzt, kann Insertionsort eine solche Liste in linearer Zeit sortieren. Implementierungen brechen Quicksort deshalb häufig unterhalb einer festgelegten Teillistenlänge ab und setzen mit Insertionsort fort.

Sind mehrere Prozessoren oder Prozessorkerne vorhanden, lassen sich unabhängige Teillisten parallel sortieren. Ein solcher paralleler Quicksort kann unter Umständen bessere Laufzeiten erreichen.