Quicksort

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.