Quicksort

Quicksort ⓘ
	Animierte Visualisierung des Quicksort-Algorithmus. Die horizontalen Linien sind Pivot-Werte.
Klasse	Sortieralgorithmus
Worst-Case-Leistung
Best-Case-Leistung	(einfache Partition); oder (Drei-Wege-Partition und gleiche Schlüssel)
Durchschnittliche Leistung
Schlechtester Fall: Raumkomplexität	Hilfsverfahren (naiv); Hilfsverfahren (Hoare 1962)

Quicksort ist ein Algorithmus zum Sortieren an Ort und Stelle. Er wurde 1959 von dem britischen Informatiker Tony Hoare entwickelt und 1961 veröffentlicht und ist immer noch ein häufig verwendeter Sortieralgorithmus. Wenn er gut implementiert ist, kann er etwas schneller sein als Merge Sort und etwa zwei- bis dreimal schneller als Heapsort. ⓘ

Quicksort ist ein Divide-and-Conquer-Algorithmus. Er funktioniert, indem er ein Pivot-Element aus dem Array auswählt und die anderen Elemente in zwei Unter-Arrays aufteilt, je nachdem, ob sie kleiner oder größer als das Pivot-Element sind. Aus diesem Grund wird er manchmal auch Partition-Exchange-Sort genannt. Die Sub-Arrays werden dann rekursiv sortiert. Dies kann an Ort und Stelle geschehen und erfordert nur einen geringen zusätzlichen Speicherbedarf für die Sortierung. ⓘ

Quicksort ist eine Vergleichssortierung, d. h. sie kann Elemente jedes Typs sortieren, für die eine "Weniger-als"-Relation (formell eine Gesamtreihenfolge) definiert ist. Effiziente Implementierungen von Quicksort sind keine stabile Sortierung, d. h. die relative Reihenfolge von Elementen gleicher Sortierung wird nicht beibehalten. ⓘ

Die mathematische Analyse von Quicksort zeigt, dass der Algorithmus im Durchschnitt $O(n\log {n})$ Vergleiche benötigt, um n Elemente zu sortieren. Im schlimmsten Fall macht er $O(n^{2})$ Vergleiche. ⓘ

Eine zufällige Permutation von Integerwerten wird mit Quicksort sortiert. Die blauen Linien zeigen den Wert des rot markierten Pivotelements im jeweiligen Rekursionsschritt. ⓘ

Quicksort (englisch quick ‚schnell‘ und to sort ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche arbeitet. Er wurde ca. 1960 von C. Antony R. Hoare in seiner Grundform entwickelt und seitdem von vielen Forschern verbessert. Der Algorithmus hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und dass er, abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack, ohne zusätzlichen Speicherplatz auskommt. ⓘ

Die Zahlen von 1 bis n in zufälliger Reihenfolge werden mit Quicksort sortiert. ⓘ

Geschichte

Der Quicksort-Algorithmus wurde 1959 von Tony Hoare entwickelt, als er Gaststudent an der Staatlichen Universität Moskau war. Zu dieser Zeit arbeitete Hoare an einem Projekt zur maschinellen Übersetzung für das National Physical Laboratory. Als Teil des Übersetzungsprozesses musste er die Wörter in russischen Sätzen sortieren, bevor er sie in einem russisch-englischen Wörterbuch nachschlagen konnte, das in alphabetischer Reihenfolge auf Magnetband gespeichert war. Nachdem er erkannt hatte, dass seine erste Idee, die Einfügesortierung, zu langsam sein würde, kam er auf eine neue Idee. Er schrieb den Partitionsteil in Mercury Autocode, hatte aber Schwierigkeiten, mit der Liste der unsortierten Segmente umzugehen. Als er nach England zurückkehrte, wurde er gebeten, den Code für Shellsort zu schreiben. Hoare erwähnte gegenüber seinem Chef, dass er einen schnelleren Algorithmus kenne, und sein Chef wettete um sechs Pence, dass er ihn nicht kenne. Sein Chef akzeptierte schließlich, dass er die Wette verloren hatte. Später lernte Hoare ALGOL und dessen Fähigkeit zur Rekursion kennen, was es ihm ermöglichte, den Code in Communications of the Association for Computing Machinery, der damals führenden Zeitschrift für Informatik, zu veröffentlichen. ⓘ

Quicksort fand weite Verbreitung und wurde zum Beispiel in Unix als Standard-Sortierunterprogramm der Bibliothek eingesetzt. Daher hat es auch der Unterroutine qsort in der C-Standardbibliothek und in der Referenzimplementierung von Java seinen Namen verliehen. ⓘ

Robert Sedgewicks Doktorarbeit aus dem Jahr 1975 gilt als Meilenstein in der Erforschung von Quicksort, in der er viele offene Probleme im Zusammenhang mit der Analyse verschiedener Pivot-Auswahlverfahren, einschließlich Samplesort, der adaptiven Partitionierung von Van Emden sowie der Ableitung der erwarteten Anzahl von Vergleichen und Vertauschungen löste. Jon Bentley und Doug McIlroy brachten verschiedene Verbesserungen zur Verwendung in Programmierbibliotheken ein, darunter eine Technik zur Behandlung gleicher Elemente und ein Pivot-Schema, das als Pseudomedian von neun bekannt ist, bei dem eine Stichprobe von neun Elementen in Dreiergruppen unterteilt und dann der Median der drei Mediane aus drei Gruppen gewählt wird. Bentley beschrieb in seinem Buch Programming Pearls ein anderes, einfacheres und kompakteres Partitionierungsschema, das er Nico Lomuto zuschrieb. Später schrieb Bentley, dass er Hoare's Version jahrelang verwendet, aber nie wirklich verstanden hat, aber Lomuto's Version war einfach genug, um sich als korrekt zu erweisen. Bentley beschrieb Quicksort in demselben Aufsatz als den "schönsten Code, den ich je geschrieben habe". Lomutos Partitionsschema wurde auch durch das Lehrbuch Introduction to Algorithms populär, obwohl es Hoares Schema unterlegen ist, da es im Durchschnitt dreimal mehr Vertauschungen vornimmt und auf $O(n 2)$ Laufzeit abfällt, wenn alle Elemente gleich sind. ⓘ

Im Jahr 2009 schlug Vladimir Yaroslavskiy eine neue Quicksort-Implementierung vor, bei der zwei Drehpunkte anstelle von einem verwendet werden. In den Mailinglisten der Java-Kernbibliothek stieß er eine Diskussion an, in der er behauptete, sein neuer Algorithmus sei der Sortiermethode der Laufzeitbibliothek überlegen, die zu diesem Zeitpunkt auf der weit verbreiteten und sorgfältig abgestimmten Variante des klassischen Quicksort von Bentley und McIlroy basierte. Yaroslavskijs Quicksort wurde nach umfangreichen empirischen Leistungstests als neuer Standardsortieralgorithmus in Oracles Java 7-Laufzeitbibliothek ausgewählt. ⓘ

Algorithmus

Vollständiges Beispiel einer Quicksortierung für eine zufällige Zahlenmenge. Das schattierte Element ist der Drehpunkt. Es wird immer als letztes Element der Partition gewählt. Allerdings führt die Wahl des letzten Elements in der Partition als Pivot auf diese Weise zu einer schlechten Leistung (

O (n 2)

) bei bereits sortierten Feldern oder Feldern mit identischen Elementen. Da gegen Ende einer Sortierprozedur auf einer großen Menge häufig Unterfelder mit sortierten/identischen Elementen auftauchen, laufen Versionen des Quicksort-Algorithmus, die den Pivot als mittleres Element wählen, viel schneller als der in diesem Diagramm beschriebene Algorithmus auf großen Mengen von Zahlen. ⓘ

Quicksort ist eine Art Divide-and-Conquer-Algorithmus zum Sortieren eines Arrays, der auf einer Partitionierungsroutine basiert; die Details dieser Partitionierung können etwas variieren, so dass Quicksort eigentlich eine Familie eng verwandter Algorithmen ist. Auf einen Bereich mit mindestens zwei Elementen angewandt, führt die Partitionierung zu einer Unterteilung in zwei aufeinanderfolgende, nicht leere Teilbereiche, so dass kein Element des ersten Teilbereichs größer ist als ein Element des zweiten Teilbereichs. Nach Anwendung dieser Partitionierung sortiert quicksort dann rekursiv die Teilbereiche, möglicherweise nach Ausschluss eines Elements am Teilungspunkt, von dem zu diesem Zeitpunkt bekannt ist, dass es sich bereits an seinem endgültigen Ort befindet. Aufgrund seiner rekursiven Natur muss quicksort (wie die Partitionsroutine) so formuliert werden, dass es für einen Bereich innerhalb eines größeren Arrays aufrufbar ist, auch wenn das letztendliche Ziel die Sortierung eines kompletten Arrays ist. Die Schritte für In-Place-Quicksort sind:

Wenn der Bereich weniger als zwei Elemente hat, ist sofort zurückzukehren, da es nichts zu tun gibt. Bei anderen sehr kurzen Längen wird möglicherweise eine spezielle Sortiermethode angewendet und der Rest dieser Schritte übersprungen.
Andernfalls wird ein Wert, der sogenannte Pivot, ausgewählt, der im Bereich vorkommt (die genaue Art der Auswahl hängt von der Partitionsroutine ab und kann zufällig sein).
Partitionieren Sie den Bereich: Ordnen Sie die Elemente neu an und bestimmen Sie dabei einen Teilungspunkt, so dass alle Elemente mit Werten kleiner als der Pivot-Wert vor der Teilung kommen, während alle Elemente mit Werten größer als der Pivot-Wert danach kommen; Elemente, die gleich dem Pivot-Wert sind, können in beide Richtungen gehen. Da mindestens eine Instanz des Pivots vorhanden ist, stellen die meisten Partitionsroutinen sicher, dass der Wert, der am Divisionspunkt endet, gleich dem Pivot ist und sich nun an seiner endgültigen Position befindet (die Beendigung der Quicksortierung hängt jedoch nicht davon ab, solange Teilbereiche erzeugt werden, die strikt kleiner als das Original sind).
Wenden Sie die Quicksortierung rekursiv auf den Teilbereich bis zum Teilungspunkt und auf den Teilbereich danach an, wobei Sie möglicherweise aus beiden Bereichen das Element ausschließen, das am Teilungspunkt gleich dem Drehpunkt ist. (Wenn die Partitionierung einen möglicherweise größeren Teilbereich in der Nähe der Grenze ergibt, von dem bekannt ist, dass alle Elemente gleich dem Drehpunkt sind, können auch diese ausgeschlossen werden). ⓘ

Die Wahl der Partitionsroutine (einschließlich der Pivot-Auswahl) und andere, oben nicht vollständig spezifizierte Details können die Leistung des Algorithmus beeinflussen, möglicherweise in hohem Maße für bestimmte Eingabe-Arrays. Bei der Erörterung der Effizienz von Quicksort ist es daher notwendig, zunächst diese Entscheidungen zu spezifizieren. Hier werden zwei spezifische Partitionsmethoden erwähnt. ⓘ

Lomuto-Partitionsschema

Dieses Schema wird Nico Lomuto zugeschrieben und von Bentley in seinem Buch Programming Pearls und Cormen et al. in ihrem Buch Introduction to Algorithms popularisiert. In den meisten Formulierungen wählt dieses Schema als Pivot das letzte Element im Array. Der Algorithmus behält den Index i bei, während er das Array mit einem anderen Index j so durchsucht, dass die Elemente an lo bis i-1 (einschließlich) kleiner als der Pivot sind und die Elemente an i bis j (einschließlich) gleich oder größer als der Pivot sind. Da dieses Schema kompakter und leichter zu verstehen ist, wird es häufig in Einführungsmaterialien verwendet, obwohl es weniger effizient ist als Hoares ursprüngliches Schema, z. B. wenn alle Elemente gleich sind. Dieses Schema verschlechtert sich auf $O(n 2)$ , wenn die Anordnung bereits in Ordnung ist. Es wurden verschiedene Varianten vorgeschlagen, um die Leistung zu steigern, einschließlich verschiedener Möglichkeiten, den Pivot zu wählen, mit gleichen Elementen umzugehen, andere Sortieralgorithmen zu verwenden, wie z. B. Insertion Sort für kleine Arrays und so weiter. In Pseudocode kann eine Quicksortierung, die Elemente an lo bis hi (einschließlich) eines Arrays A sortiert, wie folgt ausgedrückt werden:

// Sortiert ein (Teil eines) Arrays, unterteilt es in Partitionen und sortiert diese dann
Algorithmus quicksort(A, lo, hi) ist 
  // Sicherstellen, dass die Indizes in der richtigen Reihenfolge sind
  wenn lo >= hi || lo < 0 dann 
    return ⓘ

  // Partitionierung des Arrays und Ermittlung des Pivot-Index
  p := partition(A, lo, hi) ⓘ

  // Sortieren der beiden Partitionen
  quicksort(A, lo, p - 1) // Linke Seite des Pivots
  quicksort(A, p + 1, hi) // Rechte Seite des Pivots ⓘ

// Teilt Array in zwei Partitionen
Algorithmus partition(A, lo, hi) ist 
  Pivot := A[hi] // Wähle das letzte Element als Pivot ⓘ

  // Vorläufiger Pivot-Index
  i := lo - 1 ⓘ

  for j := lo to hi - 1 do 
    // Wenn das aktuelle Element kleiner oder gleich dem Pivot ist
    if A[j] <= Pivot then 
      // Verschiebe den temporären Pivot-Index nach vorne
      i := i + 1 ⓘ

      // Tausche das aktuelle Element mit dem Element am temporären Pivot-Index
      A[i] mit A[j] vertauschen 
  // Pivot-Element an die richtige Pivot-Position verschieben (zwischen dem kleineren und dem größeren Element)
  i := i + 1
  A[i] mit A[hi] vertauschen
  return i // der Pivot-Index ⓘ

Das Sortieren des gesamten Arrays wird durch quicksort(A, 0, length(A) - 1) erreicht. ⓘ

Hoare-Partitionsschema

Eine animierte Demonstration von Quicksort unter Verwendung des Hoare'schen Partitionsschemas. Die roten Umrisse zeigen die Positionen der linken und rechten Zeiger (i bzw. j), die schwarzen Umrisse die Positionen der sortierten Elemente und das gefüllte schwarze Quadrat den Wert, mit dem verglichen wird (Pivot).

Das ursprüngliche, von Tony Hoare beschriebene Partitionsschema verwendet zwei Zeiger (Indizes in den Bereich), die an beiden Enden des zu partitionierenden Arrays beginnen und sich dann aufeinander zu bewegen, bis sie eine Inversion erkennen: ein Paar von Elementen, von denen eines am ersten Zeiger größer als die Schranke (Hoares Bezeichnung für den Pivot-Wert) und eines am zweiten Zeiger kleiner als die Schranke ist; wenn an diesem Punkt der erste Zeiger immer noch vor dem zweiten liegt, befinden sich diese Elemente in der falschen Reihenfolge zueinander und werden dann ausgetauscht. Danach werden die Zeiger nach innen verschoben, und die Suche nach einer Inversion wird wiederholt; wenn sich die Zeiger schließlich kreuzen (der erste Zeiger liegt nach dem zweiten), wird kein Austausch vorgenommen; es wird eine gültige Partition gefunden, mit dem Teilungspunkt zwischen den gekreuzten Zeigern (alle Einträge, die streng zwischen den gekreuzten Zeigern liegen könnten, sind gleich dem Drehpunkt und können aus beiden gebildeten Teilbereichen ausgeschlossen werden). Bei dieser Formulierung ist es möglich, dass sich ein Teilbereich als der gesamte ursprüngliche Bereich entpuppt, was den Algorithmus am Weiterkommen hindern würde. Hoare legt daher fest, dass am Ende der Teilbereich, der das Pivot-Element enthält (das sich immer noch an seiner ursprünglichen Position befindet), durch Ausschluss dieses Pivots verkleinert werden kann, nachdem es (falls erforderlich) mit dem Teilbereichselement ausgetauscht wurde, das der Trennung am nächsten liegt; auf diese Weise wird die Beendigung der Quicksortierung sichergestellt. ⓘ

In Bezug auf diese ursprüngliche Beschreibung werden bei den Implementierungen oft geringfügige, aber wichtige Änderungen vorgenommen. Insbesondere schließt das unten dargestellte Schema Elemente, die gleich dem Pivot sind, in die Kandidaten für eine Inversion ein (daher werden "größer als" und "kleiner als" anstelle von "größer als" bzw. "kleiner als" verwendet; da die Formulierung "do...while" statt "repeat...until" verwendet, was sich in der Verwendung von strengen Vergleichsoperatoren widerspiegelt). Es gibt zwar keinen Grund, Elemente auszutauschen, die gleich der Grenze sind, aber diese Änderung erlaubt es, Tests an den Zeigern selbst wegzulassen, die sonst erforderlich sind, um sicherzustellen, dass sie nicht aus dem Bereich laufen. Da nämlich mindestens eine Instanz des Pivot-Wertes im Bereich vorhanden ist, kann die erste Weiterschaltung eines der beiden Zeiger diese Instanz nicht überschreiten, wenn ein inklusiver Test verwendet wird; sobald ein Austausch durchgeführt wird, sind diese ausgetauschten Elemente nun beide strikt vor dem Zeiger, der sie gefunden hat, und verhindern, dass dieser Zeiger ausläuft. (Letzteres gilt unabhängig von dem verwendeten Test, so dass es möglich wäre, den inklusiven Test nur bei der Suche nach der ersten Inversion zu verwenden. Die durchgängige Verwendung eines Inklusionstests stellt jedoch auch sicher, dass eine Teilung in der Nähe der Mitte gefunden wird, wenn alle Elemente im Bereich gleich sind, was einen wichtigen Effizienzgewinn beim Sortieren von Arrays mit vielen gleichen Elementen bedeutet). Das Risiko, eine nicht fortschreitende Trennung zu erzeugen, wird auf eine andere Weise als von Hoare beschrieben vermieden. Eine solche Trennung kann nur entstehen, wenn keine Invertierungen gefunden werden und beide Zeiger bei der ersten Iteration zum Pivot-Element vorrücken (sie gelten dann als gekreuzt, und es findet kein Austausch statt). Die zurückgegebene Teilung erfolgt nach der Endposition des zweiten Zeigers, so dass der zu vermeidende Fall darin besteht, dass der Drehpunkt das letzte Element des Bereichs ist und alle anderen Elemente kleiner sind als er. Daher muss bei der Wahl des Drehpunkts das letzte Element vermieden werden (in Hoares Beschreibung könnte dies jedes beliebige Element des Bereichs sein); dies geschieht hier durch Abrunden der mittleren Position unter Verwendung der Boden Funktion. Dies veranschaulicht, dass das Argument für die Korrektheit einer Implementierung des Hoare-Partitionsschemas sehr subtil sein kann, und es ist leicht, es falsch zu verstehen. ⓘ

In Pseudocode, ⓘ

// Sortiert ein (Teil eines) Arrays, teilt es in Partitionen und sortiert diese dann
Algorithmus quicksort(A, lo, hi) ist 
  if lo >= 0 && hi >= 0 && lo < hi then
    p := Partition(A, lo, hi) 
    quicksort(A, lo, p) // Hinweis: der Pivot ist jetzt enthalten
    quicksort(A, p + 1, hi) ⓘ

// Teilt das Feld in zwei Partitionen
Algorithmus partition(A, lo, hi) ist 
  // Pivot-Wert
  Drehpunkt := A[ floor((hi + lo) / 2) ] // Der Wert in der Mitte des Arrays ⓘ

  // Linker Index
  i := lo - 1 ⓘ

  // Rechter Index
  j := hi + 1 ⓘ

  Schleife für immer 
    // Bewege den linken Index mindestens einmal nach rechts und solange das Element an
    // dem linken Index kleiner als der Pivot ist
    do i := i + 1 while A[i] < Pivot ⓘ

    // Bewege den rechten Index mindestens einmal nach links und solange das Element an
    // dem rechten Index größer als der Pivot ist
    do j := j - 1 while A[j] > pivot ⓘ

    // Wenn sich die Indizes gekreuzt haben, return
    if i ≥ j then return j ⓘ

    // Tausche die Elemente am linken und rechten Index
    A[i] mit A[j] vertauschen ⓘ

Das gesamte Array wird mit quicksort(A, 0, length(A) - 1) sortiert. ⓘ

Hoare's Schema ist effizienter als Lomuto's Partitionsschema, da es im Durchschnitt dreimal weniger Swaps durchführt. Außerdem erzeugt die angegebene Implementierung, wie bereits erwähnt, eine ausgeglichene Partition, selbst wenn alle Werte gleich sind, was bei Lomutos Schema nicht der Fall ist. Wie Lomutos Partitionsschema würde auch Hoares Partitionierung dazu führen, dass Quicksort bei bereits sortierter Eingabe auf $O(n 2)$ degradiert, wenn der Pivot als erstes oder letztes Element gewählt wurde. Wird jedoch das mittlere Element als Pivot gewählt, ergeben sich sortierte Daten mit (fast) keinen Vertauschungen in gleich großen Partitionen, was zu einem Best-Case-Verhalten von Quicksort führt, d. h. $O(n log(n))$ . Wie andere Verfahren führt auch Hoare's Partitionierung nicht zu einer stabilen Sortierung. In diesem Schema ist die endgültige Position des Pivots nicht notwendigerweise der Index, der zurückgegeben wird, da der Pivot und Elemente, die dem Pivot gleich sind, nach einem Partitionsschritt überall innerhalb der Partition landen können und möglicherweise nicht sortiert werden, bis der Basisfall einer Partition mit einem einzelnen Element durch Rekursion erreicht wird. Die nächsten beiden Segmente, auf denen der Hauptalgorithmus rekursiert, sind (lo..p) (Elemente ≤ Pivot) und (p+1..hi) (Elemente ≥ Pivot), im Gegensatz zu (lo..p-1) und (p+1..hi) wie in Lomutos Schema. ⓘ

Nachfolgende Rekursionen (Erweiterung des vorherigen Absatzes) ⓘ

Erweitern wir die nächsten beiden Segmente, auf die der Hauptalgorithmus rekursiert, ein wenig. Da wir in den "do...while"-Schleifen strenge Komparatoren (>, <) verwenden, um zu verhindern, dass wir den Bereich verlassen, besteht die Möglichkeit, dass der Pivot selbst mit anderen Elementen in der Partitionsfunktion vertauscht wird. Daher ist der in der Partitionsfunktion zurückgegebene Index nicht unbedingt der Ort, an dem sich der tatsächliche Drehpunkt befindet. Nehmen wir das Beispiel [5, 2, 3, 1, 0]: Nach der ersten Partitionierung wird das Array zu [0, 2, 1, 3, 5], der zurückgegebene "Index" ist 2, also die Zahl 1, während der tatsächliche Drehpunkt, mit dem wir die Partitionierung begonnen haben, die Zahl 3 ist. Anhand dieses Beispiels sehen wir, wie notwendig es ist, den zurückgegebenen Index der Partitionsfunktion in unsere nachfolgenden Rekursionen einzubeziehen. Infolgedessen haben wir die Wahl, entweder auf (lo..p) und (p+1..hi) oder auf (lo..p - 1) und (p..hi) zu rekursieren. Welche der beiden Optionen wir wählen, hängt davon ab, welchen Index (i oder j) wir in der Partitionsfunktion zurückgeben, wenn sich die Indizes kreuzen, und wie wir unseren Pivot in der Partitionsfunktion wählen (floor vs. ceiling). ⓘ

Untersuchen wir zunächst die Wahl der Rekursion auf (lo..p) und (p+1..hi) anhand des Beispiels der Sortierung eines Arrays, in dem mehrere identische Elemente existieren [0, 0]. Wenn der Index i (der "letztere" Index) nach dem Kreuzen der Indizes in der Partitionsfunktion zurückgegeben wird, würde der Index 1 nach der ersten Partition zurückgegeben werden. Die anschließende Rekursion auf (lo..p) würde auf (0, 1) erfolgen, was genau demselben Array [0, 0] entspricht. Es entsteht eine nicht fortschreitende Trennung, die eine unendliche Rekursion verursacht. Da die linke Hälfte der Rekursion den zurückgegebenen Index enthält, ist es die Aufgabe der Partitionsfunktion, den "Schwanz" in nicht fortschreitenden Szenarien auszuschließen, wenn auf (lo..p) und (p+1..hi) rekursiert wird. Das heißt, dass der Index j (der "frühere" Index, wenn sich die Indizes kreuzen) anstelle von i zurückgegeben werden sollte. Mit einer ähnlichen Logik betrachtet man das Beispiel eines bereits sortierten Arrays [0, 1] und wählt als Pivot "floor", um sicherzustellen, dass die Zeiger auf dem "früheren" und nicht auf dem "späteren" stehen bleiben (mit "ceiling" als Pivot würde der Index 1 zurückgegeben und in (lo..p) eingeschlossen, was zu einer unendlichen Rekursion führen würde). Aus genau demselben Grund muss die Wahl des letzten Elements als Pivot vermieden werden. ⓘ

Die Wahl der Rekursion auf (lo..p - 1) und (p..hi) folgt genau der gleichen Logik wie oben. Da die rechte Hälfte der Rekursion den zurückgegebenen Index enthält, ist es die Aufgabe der Partitionsfunktion, den "Kopf" in nicht-fortschreitenden Szenarien auszuschließen. Der Index i (der "letzte" Index nach der Kreuzung der Indizes) in der Partitionsfunktion muss zurückgegeben werden, und "ceiling" muss als Pivot gewählt werden. Die beiden Nuancen werden wieder deutlich, wenn man die Beispiele für das Sortieren eines Arrays, in dem mehrere identische Elemente existieren ([0, 0]), und eines bereits sortierten Arrays [0, 1] betrachtet. Es sei darauf hingewiesen, dass bei der Version der Rekursion aus demselben Grund die Wahl des ersten Elements als Pivot vermieden werden muss. ⓘ

Probleme bei der Implementierung

Wahl des Pivots

In den sehr frühen Versionen von Quicksort wurde oft das ganz linke Element der Partition als Pivot-Element gewählt. Leider führt dies bei bereits sortierten Arrays zum Worst-Case-Verhalten, was ein recht häufiger Anwendungsfall ist. Das Problem konnte leicht gelöst werden, indem man entweder einen zufälligen Index für den Pivot wählte, den mittleren Index der Partition wählte oder (insbesondere bei längeren Partitionen) den Median des ersten, mittleren und letzten Elements der Partition als Pivot wählte (wie von Sedgewick empfohlen). Diese "Median-von-Drei"-Regel gilt für den Fall einer sortierten (oder umgekehrt sortierten) Eingabe und liefert eine bessere Schätzung des optimalen Drehpunkts (des wahren Medians) als die Auswahl eines einzelnen Elements, wenn keine Informationen über die Reihenfolge der Eingabe bekannt sind. ⓘ

Median-von-Drei-Codeausschnitt für die Lomuto-Partition:

mid := ⌊(lo + hi) / 2⌋
wenn A[mid] < A[lo]
    A[lo] mit A[mid] vertauschen
wenn A[hi] < A[lo]
    tausche A[lo] mit A[hi]
wenn A[mid] < A[hi]
    A[mid] mit A[hi] tauschen
pivot := A[hi]

Zuerst wird ein Median in A[hi] eingesetzt, dann wird dieser neue Wert von A[hi] als Pivot verwendet, wie in dem oben vorgestellten Grundalgorithmus. ⓘ

Die erwartete Anzahl der Vergleiche, die zum Sortieren von n Elementen (siehe § Analyse der randomisierten Quicksortierung) mit zufälliger Pivot-Auswahl benötigt werden, beträgt 1,386 n log n. Mit Median-of-three-Pivoting sinkt dieser Wert auf C_{n, 2} ≈ 1,188 n log n, allerdings auf Kosten einer um drei Prozent höheren erwarteten Anzahl von Vertauschungen. Eine noch stärkere Pivoting-Regel für größere Arrays ist die Wahl des ninther, ein rekursiver Median-of-three (Mo3), definiert als ⓘ

ninther(a) = median(Mo3(erstes 13 von a), Mo3(mittleres 13 von a), Mo3(letztes 13 von a)) ⓘ

Die Auswahl eines Pivotelements wird auch durch die Existenz eines ganzzahligen Überlaufs erschwert. Wenn die Randindizes des zu sortierenden Subarrays ausreichend groß sind, führt der naive Ausdruck für den mittleren Index, $(lo + hi)/2$ , zu einem Überlauf und liefert einen ungültigen Pivot-Index. Dies kann umgangen werden, indem man z. B. lo + (hi-lo)/2 zur Indizierung des mittleren Elements verwendet, allerdings auf Kosten einer komplexeren Arithmetik. Ähnliche Probleme treten bei einigen anderen Methoden zur Auswahl des Pivot-Elements auf. ⓘ

Wiederholte Elemente

Bei einem Partitionierungsalgorithmus wie dem oben beschriebenen Lomuto-Partitionierungsschema (selbst bei einem, der gute Pivot-Werte wählt) zeigt Quicksort eine schlechte Leistung bei Eingaben, die viele wiederholte Elemente enthalten. Das Problem wird deutlich, wenn alle Eingabeelemente gleich sind: Bei jeder Rekursion ist die linke Partition leer (keine Eingabewerte sind kleiner als der Pivot), und die rechte Partition hat sich nur um ein Element verringert (der Pivot wurde entfernt). Folglich benötigt das Lomuto-Partitionsschema quadratische Zeit für die Sortierung eines Feldes mit gleichen Werten. Bei einem Partitionierungsalgorithmus wie dem Hoare-Partitionierungsschema führen wiederholte Elemente jedoch im Allgemeinen zu einer besseren Partitionierung, und obwohl es zu unnötigen Vertauschungen von Elementen kommen kann, die gleich dem Pivot sind, nimmt die Laufzeit im Allgemeinen ab, wenn die Anzahl der wiederholten Elemente zunimmt (wobei der Cache-Speicher den Overhead der Vertauschung reduziert). Wenn alle Elemente gleich sind, tauscht das Hoare-Partitionsschema unnötigerweise Elemente aus, aber die Partitionierung selbst ist der beste Fall, wie im Abschnitt über die Hoare-Partition oben erwähnt. ⓘ

Zur Lösung des Lomuto-Partitionsschema-Problems (manchmal auch als niederländisches Nationalflaggen-Problem bezeichnet) kann eine alternative Partitionsroutine mit linearer Zeit verwendet werden, die die Werte in drei Gruppen unterteilt: Werte kleiner als der Drehpunkt, Werte gleich dem Drehpunkt und Werte größer als der Drehpunkt. (Bentley und McIlroy nennen dies eine "fette Partition", und sie wurde bereits in qsort der Version 7 von Unix implementiert.) Die Werte, die gleich dem Pivot sind, sind bereits sortiert, so dass nur die Partitionen "kleiner als" und "größer als" rekursiv sortiert werden müssen. In Pseudocode ausgedrückt, lautet der Algorithmus quicksort ⓘ

Algorithmus quicksort(A, lo, hi) ist
    wenn lo < hi dann
        p := Pivot(A, lo, hi)
        left, right := partition(A, p, lo, hi) // Hinweis: mehrere Rückgabewerte
        Quicksort(A, lo, left - 1)
        quicksort(A, rechts + 1, hi) ⓘ

Der Partitionsalgorithmus gibt die Indizes für das erste ("ganz links") und das letzte ("ganz rechts") Element der mittleren Partition zurück. Jedes Element der Partition ist gleich p und wird daher sortiert. Folglich müssen die Elemente der Partition nicht in den rekursiven Aufrufen von quicksort enthalten sein. ⓘ

Der beste Fall für den Algorithmus tritt nun ein, wenn alle Elemente gleich sind (oder aus einer kleinen Menge von $k ≪ n$ Elementen ausgewählt werden). Wenn alle Elemente gleich sind, führt das geänderte Quicksort nur zwei rekursive Aufrufe auf leeren Unterfeldern durch und ist somit in linearer Zeit fertig (vorausgesetzt, das Partitionsunterprogramm benötigt nicht länger als lineare Zeit). ⓘ

Optimierungen

Zwei weitere wichtige Optimierungen, die ebenfalls von Sedgewick vorgeschlagen und in der Praxis häufig verwendet werden, sind:

Um sicherzustellen, dass höchstens $O (log n)$ Platz verbraucht wird, rekursiv zuerst in die kleinere Seite der Partition, dann mit einem Tail-Aufruf in die andere Seite rekursiv, oder die Parameter so aktualisieren, dass die nun sortierte kleinere Seite nicht mehr enthalten ist, und iterativ die größere Seite sortieren.
Wenn die Anzahl der Elemente unter einem bestimmten Schwellenwert liegt (vielleicht zehn Elemente), wechseln Sie zu einem nicht rekursiven Sortieralgorithmus wie z. B. Insertion Sort, der weniger Vertauschungen, Vergleiche oder andere Operationen auf solch kleinen Arrays durchführt. Der ideale "Schwellenwert" hängt von den Details der jeweiligen Implementierung ab.
Eine ältere Variante der vorherigen Optimierung: Wenn die Anzahl der Elemente kleiner als der Schwellenwert k ist, wird einfach gestoppt; nachdem das gesamte Array verarbeitet wurde, wird eine Einfügesortierung durchgeführt. Wenn die Rekursion vorzeitig abgebrochen wird, bleibt das Feld k-sortiert, was bedeutet, dass jedes Element höchstens k Positionen von seiner endgültigen Sortierposition entfernt ist. In diesem Fall benötigt die Einfügesortierung $O(kn)$ Zeit, um die Sortierung abzuschließen, was linear ist, wenn k eine Konstante ist. Verglichen mit der Optimierung "viele kleine Sortierungen" führt diese Version zwar weniger Anweisungen aus, nutzt aber die Cache-Speicher moderner Computer suboptimal aus. ⓘ

Parallelisierung

Die "Divide-and-Conquer"-Formulierung von Quicksort ermöglicht eine Parallelisierung durch Task-Parallelität. Der Partitionierungsschritt wird durch die Verwendung eines parallelen Präfixsummen-Algorithmus erreicht, um einen Index für jedes Arrayelement in seinem Abschnitt des partitionierten Arrays zu berechnen. Bei einem Array der Größe n führt der Partitionierungsschritt $O(n)$ Arbeit in $O (log n)$ Zeit aus und erfordert $O(n)$ zusätzlichen Speicherplatz. Nachdem das Array partitioniert wurde, können die beiden Partitionen rekursiv parallel sortiert werden. Unter der Annahme einer idealen Wahl der Pivots, sortiert paralleles Quicksort ein Array der Größe n in $O(n log n)$ Arbeit in $O(log 2 n)$ Zeit und benötigt $O(n)$ zusätzlichen Platz. ⓘ

Quicksort hat im Vergleich zu alternativen Sortieralgorithmen, wie Merge Sort, einige Nachteile, die eine effiziente Parallelisierung erschweren. Die Tiefe des Divide-and-Conquer-Baums von Quicksort wirkt sich direkt auf die Skalierbarkeit des Algorithmus aus, und diese Tiefe ist in hohem Maße von der Wahl des Pivots durch den Algorithmus abhängig. Außerdem ist es schwierig, den Partitionierungsschritt effizient in-place zu parallelisieren. Die Verwendung von Scratch Space vereinfacht den Partitionierungsschritt, erhöht aber den Speicherbedarf des Algorithmus und die konstanten Overheads. ⓘ

Andere, ausgefeiltere parallele Sortieralgorithmen können sogar noch bessere Zeitgrenzen erreichen. So beschrieb David Powers 1991 eine parallelisierte Quicksortierung (und eine verwandte Radix-Sortierung), die in $O (log n)$ -Zeit auf einer CRCW (concurrent read and concurrent write) PRAM (Parallel Random Access Machine) mit n Prozessoren arbeiten kann, indem sie die Partitionierung implizit durchführt. ⓘ

Formale Analyse

Analyse des ungünstigsten Falles

Die unausgewogenste Partition tritt auf, wenn eine der von der Partitionierungsroutine zurückgegebenen Teillisten die Größe n - 1 hat. Dies kann der Fall sein, wenn der Pivot das kleinste oder größte Element der Liste ist, oder in einigen Implementierungen (z. B. dem oben beschriebenen Lomuto-Partitionsschema), wenn alle Elemente gleich sind. ⓘ

Wenn dies in jeder Partition wiederholt geschieht, dann wird bei jedem rekursiven Aufruf eine Liste verarbeitet, die um eins kleiner ist als die vorherige Liste. Folglich können wir n - 1 verschachtelte Aufrufe machen, bevor wir eine Liste der Größe 1 erreichen. Das bedeutet, dass der Aufrufbaum eine lineare Kette von n - 1 verschachtelten Aufrufen ist. Der i-te Aufruf macht O(n - i) Arbeit, um die Partitionierung durchzuführen, und $\textstyle \sum _{i=0}^{n}(n-i)=O(n^{2})$ so dass Quicksort in diesem Fall $O (n 2)$ Zeit benötigt. ⓘ

Best-Case-Analyse

Im ausgewogensten Fall wird die Liste bei jeder Partitionierung in zwei annähernd gleiche Teile geteilt. Das bedeutet, dass jeder rekursive Aufruf eine halb so große Liste verarbeitet. Folglich können wir nur $log 2 n$ verschachtelte Aufrufe machen, bevor wir eine Liste der Größe 1 erreichen. Das bedeutet, dass die Tiefe des Aufrufbaums $log 2 n$ beträgt. Aber keine zwei Aufrufe auf derselben Ebene des Aufrufbaums verarbeiten denselben Teil der ursprünglichen Liste; daher benötigt jede Ebene von Aufrufen insgesamt nur $O(n)$ Zeit (jeder Aufruf hat einen gewissen konstanten Overhead, aber da es nur $O(n)$ Aufrufe auf jeder Ebene gibt, wird dieser unter dem Faktor $O(n)$ subsumiert). Das Ergebnis ist, dass der Algorithmus nur $O(n log n)$ Zeit benötigt. ⓘ

Analyse des durchschnittlichen Falles

Um ein Array mit n verschiedenen Elementen zu sortieren, benötigt Quicksort erwartungsgemäß $O (n log n)$ Zeit, gemittelt über alle $n!$ Permutationen von n Elementen mit gleicher Wahrscheinlichkeit. Wir führen hier drei gängige Beweise für diese Behauptung auf, die unterschiedliche Einblicke in die Funktionsweise von Quicksort geben. ⓘ

Verwendung von Perzentilen

Wenn jeder Pivot einen Rang in der Mitte der 50 % hat, d. h. zwischen dem 25. und dem 75. Perzentil, dann teilt er die Elemente mit mindestens 25 % und höchstens 75 % auf jeder Seite. Wenn wir konsequent solche Pivots wählen könnten, müssten wir die Liste nur maximal $\log _{4/3}n$ geteilt werden, bevor man Listen der Größe 1 erreicht, was einen $O(n log n)$ -Algorithmus ergibt. ⓘ

Wenn die Eingabe eine zufällige Permutation ist, hat der Pivot einen zufälligen Rang, so dass nicht garantiert ist, dass er in den mittleren 50 Prozent liegt. Wenn wir jedoch von einer zufälligen Permutation ausgehen, hat der Pivot bei jedem rekursiven Aufruf einen zufälligen Rang in seiner Liste, so dass er etwa die Hälfte der Zeit in der Mitte der 50 Prozent liegt. Das ist gut genug. Stellen Sie sich vor, dass eine Münze geworfen wird: Kopf bedeutet, dass der Rang des Pivots in der Mitte der 50 Prozent liegt, Schwanz bedeutet, dass er es nicht tut. Stellen Sie sich nun vor, dass die Münze immer wieder geworfen wird, bis sie k Kopf ergibt. Obwohl dies sehr lange dauern kann, sind im Durchschnitt nur $2k$ Würfe erforderlich, und die Wahrscheinlichkeit, dass die Münze nach $100k$ Würfen nicht k Kopf ergibt, ist höchst unwahrscheinlich (dies kann mit Hilfe von Chernoff-Schranken rigoros nachgewiesen werden). Mit dem gleichen Argument endet die Rekursion von Quicksort im Durchschnitt bei einer Aufruftiefe von nur $2\log _{4/3}n$ . Wenn die durchschnittliche Aufruftiefe jedoch $O (log n)$ beträgt und jede Ebene des Aufrufbaums höchstens n Elemente verarbeitet, ist die gesamte im Durchschnitt geleistete Arbeit das Produkt $O (n log n)$ . Der Algorithmus muss nicht überprüfen, ob der Drehpunkt in der mittleren Hälfte liegt - wenn wir ihn in einem konstanten Bruchteil der Fälle treffen, reicht das für die gewünschte Komplexität aus. ⓘ

Verwendung von Rekursionen

Ein alternativer Ansatz besteht darin, eine Rekursionsrelation für den Faktor $T (n)$ aufzustellen, d. h. für die Zeit, die zum Sortieren einer Liste der Größe n benötigt wird. Im unausgewogensten Fall erfordert ein einziger Quicksort-Aufruf $O (n)$ Arbeit plus zwei rekursive Aufrufe auf Listen der Größe $0$ und n-1, so dass die Rekursionsrelation lautet ⓘ

T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1).

ⓘ

Dies ist die gleiche Beziehung wie für Insertion Sort und Selection Sort, und sie löst im schlimmsten Fall $T (n) = O (n 2)$ . ⓘ

Im ausgewogensten Fall erfordert ein einziger Quicksort-Aufruf $O (n)$ Arbeit plus zwei rekursive Aufrufe auf Listen der Größe $n/2$ , so dass die Rekursionsrelation lautet ⓘ

T(n)=O(n)+2T\left({\frac {n}{2}}\right).

ⓘ

Der Hauptsatz für Divide-and-Conquer-Rekurrenzen besagt, dass $T(n) = O (n log n)$ . ⓘ

Im Folgenden wird ein formaler Beweis für die erwartete Zeitkomplexität von $O (n log n)$ skizziert. Nehmen wir an, dass es keine Duplikate gibt, da Duplikate mit linearer Zeit für die Vor- und Nachbearbeitung behandelt werden können oder als Fälle betrachtet werden, die einfacher sind als die analysierten. Wenn die Eingabe eine zufällige Permutation ist, ist der Rang des Pivots gleichmäßig zufällig von 0 bis n - 1. Dann haben die resultierenden Teile der Partition die Größen i und n - i - 1, und i ist gleichmäßig zufällig von 0 bis n - 1. Wenn man also den Durchschnitt über alle möglichen Aufteilungen bildet und feststellt, dass die Anzahl der Vergleiche für die Partition n - 1 ist, kann die durchschnittliche Anzahl der Vergleiche über alle Permutationen der Eingabesequenz durch Lösen der Rekursionsbeziehung genau geschätzt werden:

C(n)=n-1+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(n-i-1))=n-1+{\frac {2}{n}}\sum _{i=0}^{n-1}C(i)

nC(n)=n(n-1)+2\sum _{i=0}^{n-1}C(i)

ⓘ

nC(n)-(n-1)C(n-1)=n(n-1)-(n-1)(n-2)+2C(n-1)

ⓘ

nC(n)=(n+1)C(n-1)+2n-2

ⓘ

{\begin{aligned}{\frac {C(n)}{n+1}}&={\frac {C(n-1)}{n}}+{\frac {2}{n+1}}-{\frac {2}{n(n+1)}}\leq {\frac {C(n-1)}{n}}+{\frac {2}{n+1}}\\&={\frac {C(n-2)}{n-1}}+{\frac {2}{n}}-{\frac {2}{(n-1)n}}+{\frac {2}{n+1}}\leq {\frac {C(n-2)}{n-1}}+{\frac {2}{n}}+{\frac {2}{n+1}}\\&\ \ \vdots \\&={\frac {C(1)}{2}}+\sum _{i=2}^{n}{\frac {2}{i+1}}\leq 2\sum _{i=1}^{n-1}{\frac {1}{i}}\approx 2\int _{1}^{n}{\frac {1}{x}}\mathrm {d} x=2\ln n\end{aligned}}

ⓘ

Die Lösung der Rekursionsrelation ergibt C(n) = 2n ln n ≈ 1,39n log₂ n. ⓘ

Das bedeutet, dass Quicksort im Durchschnitt nur etwa 39% schlechter abschneidet als im besten Fall. In diesem Sinne ist es näher am besten als am schlechtesten Fall. Eine Vergleichssortierung kann im Durchschnitt nicht weniger als $log 2 (n!)$ Vergleiche verwenden, um n Elemente zu sortieren (wie im Artikel Vergleichssortierung erläutert), und im Falle eines großen n ergibt die Näherung von Stirling log₂(n!) ≈ n(log₂ n - log₂ e), so dass Quicksort nicht viel schlechter ist als eine ideale Vergleichssortierung. Diese schnelle durchschnittliche Laufzeit ist ein weiterer Grund für die praktische Dominanz von quicksort gegenüber anderen Sortieralgorithmen. ⓘ

Verwendung eines binären Suchbaums

Der folgende binäre Suchbaum (BST) entspricht jeder Ausführung von Quicksort: Der anfängliche Pivot ist der Wurzelknoten; der Pivot der linken Hälfte ist die Wurzel des linken Teilbaums, der Pivot der rechten Hälfte ist die Wurzel des rechten Teilbaums usw. Die Anzahl der Vergleiche bei der Ausführung von Quicksort entspricht der Anzahl der Vergleiche bei der Konstruktion der BST durch eine Folge von Einfügungen. Die durchschnittliche Anzahl der Vergleiche für randomisiertes Quicksort ist also gleich den durchschnittlichen Kosten für die Konstruktion eines BST, wenn die eingefügten Werte $(x_{1},x_{2},\ldots ,x_{n})$ eine zufällige Permutation bilden. ⓘ

Betrachten wir eine BST, die durch Einfügen einer Folge von Werten $(x_{1},x_{2},\ldots ,x_{n})$ von Werten, die eine zufällige Permutation bilden. Bezeichnen wir mit $C$ die Kosten für die Erstellung des BST. Wir haben $C=\sum _{i}\sum _{j<i}c_{i,j}$ , wobei $c_{i,j}$ eine binäre Zufallsvariable ist, die angibt, ob während der Einfügung von $x_{i}$ ein Vergleich stattgefunden hat mit $x_{j}$ . ⓘ

Aufgrund der Linearität des Erwartungswertes ist der Erwartungswert $\operatorname {E} [C]$ von $C$ gleich $\operatorname {E} [C]=\sum _{i}\sum _{j<i}\Pr(c_{i,j})$ . ⓘ

Fix i und $j <i$ . Die Werte ${x_{1},x_{2},\ldots ,x_{j}}$ definieren, sobald sie sortiert sind, $j +1$ Intervalle. Die wichtigste strukturelle Beobachtung ist, dass $x_{i}$ verglichen wird mit $x_{j}$ im Algorithmus dann und nur dann verglichen wird, wenn $x_{i}$ in eines der beiden Intervalle fällt, die an $x_{j}$ . ⓘ

Beachten Sie, dass $(x_{1},x_{2},\ldots ,x_{n})$ eine zufällige Permutation ist, $(x_{1},x_{2},\ldots ,x_{j},x_{i})$ auch eine zufällige Permutation ist, also ist die Wahrscheinlichkeit, dass $x_{i}$ benachbart ist zu $x_{j}$ ist genau ${\frac {2}{j+1}}$ . ⓘ

Wir schließen mit einer kurzen Berechnung:

\operatorname {E} [C]=\sum _{i}\sum _{j<i}{\frac {2}{j+1}}=O\left(\sum _{i}\log i\right)=O(n\log n).

ⓘ

Raumkomplexität

Der Platzbedarf von quicksort hängt von der verwendeten Version ab. ⓘ

Die In-Place-Version von quicksort hat selbst im schlimmsten Fall eine Platzkomplexität von $O (log n)$ , wenn sie sorgfältig mit den folgenden Strategien implementiert wird. ⓘ

Es wird eine In-Place-Partitionierung verwendet. Diese instabile Partitionierung benötigt $O (1)$ Platz.
Nach der Partitionierung wird die Partition mit den wenigsten Elementen zuerst (rekursiv) sortiert, was höchstens $O(log n)$ Platz benötigt. Dann wird die andere Partition mittels Tail-Rekursion oder Iteration sortiert, was den Aufrufstapel nicht vergrößert. Diese Idee wurde, wie oben erwähnt, von R. Sedgewick beschrieben und hält die Stapeltiefe auf $O(log n)$ begrenzt. ⓘ

Quicksort mit In-Place- und Instable-Partitionierung verbraucht nur konstanten zusätzlichen Speicherplatz, bevor ein rekursiver Aufruf erfolgt. Quicksort muss für jeden verschachtelten rekursiven Aufruf eine konstante Menge an Informationen speichern. Da im besten Fall höchstens $O(log n)$ verschachtelte rekursive Aufrufe erfolgen, wird $O(log n)$ Platz benötigt. Ohne Sedgewicks Trick zur Begrenzung der rekursiven Aufrufe könnte Quicksort jedoch im schlimmsten Fall $O(n)$ verschachtelte rekursive Aufrufe machen und $O(n)$ zusätzlichen Platz benötigen. ⓘ

Vom Standpunkt der Bitkomplexität aus gesehen, verbrauchen Variablen wie lo und hi keinen konstanten Platz; es braucht $O(log n)$ Bits, um in eine Liste von n Elementen zu indizieren. Da es solche Variablen in jedem Stackframe gibt, benötigt die Quicksortierung mit Sedgewicks Trick $O((log n) 2)$ Bits Platz. Dieser Platzbedarf ist allerdings nicht allzu schlimm, denn wenn die Liste eindeutige Elemente enthielte, würde sie mindestens $O(n log n)$ Bits Platz benötigen. ⓘ

Eine andere, weniger verbreitete Version von Quicksort, die nicht an Ort und Stelle ausgeführt wird, benötigt $O(n)$ Platz für den Arbeitsspeicher und kann eine stabile Sortierung implementieren. Der Arbeitsspeicher ermöglicht es, das Eingabefeld auf einfache Weise stabil zu partitionieren und dann für aufeinanderfolgende rekursive Aufrufe zurück in das Eingabefeld zu kopieren. Die Optimierung von Sedgewick ist immer noch angemessen. ⓘ

Beziehung zu anderen Algorithmen

Quicksort ist eine platzoptimierte Version der binären Baumsortierung. Anstatt Elemente nacheinander in einen expliziten Baum einzufügen, werden sie bei Quicksort gleichzeitig in einem Baum organisiert, der durch die rekursiven Aufrufe impliziert wird. Die Algorithmen führen genau die gleichen Vergleiche durch, allerdings in einer anderen Reihenfolge. Eine oft erwünschte Eigenschaft eines Sortieralgorithmus ist die Stabilität - d. h. die Reihenfolge der Elemente, die gleich verglichen werden, wird nicht geändert, wodurch die Reihenfolge von Tabellen mit mehreren Schlüsseln (z. B. Verzeichnis- oder Ordnerlisten) auf natürliche Weise gesteuert werden kann. Diese Eigenschaft ist bei der In-Situ- (oder In-Place-) Quicksortierung (die nur konstanten zusätzlichen Speicherplatz für Zeiger und Puffer und $O(log n)$ zusätzlichen Speicherplatz für die Verwaltung expliziter oder impliziter Rekursionen benötigt) schwer zu erhalten. Bei abweichenden Quicksortierungen, die aufgrund von Darstellungen mit Zeigern (z. B. Listen oder Bäume) oder Dateien (effektiv Listen) zusätzlichen Speicherplatz benötigen, ist es trivial, die Stabilität zu erhalten. Komplexere oder plattengebundene Datenstrukturen erhöhen tendenziell die Zeitkosten, da sie im Allgemeinen immer mehr virtuellen Speicher oder Platten nutzen. ⓘ

Der direkteste Konkurrent von Quicksort ist Heapsort. Die Laufzeit von Heapsort ist $O(n log n)$ , aber die durchschnittliche Laufzeit von Heapsort wird in der Regel als langsamer als In-Place-Quicksort angesehen. Dieses Ergebnis ist umstritten; in einigen Veröffentlichungen wird das Gegenteil behauptet. Introsort ist eine Variante von Quicksort, die auf Heapsort umschaltet, wenn ein ungünstiger Fall erkannt wird, um die Worst-Case-Laufzeit von Quicksort zu vermeiden. ⓘ

Quicksort konkurriert auch mit Mergesort, einem weiteren $O(n log n)$ -Sortieralgorithmus. Mergesort ist ein stabiler Sortieralgorithmus, im Gegensatz zu den Standard-In-Place-Quicksort- und Heapsort-Algorithmen, und hat eine ausgezeichnete Worst-Case-Leistung. Der Hauptnachteil von Mergesort besteht darin, dass effiziente Implementierungen bei der Bearbeitung von Arrays $O(n)$ -Hilfsraum benötigen, während die Variante von Quicksort mit In-Place-Partitionierung und Tail-Rekursion nur $O(log n)$ -Platz benötigt. ⓘ

Mergesort funktioniert sehr gut auf verknüpften Listen und benötigt nur eine kleine, konstante Menge an Hilfsspeicher. Obwohl Quicksort als stabile Sortierung mit verknüpften Listen implementiert werden kann, leidet es oft unter schlechten Pivot-Entscheidungen ohne zufälligen Zugriff. Mergesort ist auch der Algorithmus der Wahl für die externe Sortierung sehr großer Datensätze, die auf langsam zugänglichen Medien wie Festplattenspeicher oder Netzwerkspeicher gespeichert sind. ⓘ

Bucket Sort mit zwei Buckets ist Quicksort sehr ähnlich; der Pivot ist in diesem Fall effektiv der Wert in der Mitte des Wertebereichs, der bei gleichmäßig verteilten Eingaben im Durchschnitt gut funktioniert. ⓘ

Auswahlbasierte Pivotierung

Ein Auswahlalgorithmus wählt die k-te kleinste Zahl aus einer Liste von Zahlen aus; dies ist im Allgemeinen ein einfacheres Problem als das Sortieren. Ein einfacher, aber effektiver Auswahlalgorithmus funktioniert fast genauso wie Quicksort und ist dementsprechend als Quickselect bekannt. Der Unterschied besteht darin, dass er statt rekursiver Aufrufe auf beiden Teillisten nur einen einzigen tail-rekursiven Aufruf auf der Teilliste macht, die das gewünschte Element enthält. Durch diese Änderung wird die durchschnittliche Komplexität auf lineare oder $O(n)$ -Zeit gesenkt, was für die Auswahl optimal ist, aber der Auswahlalgorithmus ist im schlimmsten Fall immer noch $O(n 2)$ . ⓘ

Eine Variante von quickselect, der Algorithmus Median der Mediane, wählt die Pivots sorgfältiger aus und stellt sicher, dass die Pivots in der Nähe der Mitte der Daten liegen (zwischen dem 30. und 70. Perzentil), wodurch eine lineare Zeit - $O(n)$ - garantiert wird. Dieselbe Pivot-Strategie kann verwendet werden, um eine Variante der Quicksortierung (Median der Mediane Quicksortierung) mit $O(n log n)$ Zeit zu konstruieren. Der Aufwand für die Auswahl des Pivots ist jedoch beträchtlich, so dass dies in der Praxis im Allgemeinen nicht verwendet wird. ⓘ

Abstrakter ausgedrückt, kann man einen $O(n)$ -Auswahlalgorithmus verwenden, um den idealen Pivot (den Median) bei jedem Schritt von Quicksort zu finden und so einen Sortieralgorithmus mit $O(n log n)$ -Zeit zu erzeugen. Praktische Implementierungen dieser Variante sind im Durchschnitt deutlich langsamer, aber sie sind von theoretischem Interesse, weil sie zeigen, dass ein optimaler Auswahlalgorithmus einen optimalen Sortieralgorithmus ergeben kann. ⓘ

Varianten

Multi-Pivot-Quicksort

Anstatt mit einem einzigen Pivot in zwei Unterfelder zu partitionieren, partitioniert Multi-Pivot-Quicksort (auch Multiquicksort) seine Eingabe mit s - 1 Pivots in eine Anzahl s von Unterfeldern. Der Fall mit zwei Pivots ( $s = 3$ ) wurde von Sedgewick und anderen bereits Mitte der 1970er Jahre untersucht, doch waren die daraus resultierenden Algorithmen in der Praxis nicht schneller als das "klassische" Quicksort. Eine 1999 durchgeführte Bewertung eines Multi-Quicksort-Algorithmus mit einer variablen Anzahl von Pivots, der auf eine effiziente Nutzung der Prozessor-Caches abgestimmt ist, ergab, dass sich die Anzahl der Anweisungen um etwa 20 % erhöht, aber die Simulationsergebnisse deuten darauf hin, dass er bei sehr großen Eingaben effizienter ist. Eine 2009 von Yaroslavskiy entwickelte Version von Dual-Pivot-Quicksort erwies sich als schnell genug, um die Implementierung in Java 7 als Standardalgorithmus zum Sortieren von Arrays von Primitiven zu rechtfertigen (das Sortieren von Arrays von Objekten erfolgt mit Timsort). Der Leistungsvorteil dieses Algorithmus wurde später festgestellt, dass er hauptsächlich mit der Cache-Leistung zusammenhängt, und experimentelle Ergebnisse deuten darauf hin, dass die Drei-Pivot-Variante auf modernen Maschinen sogar noch besser abschneiden könnte. ⓘ

Externe Quicksortierung

Für Festplattendateien ist eine externe Sortierung möglich, die auf einer Partitionierung ähnlich wie Quicksort basiert. Sie ist langsamer als die externe Mischsortierung, benötigt aber keinen zusätzlichen Speicherplatz. Es werden 4 Puffer verwendet, 2 für die Eingabe und 2 für die Ausgabe. N = Anzahl der Datensätze in der Datei, B = Anzahl der Datensätze pro Puffer und M = N/B = Anzahl der Puffersegmente in der Datei. Die Daten werden von beiden Enden der Datei nach innen gelesen (und geschrieben). X steht dabei für die Segmente, die am Anfang der Datei beginnen, und Y für die Segmente, die am Ende der Datei beginnen. Die Daten werden in die Lesepuffer X und Y eingelesen. Es wird ein Pivot-Datensatz ausgewählt, und die Datensätze in den X- und Y-Puffern außer dem Pivot-Datensatz werden in aufsteigender Reihenfolge in den X-Schreibpuffer und in absteigender Reihenfolge in den Y-Schreibpuffer kopiert, wobei ein Vergleich mit dem Pivot-Datensatz erfolgt. Sobald einer der beiden X- oder Y-Puffer gefüllt ist, wird er in die Datei geschrieben, und der nächste X- oder Y-Puffer wird aus der Datei gelesen. Der Prozess wird fortgesetzt, bis alle Segmente gelesen sind und ein Schreibpuffer übrig bleibt. Handelt es sich bei diesem Puffer um einen X-Schreibpuffer, wird der Pivot-Datensatz an ihn angehängt und der X-Puffer geschrieben. Handelt es sich bei diesem Puffer um einen Y-Schreibpuffer, wird der Pivot-Datensatz an den Y-Puffer angehängt und der Y-Puffer geschrieben. Dies stellt einen Partitionsschritt der Datei dar, und die Datei besteht nun aus zwei Unterdateien. Die Start- und Endpositionen jeder Unterdatei werden über eine Rekursion auf einen eigenständigen Stack oder den Hauptstack geschoben/gepoppt. Um den Stapelplatz auf O(log2(n)) zu begrenzen, wird die kleinere Unterdatei zuerst verarbeitet. Bei einem eigenständigen Stack werden die Parameter der größeren Subdatei auf den Stack geschoben und die kleinere Subdatei iteriert. Bei einer Rekursion wird zuerst auf der kleineren Unterdatei rekursiert, dann wird die größere Unterdatei verarbeitet. Sobald eine Teildatei kleiner oder gleich 4 B-Datensätze ist, wird die Teildatei an Ort und Stelle mittels Quicksort sortiert und geschrieben. Diese Teildatei ist nun sortiert und in der Datei vorhanden. Der Prozess wird fortgesetzt, bis alle Teildateien sortiert und an ihrem Platz sind. Die durchschnittliche Anzahl der Durchläufe für die Datei beträgt etwa 1 + ln(N+1)/(4 B), im schlimmsten Fall sind es N Durchläufe (entspricht O(n^2) für die interne Sortierung im schlimmsten Fall). ⓘ

Dreifache Radix-Quicksortierung

Dieser Algorithmus ist eine Kombination aus Radixsortierung und Quicksortierung. Wählen Sie ein Element aus dem Array (den Drehpunkt) und betrachten Sie das erste Zeichen (Schlüssel) der Zeichenfolge (Multikey). Teilen Sie die verbleibenden Elemente in drei Gruppen auf: diejenigen, deren entsprechendes Zeichen kleiner, gleich oder größer als das Zeichen des Pivots ist. Rekursive Sortierung der Partitionen "kleiner als" und "größer als" nach demselben Zeichen. Rekursive Sortierung der Partition "gleich" nach dem nächsten Zeichen (Schlüssel). Unter der Voraussetzung, dass wir mit Bytes oder Wörtern der Länge $W$ Bits sortieren, ist der beste Fall $O (KN)$ und der schlechteste Fall $O (2K N)$ oder mindestens $O (N 2)$ wie bei der Standard-Quicksortierung, vorausgesetzt für eindeutige Schlüssel $N <2K$ , und K ist eine versteckte Konstante in allen Standard-Vergleichssortieralgorithmen einschließlich Quicksortierung. Es handelt sich um eine Art Drei-Wege-Quicksort, bei der die mittlere Partition eine (trivialerweise) sortierte Teilreihe von Elementen darstellt, die genau gleich dem Pivot sind. ⓘ

Schnelle Radixsortierung

Ebenfalls von Powers als $O(K)$ -paralleler PRAM-Algorithmus entwickelt. Auch hier handelt es sich um eine Kombination aus Radixsortierung und Quicksortierung, wobei die Entscheidung über die linke/rechte Partitionierung auf der Grundlage aufeinanderfolgender Bits des Schlüssels getroffen wird und somit $O(KN)$ für $N$ K-Bit-Schlüssel beträgt. Alle Vergleichssortieralgorithmen setzen implizit das transdichotome Modell mit K in $Θ (log N)$ voraus, denn wenn K kleiner ist, können wir in $O(N)$ -Zeit mit einer Hash-Tabelle oder Ganzzahlensortierung sortieren. Wenn $K ≫ log N$ ist, aber die Elemente innerhalb von $O(log N)$ Bits eindeutig sind, werden die verbleibenden Bits weder von Quicksort noch von Quick Radix Sort betrachtet. Andernfalls haben alle Vergleichssortieralgorithmen den gleichen Aufwand, $O(K)$ relativ nutzlose Bits zu durchsuchen, aber Quick-Radix-Sort vermeidet das $O(N 2)$ -Verhalten von Standard-Quicksort und Radix-Quicksort im schlimmsten Fall und ist selbst im besten Fall dieser Vergleichsalgorithmen unter diesen Bedingungen von $Uniqueprefix(K) ≫ log N$ schneller. Siehe Powers für eine weitere Erörterung der versteckten Overheads bei Vergleichs-, Radix- und Parallelsortierung. ⓘ

BlockQuicksort

Bei jedem vergleichsbasierten Sortieralgorithmus erfordert die Minimierung der Anzahl der Vergleiche eine Maximierung der aus jedem Vergleich gewonnenen Informationen, was bedeutet, dass die Vergleichsergebnisse unvorhersehbar sind. Dies führt zu häufigen Verzweigungsfehlprognosen, was die Leistung einschränkt. BlockQuicksort ordnet die Berechnungen von Quicksort neu an, um unvorhersehbare Verzweigungen in Datenabhängigkeiten umzuwandeln. Bei der Partitionierung wird die Eingabe in Blöcke mittlerer Größe unterteilt (die leicht in den Daten-Cache passen), und zwei Arrays werden mit den Positionen der zu vertauschenden Elemente gefüllt. (Um bedingte Verzweigungen zu vermeiden, wird die Position bedingungslos am Ende des Arrays gespeichert, und der Index des Endes wird inkrementiert, wenn eine Vertauschung erforderlich ist.) In einem zweiten Durchlauf werden die Elemente an den in den Arrays angegebenen Positionen ausgetauscht. Beide Schleifen haben nur eine bedingte Verzweigung, einen Test auf Abbruch, der normalerweise durchgeführt wird. ⓘ

Partielle und inkrementelle Quicksortierung

Es gibt mehrere Varianten von Quicksort, die die k kleinsten oder größten Elemente vom Rest der Eingabe trennen. ⓘ

Verallgemeinerung

Richard Cole und David C. Kandathil entdeckten 2004 eine Ein-Parameter-Familie von Sortieralgorithmen, die so genannten Partitionssortierungen, die im Durchschnitt (bei gleicher Wahrscheinlichkeit aller Eingabearrangements) höchstens $n\log n+{O}(n)$ Vergleiche (nahe der informationstheoretischen Untergrenze) und ${\Theta }(n\log n)$ Operationen durchführen; im schlechtesten Fall führen sie ${\Theta }(n\log ^{2}n)$ Vergleiche (und auch Operationen); diese werden an Ort und Stelle durchgeführt und erfordern nur zusätzlichen ${O}(\log n)$ Platz. Praktische Effizienz und geringere Varianz in der Leistung wurden gegenüber optimierten Quicksorts (von Sedgewick und Bentley-McIlroy) nachgewiesen. ⓘ

Beispiele

Vollständiges Beispiel für alphabetische Sortierung

In diesem Beispiel soll der Quicksortalgorithmus die Buchstabenfolge „Quicksort“ sortieren. Zunächst wird das rechte Element P-> als Pivotelement definiert. Dann laufen die Zähler g für „größer“ von links nach rechts und k für „kleiner“ von rechts nach links los, ⓘ

 Quicksort
^       ^^
g       kP ⓘ

bis g auf ein Element trifft, welches größer als das Pivotelement ist und bis k auf ein Element trifft, welches kleiner oder gleich dem Pivotelement ist. ⓘ

 Quicksort
  ^     ^^
  g     kP ⓘ

Diese beiden gefundenen Elemente r und u werden dann im folgenden Schritt getauscht. ⓘ

 Qricksout
  ^     ^^
  g     kP ⓘ

Im folgenden Schritt laufen die Indizes k und g in der gleichen Richtung wie gehabt weiter und suchen Elemente, die bei k kleiner als oder gleich dem Pivotelement und bei g größer als das Pivotelement sind. ⓘ

 Qricksout
       ^^^
       kgP ⓘ

Jetzt sind k und g aneinander vorbeigelaufen. Dieses Ereignis ist eine Abbruchbedingung. Jetzt wird das Pivotelement mit dem durch g indizierten Element getauscht. ⓘ

 Qricksotu
       ^^^
       kPg ⓘ

Jetzt treffen folgende zwei Aussagen zu: „Links des Pivotelements sind alle Elemente kleiner oder gleich dem Pivotelement. Rechts des Pivotelements sind alle Elemente größer oder gleich dem Pivotelement.“ ⓘ

   links|:|rechts
 Qrickso|t|u
       ^|^|^
       k|P|g ⓘ

Das Pivotelement „teilt“ nun die Datenmenge an der Stelle des Pivotelements in zwei Hälften Links und Rechts. Nun muss der Algorithmus den linken und den rechten Teil auf die gleiche Weise wie im Vorangehenden schon geschehen weiterbehandeln. Hierdurch ergibt sich nun die Rekursion. Der rechte Teil (Der Buchstabe u) ist nur ein einzelnes Element und ist somit per Definition sortiert. Also wird nun der linke Teil behandelt. Das rechte Element ist wieder das Pivotelement, und die Zähler werden passend gesetzt. ⓘ

 Qrickso|t|u
^     ^^
g     kP ⓘ

Das Q ist größer als o und das k ist kleiner als das o. ⓘ

 Qrickso|t|u
 ^   ^ ^
 g   k P ⓘ

Also werden das Q und das k vertauscht. ⓘ

 kricQso|t|u
 ^   ^ ^
 g   k P ⓘ

Indizes g und k laufen weiter... ⓘ

 kricQso|t|u
  ^ ^  ^
  g k  P ⓘ

Das r und das c werden getauscht. ⓘ

 kcirQso|t|u
  ^ ^  ^
  g k  P ⓘ

Im folgenden Schritt sind die Indizes wieder aneinander vorbeigelaufen... ⓘ

 kcirQso|t|u
   ^^  ^
   kg P ⓘ

… und das Pivotelement (Buchstabe o) wird mit dem größeren Element (Buchstabe r) getauscht. ⓘ

 kcioQsr|t|u
   ^^  ^
   kP  g ⓘ

Nun ergibt sich erneut ein linker und ein rechter Teil. ⓘ

links:rechts
 kci|o|Qsr  |t|u
   ^|^|  ^  | |
   k|P|  g  | | ⓘ

Zunächst wird der linke Teil behandelt. ⓘ

 kci|o| Qsr|t|u
^ ^^| |^ ^^| |
g kP| |g kP| | ⓘ

 cki|o| Qsr|t|u
 ^^^| |^ ^^| |
 gkP| |g kP| | ⓘ

Buchstabe c und k werden getauscht. ⓘ

 cki|o| Qsr|t|u
 ^^^| |^ ^^| |
 kgP| |g kP| | ⓘ

Indizes sind aneinander vorbeigelaufen, und das Element des Index g wird mit dem des Index P vertauscht. ⓘ

 cik|o| Qsr|t|u
 ^^^| |^ ^^| |
 kPg| |g kP| | ⓘ

Der jetzt entstandene neue linke und rechte Teil besteht nun nur noch aus einem einzelnen Element und gilt als sortiert. ⓘ

 cik|o| Qsr|t|u
    | | ^^^| |
    | | kgP| | ⓘ

Im ehemals rechten Teil (Buchstaben Qsr) laufen die Indizes direkt aneinander vorbei, und das Element bei g wird mit dem Pivotelement getauscht. ⓘ

 cik|o| Qrs|t|u
    | | ^^^| |
    | | kPg| | ⓘ

Damit sind alle Zeichen sortiert. ⓘ

 cik|o| Qrs|t|u ⓘ

Ergebnis:

 cikoQrstu ⓘ

Varianten

QuickSort für verkettete Listen

Bei nachfolgend dargestellter QuickSort-Variante für verkettete Listen wird als Pivotelement das jeweils erste der zu teilenden Folge gewählt. Ein Zeiger Zeiger2 wird soweit vorgeschoben, bis er auf ein Element trifft, das kleiner als das Pivot ist. Die Elemente, über die Zeiger2 hinweggegangen ist, sind demzufolge größer oder gleich dem Pivot. Ein Tausch des ersten dieser größeren Elemente mit dem bei Zeiger2 sorgt also dafür, dass die betreffenden Elemente im richtigen Teilabschnitt landen. Zeiger1 markiert das aktuelle Ende des Teilabschnitts der Elemente, die kleiner als das Pivot sind. Wenn Zeiger2 am rechten Rand der zu teilenden Folge angelangt ist, wird abschließend das Pivotelement an die richtige Position zwischen den Teilfolgen getauscht. ⓘ

// Links, Rechts sind hier Zeiger
QuickSort(Links, Rechts):
  falls Links<>Rechts dann
    // Initialisierung der (lokalen) Zeiger
    // Zeiger0 wird nur als Vorgänger von Zeiger1 benötigt
    Zeiger0 := Links
    Zeiger1 := Links
    Zeiger2 := Links ⓘ

    Pivot := Links.Zahl ⓘ

    wiederhole
      Zeiger2 := Zeiger2.Nachfolger; ⓘ

      falls Zeiger2.Zahl<Pivot dann
        Zeiger0 := Zeiger1;
        Zeiger1 := Zeiger1.Nachfolger;
        tausche(Zeiger1, Zeiger2)
    solange bis Zeiger2 = Rechts; ⓘ

    tausche(Links,Zeiger1); ⓘ

    falls Zeiger1<>Rechts dann
      Zeiger1 := Zeiger1.Nachfolger; ⓘ

    QuickSort(Links, Zeiger0);
    QuickSort(Zeiger1, Rechts);
ende ⓘ

Der Nachteil dieses Verfahrens liegt darin, dass eine weitgehend sortierte Folge oder viele gleichartige Schlüsselwerte zu einem Worst-Case-ähnlichen Verhalten führen. Daher wählt man für verkettete Listen gern Sortieralgorithmen wie etwa Mergesort, die auch im Worst Case eine Zeitkomplexität von ${\mathcal {O}}(n\log(n))$ besitzen. Andere dynamische Datenstrukturen wie balancierte Bäume (z. B. B-Bäume, AVL-Bäume) verteilen die Kosten des Sortierens auf die Einfügeoperationen, so dass nachträgliches Sortieren nicht notwendig ist. ⓘ

Iteratives Quicksort

Quicksort kann auch nicht-rekursiv mit Hilfe eines kleinen Stack oder Array implementiert werden. Hier eine einfache Variante mit zufälliger Auswahl des Pivotelements:

funktion quicksort_iterativ(links, rechts)
   zufall := random() // zufälliger Startwert
   wiederhole // äußere Schleife
      solange links < rechts wiederhole
         pivot := daten[random(links, rechts)] // Auswahl eines zufälligen Elements, das zwischen links und rechts liegt
         push(rechts) // rechten Teil später sortieren
         mitte := links
         wiederhole // innere Schleife, teile Feld
            solange daten[mitte] < pivot wiederhole // suche falsch einsortiertes Element von links
               mitte := mitte + 1
            ende
            solange daten[rechts] > pivot wiederhole // suche falsch einsortiertes Element von rechts
               rechts := rechts - 1
            ende
            falls mitte >= rechts dann Abbruch innere Schleife
            tausche daten[mitte] mit daten[rechts]
         ende // Feld geteilt, linken Teil weitersortieren
      ende
      falls stapel leer dann Abbruch äußere Schleife // noch ein rechter Teil übrig?
      links := rechts + 1
      pop(rechts) // jetzt rechten Teil sortieren
   ende
ende ⓘ

Die Anweisung push legt dabei ein Element auf den Stack wo es mit pop wieder geholt wird. Die zufällige Wahl des Pivotelements sorgt dabei mit hoher Wahrscheinlichkeit für einen Average-Case. Die Größe des nötigen Stapelspeichers ist dabei mit ausreichender Sicherheit kleiner als 2·log₂(n). Falls ein begrenzter Stapel trotzdem überläuft, so kann zum Sortieren des noch verbleibenden Teils einfach von vorne begonnen werden. ⓘ

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 ${\mathcal {O}}(n^{2})$ 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 Liste sortiert Insertionsort in linearer Zeit, so dass häufig in der Implementierung unterhalb einer definierten Teillistenlänge der Quicksort abgebrochen wird, um mit Insertionsort weiter zu sortieren. ⓘ

QuickSort in funktionalen Sprachen

In funktionalen Sprachen wie Haskell oder Erlang lässt sich QuickSort aufgrund mächtigerer Listenverarbeitung sehr einfach implementieren:

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (e:es) = quicksort [x | x <- es, x <= e] ++ [e] ++ quicksort [x | x <- es, x > e] <span title="Aus: Deutsche Wikipedia, Abschnitt &quot;QuickSort in funktionalen Sprachen&quot;" class="plainlinks">[https://de.wikipedia.org/wiki/Quicksort#QuickSort_in_funktionalen_Sprachen <span style="color:#dddddd">ⓘ</span>]</span>

Dabei ist ++ der Verkettungsoperator für Listen; das Pattern (e:es) isoliert das erste Element der Liste und [x | x <- es, x <= e] ergibt alle Elemente der Liste es, die kleiner sind als das Pivotelement e. ⓘ

Parallel Quicksort

Wenn mehrere Prozessoren/-kerne zur Verfügung stehen, ist es auch möglich Quicksort zu parallelisieren. Damit sind unter Umständen bessere Laufzeiten erreichbar. ⓘ