Quicksort

Quicksort 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 seid 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.

QuickSort wählt ein Element aus der zu sortierenden Liste aus ("Pivotelement") und zerlegt die Liste in zwei Teillisten, von denen die eine alle Elemente enthält, die größer sind als das Pivotelement, die andere den Rest. Entsprechend werden auch die Teillisten zerlegt (Rekursion) und, sobald nur noch Listen mit einem Element vorhanden sind, wieder zusammengesetzt.

QuickSort liegt im worst case (schlimmsten Fall) in der Aufwandsklasse O(n²), im Mittel in der Aufwandsklasse O(n * log n).

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 Procedur 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 für ein Array mit dem Inhalt [44 55 12 42 94 18 06 67]

44 55 12 42 94 18 06 67  	Pivotelement auswählen und tauschen
         ^

06 18 12 (42) 94 55 44 67   Weitere Pivotelemente auswählen und tauschen
   ^             ^ 
06 12 (18 42 44 55) 94 67   Auswählen und ggf. tauschen
   ^                ^
(06 12 18 42 44 55 67 94)   Sortierte Menge