QuickSort (von engl. quick - schnell) ist ein schneller, rekursiver Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (engl. Divide and conquer) arbeitet. Er wurde 1960 von C. Antony R. Hoare in seiner Grundform entwickelt und seit dem von vielen Forschern weiter entwickelt. Er 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.
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 Element als das Pivotelement gesucht. Die beiden Elemente werden dann vertauscht und landen damit in der 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 (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.
Implementierung
Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus:
procedure quicksort(linke_grenze, rechte_grenze) {
if(rechte_grenze > 1) {
teilungsfeld = feld_aufteilen(linke_grenze, rechte_grenze);
quicksort(linke_grenze, teilungsfeld-1);
quicksort(teilungsfeld+1, rechte_grenze);
}
}
Die Prozedur 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.
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 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.