QuickSort (von engl. quick - schnell) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (engl. Divide and conquer) arbeitet. Er wurde 1960 von C. Antony R. Hoare in seiner Grundform erfunden und seit dem von vielen Forschern weiter entwickelt. Der Algorithmus hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und ohne zusätzlichen Speicherplatz auskommt (abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack).
Prinzip
QuickSort wählt ein Element aus der zu sortierenden Liste aus ("Pivotelement") und zerlegt die Liste in zwei Teillisten, eine obere und eine untere, von denen die eine alle Elemente enthält, die größer sind als das Pivotelement, die andere den Rest. Dazu wird zunächst ein Element von unten gesucht, das größer als das Pivotelement und damit für die untere Liste zu groß ist. Entsprechend wird von oben ein kleineres (oder gleichgroßes) Element als das Pivotelement gesucht. Die beiden Elemente werden dann vertauscht und landen damit in der jeweils richtigen Liste. Der Vorgang wird fortgesetzt, bis sich die untere und obere Suche treffen. Damit sind die oben erwähnten Teillisten in einem einzigen Durchlauf entstanden. Suche und Vertauschung können in-place durchgeführt werden.
Die noch unsortierten Teillisten werden über denselben Algorithmus in noch kleinere Teillisten zerlegt (z.B. mittels Rekursion) und, sobald nur noch Listen mit je einem Element vorhanden sind, wieder zusammengesetzt. Die Sortierung ist damit abgeschlossen.
Laufzeit
Der Algorithmus wird meist so implementiert, dass als Pivotelement das Element in der Mitte oder am Ende der (Teil-)Liste gewählt wird.
Im worst case (schlimmsten 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.
QuickSort liegt im worst case in der Aufwandsklasse O(n²), im Mittel in der Aufwandsklasse O(n·log(n)).
Ein Ansatz, um worst-case-Laufzeiten zu verhindern, ist, als Pivotelement ein zufällig bestimmtes Element zu wä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, so dass man praktisch von einer Komplexität von O(n·log(n)) ausgehen kann.
In der Praxis ist das schlechte Worst Case Verhalten des Algorithmus' oft problematisch. Er wird trotzdem häufig verwendet, denn er wurde gründlich mathematisch analysiert und diese Analyse wurde durch umfangreiche empirische Erfahrungen bestätigt. Er ist auch heute noch für ein breites Spektrum von praktischen Anwendungen die bevorzugte Sortiermethode, weil er, sofern Rekursionen zur Verfügung stehen, einfach zu implementieren ist und Implementationen außerdem in vielen Standard-Bibiotheken vorhanden sind.
Durch geschickte Techniken der Median Wahl (z.B. Verwendung des Mittleren Elements von mehreren zufällig ausgewählten) kann man das mittlere schlechteste Verhalten verbessern. Das Eintreten des Worst Cases kann man jedoch nicht beeinflussen.
Quicksort setzt jedoch voraus, dass effizient (d.h mit Aufwand O(1)) über einen Index auf die Elemente zugegriffen werden kann. Dies ist jedoch meist nur bei Arrays der Fall. Für verkettete Listen sind andere Sortieralgorithmen meist effektiver, wie etwa adaptiertes 2-Phasen-2-Band-Mischen oder Mergesort. Andere dynamische Datenstrukturen wie balancierte Bäume (B-Bäume, AVL-Bäume oder 2-3-4-Bäume, letztere meist effektiv implementiert als Rot-Schwarz-Baum) verteilen die Kosten des Sortierens auf die Einfügeoperationen, so dass nachträgliches Sortieren nicht notwendig ist.
Implementierung
Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus:
prozedur quicksort(linke_grenze, rechte_grenze) {
wenn (rechte_grenze > linke_grenze) {
teilung_grenze = feld_aufteilen(linke_grenze, rechte_grenze);
quicksort(linke_grenze, teilung_grenze);
quicksort(teilung_grenze + 1, rechte_grenze);
}
}
Die Funktion feld_aufteilen muss dabei das Feld so teilen, dass sich das Pivotelement an seiner endgültigen Position befindet und alle kleineren Elemente davor stehen, während alle größeren danach kommen, zum Beispiel durch
funktion feld_aufteilen(links, rechts) {
pivotelement=feld[beliebiger_index_innerhalb_des_bereichs]; (z. B. (links+rechts)/2)
solange (links<rechts) {
solange (feld[links]<pivotelement und links<rechts)
links:=links+1;
solange (feld[rechts]>pivotelement und links<rechts)
rechts:=rechts-1;
vertausche feld[links] mit feld[rechts];
}
ergebniswert links; (oder rechts)
}
Beispiel
Es soll ein Array mit dem Inhalt [44 | 55 | 12 | 42 | 94 | 18 | 06 | 67] mittels QuickSort sortiert werden. Als Pivotelement (fett gedruckt) wird dabei immer das Element in der Mitte (abgerundet) des (Teil-)Arrays gewählt.
44 55 12 42 94 18 06 67 Element in der Mitte als Pivotelement auswählen
44 55 12 42 94 18 06 67 67 ist größer 42, also keine Änderung. Da 44 größer
und 06 kleiner als das Pivotelement, vertausche beide
06 55 12 42 94 18 44 67 55>42 und 18<55, also vertausche 18 und 55
06 18 12 (42) 94 55 44 67 Wähle 18 als Pivotelement für das linke
und 55 für das rechte Teilarray
06 18 12 (42) 94 55 44 67 12<18 und 18≥18; 44<55 und 94>55
06 12 (18 42 44 55) 94 67 Pivotelemente auswählen und ggf. tauschen
(06 12 18 42 44 55 67 94) Sortierte Menge
Varianten
Da QuickSort bei kurzen Listen relativ ineffizient ist, wird es oft so programmiert, dass ab einer bestimmten Kürze der Teillisten diese mit einem einfacheren Sortierverfahren, etwa BubbleSort, weitersortiert werden. Diese Variante wird IntroSort genannt.
weitere Sortierverfahren
- Shellsort
- Heapsort (siehe auch Heap)
- Mergesort
- Bubblesort
Literatur
- Robert Sedgewick: Algorithmen. Pearson Studium 2002 ISBN 3827370329
- Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Introduction to Algorithms (Second Edition), ISBN 0262032937 -- ein Standardwerk zu Algorithmen