Quicksort

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 seitdem von vielen Forschern weiterentwickelt. 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 untere, die alle Elemente kleiner und eine obere, die alle Elemente gleich oder größer dem Pivotelement enthält. Dazu wird zunächst ein Element von unten gesucht, das größer (oder gleichgroß) 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 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 (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 von QuickSort benötigte Rechenzeit liegt im worst case in der Komplexitätsklasse O(n²), im Mittel aber in 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. Eine andere Möglichkeit ist die Verwendung des Medians von z.B. drei zufällig gewählten Elementen. Durch geschickte Wahl des Pivotelemntes kann man aber nur das mittlere schlechteste Verhalten verbessern. Vollständig verhindern kann man das Eintreten des Worst Cases jedoch nicht.

In der Praxis wird der Algorithmus trotz dem möglichen Auftreten des schlechtesten Falles verwendet. Er ist heute für ein breites Spektrum von praktischen Anwendungen die bevorzugte Sortiermethode, weil er schnell ist und, sofern Rekursion zur Verfügung steht, einfach zu implementieren ist. In vielen Standard-Bibliotheken ist er bereits vorhanden.

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. runde((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

Die Effizienz von QuickSort liegt darin, dass es Elemente aus großer Distanz miteinander vertauscht. Je kürzer die zu sortierende Liste wird, desto ineffizienter arbeitet QuickSort, da es sich einer Komplexität von O(n²) nähert. Die von QuickSort in Teillisten zerlegte Liste hat jedoch die Eigenschaft, dass der Abstand zwischen einem Element und seiner sortierten Position nach oben beschränkt ist. Eine solche Listen sortiert Insertionsort in linearer Zeit, so dass häufig in der Implementierung unterhalb einer definierten Teillistenlänge der QuickSort abgebrochen wird, um mit Insertionsort weiterzusortieren.

Siehe auch: IntroSort

weitere Sortierverfahren

siehe auch: Sortierverfahren

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

Weblinks