mini|Eine zufällige Permutation von Integerwerten wird mit Quicksort sortiert. Die blauen Linien zeigen den Wert des rot markierten Pivotelements im jeweiligen Rekursionsschritt.
Quicksort ( und ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche arbeitet. Er wurde ca. 1960 von C. Antony R. Hoare in seiner Grundform entwickelt und seitdem von vielen Forschern verbessert. Der Algorithmus hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und dass er, abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack, ohne zusätzlichen Speicherplatz auskommt.
Im Durchschnitt führt der Quicksort-Algorithmus Vergleiche durch. Im schlechtesten Fall werden Vergleiche durchgeführt, was aber in der Praxis sehr selten vorkommt.
mini|Die Zahlen von 1 bis n in zufälliger Reihenfolge werden mit Quicksort sortiert.
Prinzip Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt. Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.
Anschließend muss man also noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so weiter. Diese Selbstaufrufe werden als Rekursion bezeichnet. Wenn eine Teilliste der Länge eins oder null auftritt, so ist diese bereits sortiert und es erfolgt der Abbruch der Rekursion.
Die Positionen der Elemente, die gleich dem Pivotelement sind, hängen vom verwendeten Teilungsalgorithmus ab. Sie können sich beliebig auf die Teillisten verteilen. Da sich die Reihenfolge von gleichwertigen Elementen zueinander ändern kann, ist Quicksort im Allgemeinen nicht stabil.
Das Verfahren muss sicherstellen, dass jede der Teillisten mindestens um eins kürzer ist als die Gesamtliste. Dann endet die Rekursion garantiert nach endlich vielen Schritten. Das kann z. B. dadurch erreicht werden, dass das ursprünglich als Pivot gewählte Element auf einen Platz zwischen den Teillisten gesetzt wird und somit zu keiner Teilliste gehört.
Pseudocode Die Implementierung der Teilung erfolgt als In-place-Algorithmus: Die Elemente werden nicht in zusätzlichen Speicher kopiert, sondern nur innerhalb der Liste vertauscht. Dafür wird ein Verfahren verwendet, das als Teilen oder auch Partitionieren bezeichnet wird. Danach sind die beiden Teillisten gleich in der richtigen Position. Sobald die Teillisten in sich sortiert wurden, ist die Sortierung der Gesamtliste beendet.
Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus, wobei daten die zu sortierende Liste mit n Elementen ist. Bei jedem Aufruf von quicksort() gibt links den Index des ersten Elements in der Teilliste an und rechts den des letzten. Beim ersten Aufruf (oberste Rekursionsebene) ist links = 0 und rechts = n-1. Die übergebene Liste wird dabei rekursiv immer weiter geteilt, bis sie nur noch einen Wert enthält.
funktion quicksort(links, rechts) falls links < rechts dann teiler:= teile(links, rechts) quicksort(links, teiler - 1) quicksort(teiler + 1, rechts) ende ende
Die folgende Implementierung der Funktion teile teilt das Feld so, dass sich das Pivotelement an seiner endgültigen Position befindet und alle kleineren Elemente davor stehen, während alle größeren danach kommen:
funktion teile(links, rechts) i:= links // Starte mit j links vom Pivotelement j:= rechts - 1 pivot:= daten[rechts] wiederhole solange i < j // solange i an j nicht vorbeigelaufen ist // Suche von links ein Element, welches größer als das Pivotelement ist wiederhole solange i < j und daten[i] <= pivot i:= i + 1 ende // Suche von rechts ein Element, welches kleiner oder gleich dem Pivotelement ist wiederhole solange j > i und daten[j] > pivot j:= j - 1 ende falls daten[i] > daten[j] dann tausche daten[i] mit daten[j] ende ende // Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i]) // und gib die neue Position des Pivotelements zurück, beende Durchlauf falls daten[i] > pivot dann tausche daten[i] mit daten[rechts] sonst i:= rechts ende antworte i ende
Nach der Wahl des Pivotelementes wird zunächst ein Element vom Anfang der Liste beginnend gesucht (Index i), welches größer als das Pivotelement ist. Entsprechend wird vom Ende der Liste beginnend ein Element kleiner als das Pivotelement gesucht (Index j). Die beiden Elemente werden dann vertauscht und landen damit in der jeweils richtigen Teilliste. Dann werden die beiden Suchvorgänge von den erreichten Positionen fortgesetzt, bis sich die untere und obere Suche treffen; dort ist die Grenze zwischen den beiden Teillisten.
Beispiel teile(links, rechts)
Die Buchstabenfolge „einbeispiel“ soll alphabetisch sortiert werden.
Ausgangssituation nach Initialisierung von i und j, das Element rechts (l) ist das Pivotelement:
e i n b e i s p i e l ^ ^ i j
Nach der ersten Suche in den inneren Schleifen hat i auf einem Element > l und j auf einem Element <= l gehalten:
e i n b e i s p i e l ^ ^ i j
Nach dem Tauschen der Elemente bei i und j:
e i e b e i s p i n l ^ ^ i j
Nach der nächsten Suche und tauschen:
e i e b e i i p s n l ^ ^ i j
Nach einer weiteren Suche sind die Indizes aneinander vorbeigelaufen:
e i e b e i i p s n l ^ ^ j i
Nach dem Tauschen von i und Pivot bezeichnet i die Trennstelle der Teillisten. Bei i steht das Pivot-Element, links davon sind nur Elemente ≤ Pivot und rechts nur solche > Pivot:
e i e b e i i l s n p ^ i
Vollständiges Beispiel für alphabetische Sortierung In diesem Beispiel soll der Quicksortalgorithmus die Buchstabenfolge „Quicksort“ sortieren. Zunächst wird das rechte Element P-> als Pivotelement definiert. Dann laufen die Zähler g für „größer“ von links nach rechts und k für „kleiner“ von rechts nach links los,
Quicksort ^ ^^ g kP
bis g auf ein Element trifft, welches größer als das Pivotelement ist und bis k auf ein Element trifft, welches kleiner oder gleich dem Pivotelement ist.
Quicksort ^ ^^ g kP
Diese beiden gefundenen Elemente r und u werden dann im folgenden Schritt getauscht.
Qricksout ^ ^^ g kP
Im folgenden Schritt laufen die Indizes k und g in der gleichen Richtung wie gehabt weiter und suchen Elemente, die bei k kleiner als oder gleich dem Pivotelement und bei g größer als das Pivotelement sind.
Qricksout ^^^ kgP
Jetzt sind k und g aneinander vorbeigelaufen. Dieses Ereignis ist eine Abbruchbedingung. Jetzt wird das Pivotelement mit dem durch g indizierten Element getauscht.
Qricksotu ^^^ kPg
Jetzt treffen folgende zwei Aussagen zu: „Links des Pivotelements sind alle Elemente kleiner oder gleich dem Pivotelement. Rechts des Pivotelements sind alle Elemente größer oder gleich dem Pivotelement.“
links|:|rechts Qrickso|t|u ^|^|^ k|P|g
Das Pivotelement „teilt“ nun die Datenmenge an der Stelle des Pivotelements in zwei Hälften Links und Rechts. Nun muss der Algorithmus den linken und den rechten Teil auf die gleiche Weise wie im Vorangehenden schon geschehen weiterbehandeln. Hierdurch ergibt sich nun die Rekursion. Der rechte Teil (Der Buchstabe u) ist nur ein einzelnes Element und ist somit per Definition sortiert. Also wird nun der linke Teil behandelt. Das rechte Element ist wieder das Pivotelement, und die Zähler werden passend gesetzt.
Qrickso|t|u ^ ^^ g kP
Das Q ist größer als o und das k ist kleiner als das o.
Qrickso|t|u ^ ^ ^ g k P
Also werden das Q und das k vertauscht.
kricQso|t|u ^ ^ ^ g k P
Indizes g und k laufen weiter...
kricQso|t|u ^ ^ ^ g k P
Das r und das c werden getauscht.
kcirQso|t|u ^ ^ ^ g k P
Im folgenden Schritt sind die Indizes wieder aneinander vorbeigelaufen...
kcirQso|t|u ^^ ^ kg P
… und das Pivotelement (Buchstabe o) wird mit dem größeren Element (Buchstabe r) getauscht.
kcioQsr|t|u ^^ ^ kP g
Nun ergibt sich erneut ein linker und ein rechter Teil.
links:rechts kci|o|Qsr |t|u ^|^| ^ | | k|P| g | |
Zunächst wird der linke Teil behandelt.
kci|o| Qsr|t|u ^ ^^| |^ ^^| | g kP| |g kP| |
cki|o| Qsr|t|u ^^^| |^ ^^| | gkP| |g kP| |
Buchstabe c und k werden getauscht.
cki|o| Qsr|t|u ^^^| |^ ^^| | kgP| |g kP| |
Indizes sind aneinander vorbeigelaufen, und das Element des Index g wird mit dem des Index P vertauscht.
cik|o| Qsr|t|u ^^^| |^ ^^| | kPg| |g kP| |
Der jetzt entstandene neue linke und rechte Teil besteht nun nur noch aus einem einzelnen Element und gilt als sortiert.
cik|o| Qsr|t|u | | ^^^| | | | kgP| |
Im ehemals rechten Teil (Buchstaben Qsr) laufen die Indizes direkt aneinander vorbei, und das Element bei g wird mit dem Pivotelement getauscht.
cik|o| Qrs|t|u | | ^^^| | | | kPg| |
Damit sind alle Zeichen sortiert.
cik|o| Qrs|t|u
Ergebnis: cikoQrstu
Kenngrößen Laufzeit Die Laufzeit des Algorithmus hängt im Wesentlichen von der Wahl des Pivotelementes ab.
Im Worst Case (schlechtesten Fall) wird das Pivotelement stets so gewählt, dass es das größte oder das kleinste Element der Liste ist. Dies ist etwa der Fall, wenn als Pivotelement stets das Element am Ende der Liste gewählt wird und die zu sortierende Liste bereits sortiert vorliegt. Die zu untersuchende Liste wird dann in jedem Rekursionsschritt nur um eins kleiner und die Zeitkomplexität wird beschrieben durch . Die Anzahl der Vergleiche ist in diesem Fall .
Im Best Case (besten Fall) wird das Pivotelement stets so gewählt, dass die beiden entstehenden Teillisten etwa gleich groß sind. In diesem Fall gilt für die asymptotische Laufzeit des Algorithmus . Diese Zeitkomplexität gilt ebenso für den Average Case (durchschnittlichen Fall). Die Länge der jeweils längeren Teilliste beim rekursiven Aufruf ist nämlich im Schnitt
und die Tiefe der Rekursion damit in . Im Average Case ist die Anzahl der Vergleiche etwa .Performanceof Quicksort (PDF) University of Illinois System, Department of Mathematics, Statistics, and Computer Science.
Für die Wahl des Pivotelementes sind in der Literatur verschiedene Ansätze beschrieben worden. Die Wahrscheinlichkeit des Eintreffens des Worst Case ist bei diesen unterschiedlich groß.
Ein möglicher Ansatz ist es, immer das erste, das letzte oder das mittlere Element der Liste zu wählen. Dieser naive Ansatz ist aber relativ ineffizient. Eine andere Möglichkeit ist es, den Median dieser drei Elemente zu bestimmen und als Pivotelement zu verwenden. Ein anderer Ansatz ist, als Pivotelement ein zufälliges Element auszuwählen. Bei diesem randomisierten Quicksort ist die Wahrscheinlichkeit, dass das Pivotelement in jedem Teilungsschritt so gewählt wird, dass sich die Worst-Case-Laufzeit ergibt, extrem gering. Man kann davon ausgehen, dass er praktisch nie auftritt.
Es gibt Algorithmen, beispielsweise Heapsort, deren Laufzeiten auch im Worst Case durch beschränkt sind. In der Praxis wird aber trotzdem Quicksort eingesetzt, da angenommen wird, dass bei Quicksort der Worst Case nur sehr selten auftritt und im mittleren Fall schneller als Heapsort ist, da die innerste Schleife von Quicksort nur einige wenige, sehr einfache Operationen enthält. Dies ist jedoch noch Forschungsgegenstand und einige Analysen und Simulationen sehen Heapsortvarianten vorne, sowohl aus informationstheoretischen Überlegungen wie Implementierungsbetrachtungen.