Beim QuickSort legt man die ganze Arbeit in die Zerlegung. Man wählt ein beliebiges Element (z. B. das erste) und teilt die Liste in drei Teile: die kleineren Elemente, die gleichen Elemente, die größeren Elemente. Wenn diese drei Teillisten selbst sortiert worden sind, kann man sie einfach zum Ergebnis konkatenieren. Die Zerlegung geschieht mithilfe des Filter-Funktionals. [FUNPROG]

QuickSort gehört zur Klasse der Divide-and-Conquer-Algorithmen. [INFO2002]

Wenn die Zerlegung jedes Mal so klappt, dass die Teillisten der kleinen und der großen Elemente ungefähr gleich lang sind, hat dieser Algorithmus einen Aufwand in der Größenordnung O(N log N). Das ist aber nur der durchschnittliche Aufwand. Im worst case, also wenn die Zerlegung jedes Mal sehr unausgewogen erfolgt, ist der Aufwand quadratisch.

In der Praxis ist der QuickSort der effizienteste aller bekannten Sortieralgorithmen. [FUNPROG]

Stellen Sie sich einfach mal vor, Sie hätten in einem Europa-Gewinnspiel einen großen Haufen von Euro- und Centmünzen gewonnen. Sie möchten selbstverständlich wissen, wie viel dieser Münzhaufen wert ist, und beginnen zunächst, den gesamten Münzhaufen in mehrere Haufen aufzuteilen — die 1-Cent-Münzen ganz links, die 2-Cent-Münzen etwas rechts davon, die 5-Cent-Münzen auf einen weiteren Haufen rechts davon usw., um eben später jeden einzelnen Haufen einfacher abrechnen zu können.

Der Einfachheit halber sei stets das linke Element das Pivotelement.
Aus Effizienzgründen soll ein glatter (siehe unten oder MoneyQuickSort) QuickSort vorliegen.
Notation: Aus [pivot, ...] wird [kleinere]#pivots#[größere]

• Sei nun [5,8,4,7,8,2,1,9,2,8,3,6,8,9] die zu sortierende Liste.
  • [5,8,4,7,8,2,1,9,2,8,3,6,8,9]
  • [4,2,1,2,3]#5#[8,7,8,9,8,6,8,9]
  • [2,1,2,3]#4#[]#5#[7,6]#8,8,8,8#[9,9]
  • [1]#2,2#[3]#4#[]#5#[6]#7#[]#8,8,8,8#[]#9,9#[]
• Sei nun [1,2,3,3,3,4,5,6,7,8,9] die zu sortierende Liste.
  • [1,2,3,3,3,4,5,6,7,8,9]
  • []#1#[2,3,3,3,4,5,6,7,8,9]
  • []#1#[]#2#[3,3,3,4,5,6,7,8,9]
  • []#1#[]#2#[]#3,3,3#[4,5,6,7,8,9]
  • []#1#[]#2#[]#3,3,3#[]#4#[5,6,7,8,9]
  • []#1#[]#2#[]#3,3,3#[]#4#[]#5#[6,7,8,9]
  • []#1#[]#2#[]#3,3,3#[]#4#[]#5#[]#6#[7,8,9]
  • []#1#[]#2#[]#3,3,3#[]#4#[]#5#[]#6#[]#7#[8,9]
  • []#1#[]#2#[]#3,3,3#[]#4#[]#5#[]#6#[]#7#[]#8#[9]
  Wenn bei einer vorsortierten Liste stets das linke Element als Pivotelement ausgezeichnet wird, dann kommt es zum schlechtesten Laufzeitverhalten — es handelt sich hierbei um den sogenannten worst case.
• Sei nun [9,1,8,2,3,7,3,4,5,6,3] die zu sortierende Liste.
  • [9,1,8,2,3,7,3,4,5,6,3]
  • [1,8,2,3,7,3,4,5,6,3]#9#[]
  • []#1#[8,2,3,7,3,4,5,6,3]#9#[]
  • []#1#[2,3,7,3,4,5,6,3]#8#[]#9#[]
  • []#1#[]#2#[3,7,3,4,5,6,3]#8#[]#9#[]
  • []#1#[]#2#[]#3,3,3#[7,4,5,6]#8#[]#9#[]
  • []#1#[]#2#[]#3,3,3#[4,5,6]#7#[]#8#[]#9#[]
  • []#1#[]#2#[]#3,3,3#[]#4#[5,6]#7#[]#8#[]#9#[]
  • []#1#[]#2#[]#3,3,3#[]#4#[]#5#[6]#7#[]#8#[]#9#[]
  Alle Pivotelemente sind hier unglücklicherweise Extrema der jeweiligen Teilliste, was ebenfalls zum schlechtesten Laufzeitverhalten führt.
  
  Bei unsortierten Listen kann der schlechteste Fall nicht ausgeschlossen werden.

Folgender SML-Code implementiert den QuickSort streng nach Definition — der QuickSort in Reinkultur! Zudem besitzt speziell dieser SML-QuickSort folgende Eigenschaften:

• Glattheit
  Beispielsweise werden Listen mit gleichwertigen Elementen in O(n) Schritten sortiert.
  Die Rekursion käme praktisch nicht zustande, weil schon im ersten (Rekursions-) Aufruf alle Elemente der zu sortierenden Liste in die mittlere Liste medium aufgenommen werden würden, die beiden anderen Listen small und large hingegen leer blieben.
• Stabilität
  Die Reihenfolge gleichwertiger Elemente wird stets aufrechterhalten (siehe Filter-Funktion).
  
  Dabei ist aber der QuickSort als nicht stabiler Sortieralgorithmus bekannt. Man spricht allerdings indirekt von der „In-Placement-Version” des QuickSort. Diese SML-Implementierung zeigt einen stabilen QuickSort!

Mehr zu diesen Eigenschaften finden Sie unter Sortieren.


Aus dieser Implementierung geht deutlich hervor, dass der QuickSort ein Divide-and-Conquer - Algorithmus ist und mit einer kaskadenartigen bzw. baumartigen Rekursion realisiert werden muss. Diese Rekursion erinnert stark an eine Inorder-Traversion eines binären Baumes. Deshalb spricht man auch häufig davon, dass der QuickSort eine Baumstruktur aufbaut. Der einzelne Knoten des Binärbaumes wäre demnach 3-teilig:

1. Links (hier: quicksort small)
   Der Verweis auf einen weiteren Knoten des Baumes bzw. auf die sortierte Teilliste aller kleineren Elemente bzgl. des Pivotelements.
2. Mitte (hier: medium)
   Die Liste aller Elemente, die dem Pivotelement gleichwertig sind, inklusive des Pivotelements selbst.
   Dieser Mitte verdankt man übrigens ein deutlich besseres Laufzeitverhalten, wenn Listen mit verhältnismäßig vielen gleichwertigen Elementen sortiert werden (Glattheit).
3. Rechts (hier: quicksort large)
   Der Verweis auf einen weiteren Knoten des Baumes bzw. auf die sortierte Teilliste aller größeren Elemente bzgl. des Pivotelements.

Die Prolog-Implementierung des QuickSort ist der vorhergehenden SML-Implementierung sehr ähnlich, nur dass dieser Algorithmus die Glattheit nicht berücksichtigt, weil hier die zu sortierende Liste nur in zwei kleinere Listen aufgeteilt wird. Die mittlere Liste gibt es in diesem Beispiel nicht, sie besteht praktisch nur aus dem Pivotelement selbst.

Der Schreibaufwand mit Haskell ist deutlich kleiner als bei der entsprechenden Prolog-Implementierung. Auch hier wird die Glattheit nicht berücksichtigt. Die Elemente, die dem Pivotelement p gleichen, werden mit den Elementen vermengt, welche größer (g) als das Pivotelement sind.

Möglicherweise gibt es keine andere Sprache, in der der QuickSort noch kürzer implementiert werden kann.

Im Folgenden wird der QuickSort als In-Placement-Sortierverfahren implementiert, was einen höheren und komplizierten Programmieraufwand zur Folge hat. Um die Ordnung einer Teilliste bzgl. des Pivotelements herzustellen, benötigt man lediglich so viel Speicherplatz, wie die kaskadenartige Rekursion an Stack benötigt. Um in-place sortieren zu können, geht man meist zwei Kompromisse ein:

• Verlust der Glattheit!
  Man teilt die Liste bei jedem Rekursionsschritt nur noch in zwei Teile: Die Elemente, die dem Pivotelement gleichwertig sind, werden je nach Art der Implementierung in die linke bzw. in die rechte Teilliste geswappt; die mittlere Liste besteht praktisch nur noch aus einem einzigen Element, dem Pivotelement selbst.
  Aus diesem Grunde werden selbst die Elemente, die dem Pivotelement gleichwertig sind, nochmals (überflüssigerweise) in den folgenden Rekursionsschritten betrachtet, bis diese selbst zu Pivotelementen werden oder bis der triviale Fall (Terminierung) eintritt.
• Verlust der Stabilität!
  Elemente, die dem Pivotelement gleichwertig sind, werden genauso wie die anderen Elemente behandelt. Durch das permanente Vertauschen der Elemente innerhalb der zu sortierenden Liste kann die Reihenfolge gleichwertiger Elemente nicht mehr nachvollzogen werden.

Wie ein In-Placement-QuickSort zu einem glatten Sortierverfahren modifiziert werden kann, wird beispielsweise recht ausführlich in [ALGODAT S. 96f] beschrieben.
Jedoch geht die Stabilität beim In-Placement-QuickSort für immer verloren. Bei Wunsch nach Stabilität sollte man auf andere stabile Sortierverfahren zurückgreifen, wie zum Beispiel auf eine stabile Implementierung des HeapSort.

Da in der hier gezeigten Delphi-Implementierung des QuickSort stets das mittlere Element einer Teilliste als Pivotelement ausgezeichnet wird, entsteht eine unnötige Geschwindigkeitsbremse, nämlich die Berechnung der Indexposition des Pivots: (LoIndex + HiIndex) div 2. Wählt man stets das mittlere Element als Pivotelement, geht man einer Worst-Case-Laufzeitkomplexität nicht aus dem Wege (siehe oben, das dritte konkrete Zahlenbeispiel), schlimmer noch: Der QuickSort büßt an Effizienz ein, wo doch gerade die Effizienz die Stärke des QuickSort darstellen sollte.

Im folgenden Code-Beispiel in C++ wird stets das am weitesten rechts liegende Randelement als Pivotelement ausgezeichnet — es besteht kein besonderer Anlass mehr, das Pivotelement teuer zu ermitteln.

Dies soll aber nicht bedeuten, dass C++ schneller ist als Delphi, sondern nur, dass das folgende Beispiel einen effizienteren Algorithmus implementiert (algorithmusabhängig, nicht programmiersprachenabhängig).

Dank Christian Weßel kann ich Ihnen auch einen QuickSort in Perl präsentieren, sehen Sie selbst!

Selbst ein glatter QuickSort ist in ungünstigen Fällen nicht schnell und kann sogar — wenn auch nur selten — langsamer als ein BubbleSort oder ShakerSort sein.

Bei einem Rekursionsschritt des QuickSort liegt ein ungünstiger Fall vor, wenn das Pivotelement ein Element einer verhältnismäßig kleinen Menge der größten und kleinsten Elemente der jeweiligen Teilliste ist.

Würde man beispielsweise das kleinste Element (Minimum) einer Teilliste als Pivotelement nehmen, so würde im folgenden Rekursionsschritt das Problem „Sortiere Liste der Länge n” nur auf das Problem „Sortiere Liste der Länge n-1” reduziert werden. Fiele nun die Wahl in jedem Rekursionsschritt auf das kleinste Element der jeweiligen Teilliste, dann würde der worst case mit einer Abschätzung von O(n*n) die Folge sein — der Algorithmus degeneriert.
Die Analogie zu SelectionSort wäre somit hergestellt, nur mit dem Unterschied, dass der SelectionSort in n-1 Schritten das Minimum sucht, während der QuickSort nach der Wahl des Pivotelements (hier: zufällig ein Minimum) die übrigen n-1 Elemente mit diesem vergleicht. Die Komplexität wäre in beiden Fällen gleich schlecht (quadratisch).

Der obige SML-QuickSort z. B. wählt stets das linke Grenzelement als Pivotelement. Müsste man also mit diesem SML-QuickSort eine vorsortierte Liste sortieren, hätte man genau den ungünstigsten Fall mit einer Laufzeitabschätzung von O(n*n).
Der worst case kann aber auch bei obiger Delphi-Prozedur, welche immer das mittlere Element der Teilliste als Pivotelement wählt, auftreten. Dabei müssen aber die Elemente (zufälligerweise) dementsprechend ungünstig angeordnet vorliegen (Pivotelement sei stets ein Extremum der jeweiligen Teilliste). Allerdings treten — statistisch gesehen — derartig ungünstige Anordnungen seltener auf als zum Beispiel teilweise vorsortierte Listen.

Mit den QuickSort-Varianten möchte man vorwiegend durch bessere Wahl des Pivotelements das Auftreten der quadratischen Laufzeit O(n*n) weitestgehend ausschließen.

Es gibt zwei nennenswerte QuickSort-Varianten, deren modifiziertes Verfahren zur Bestimmung des Pivotelements nicht wesentlich die Effizienz des QuickSort mindert:

1. Zufallsvariante
2. 3-Median-Variante

Eine andere Variante des QuickSort, welche IntroSort genannt wird und im schlechtesten Falle die Laufzeitabschätzung O(n log n) garantiert, behilft sich im für den QuickSort ungünstigen Falle anderer, jedoch weniger effizienter Sortierverfahren mit einer Laufzeitabschätzung von O(n log n).
Schlimmstenfalls kommt der QuickSort überhaupt nicht zum Zuge, weshalb diese Variante eher nur als Mogelpackung angesehen werden kann.

Es ist offenbar nicht sehr effizient, die Rekursion bis zum bitteren Ende fortzusetzen. Deshalb kann man sich ernsthaft überlegen, Teillisten der Länge 3 ohne Anwendung von Rekursion zu sortieren (vorzeitige Terminierung). Zudem würde auch der Bedarf an Stackspeicher gemindert werden.

QuickSort wurde um 1960 von dem berühmten britischen Informatiker C. A. R. Hoare entwickelt. Damals waren noch keine schnellen Sortieralgorithmen bekannt, und man versuchte daher, die einfachen Sortierverfahren durch raffinierte Programmiertricks zu beschleunigen. Hoare demonstrierte, dass es, wie auch in vielen anderen Fällen, sinnvoller ist, nach besseren Algorithmen zu suchen, als vorhandene Algorithmen durch trickreiche Programmierung zu beschleunigen.

Besonders bemerkenswert ist in diesem Zusammenhang, dass QuickSort ein rekursiver Algorithmus ist, was in den Frühzeiten der Informatik als ineffizient galt. [INFO2002]