Schnelle Sorte

Schnelle Sorte

Animierte Visualisierung des Quicksort -Algorithmus. Die horizontalen Linien sind Drehwerte.
Klasse	Sortieren von Algorithmus
Schlimmsten Fall Leistung	${\ displayStyle o (n^{2})}$
I'm besten fall Leistung	${\ displayStyle o (n \ log n)}$ (einfache Partition) oder ${\ displayStyle o (n)}$ (Drei-Wege-Trennwand und gleiche Schlüssel)
Durchschnitt Leistung	${\ displayStyle o (n \ log n)}$
Schlimmsten Fall Raumkomplexität	${\ displayStyle o (n)}$ Auxiliary (naiv) ${\ displayStyle o (\ log n)}$ Auxiliary (Hoare 1962)

Schnelle Sorte ist ein an Ort und Stelle Sortieren von Algorithmus. Entwickelt von britischer Informatiker Tony Hoare 1959^[1] und 1961 veröffentlicht,^[2] Es ist immer noch ein häufig verwendeter Algorithmus zum Sortieren. Wenn es gut implementiert wird, kann es etwas schneller sein als Zusammenführen, sortieren und ungefähr zwei- oder dreimal schneller als Haufen.^{[3][widersprüchlich]}

Quicksort ist a Divide-and-Conquer-Algorithmus. Es funktioniert, indem es ein "Pivot" -Element aus dem Array auswählt und die anderen Elemente in zwei Sub-Arrays aufteilt, sodass sie weniger oder größer sind als der Drehzahl. Aus diesem Grund wird es manchmal genannt Partition-Austausch-Sortierung.^[4] Die Sub-Arrays werden dann sortiert rekursiv. Das kann gemacht werden an Ort und Stelle, die kleine zusätzliche Mengen von benötigen Erinnerung Um die Sortierung durchzuführen.

Quicksort ist a Vergleichsart, was bedeutet, dass es Elemente jeglicher Art sortieren kann, für die eine "weniger als" Beziehung (formell, a Gesamtbestellung) ist definiert. Effiziente Implementierungen von Quicksort sind keine stabile Sorte, was bedeutet, dass die relative Reihenfolge gleicher Sortierelemente nicht erhalten bleibt.

Mathematische Analyse von Quicksort zeigt das, im DurchschnittDer Algorithmus nimmt ${\ displayStyle o (n \ log {n})}$ Vergleiche mit Sortieren n Artikel. In dem schlimmsten Fall, es macht ${\ displayStyle o (n^{2})}$ Vergleiche.

Geschichte

Der Quicksort -Algorithmus wurde 1959 von entwickelt Tony Hoare Während er ein Gaststudent bei war Moskauer Staatsuniversität. Zu dieser Zeit arbeitete Hoare an einem Maschinenübersetzung Projekt für die Nationales physisches Labor. Als Teil des Übersetzungsprozesses musste er die Wörter in russischen Sätzen sortieren, bevor er sie in einem russisch-englischen Wörterbuch nachging, das in alphabetischer Reihenfolge war Magnetband.^[5] Nachdem er diese erste Idee erkannt hat, Sortieren durch Einfügen, wäre langsam, er hatte eine neue Idee. Er schrieb den Partitionsteil im Quecksilber Autocode hatte aber Probleme, sich mit der Liste der unsortierten Segmente zu befassen. Bei der Rückkehr nach England wurde er gebeten, Code zu schreiben Shellsort. Hoare erwähnte seinem Chef, dass er von einem schnelleren Algorithmus und seinem Chef wete Sixpence dass er es nicht tat. Sein Chef akzeptierte schließlich, dass er die Wette verloren hatte. Später lernte Hoare von Algol und seine Fähigkeit, eine Überholung durchzuführen, die es ihm ermöglichte, den Code in zu veröffentlichen Kommunikation des Vereins für Computermaschinen, das erstklassige Informatikjournal der Zeit.^[2][6]

Quicksort erhielt eine weit verbreitete Akzeptanz und erschien beispielsweise in Unix Als Standardbibliothek sortieren Sie Unterprogramme. Daher verlieh es dem Namen dem Namen C Standardbibliothek Subroutine QSORT^[7] und in der Referenzimplementierung von Java.

Robert SedgebickDie Doktorarbeit im Jahr 1975 wird als Meilenstein in der Untersuchung von Quicksort angesehen, bei dem er viele offene Probleme in Bezug Probenort, adaptive Aufteilung von Van Emden^[8] sowie Ableitung der erwarteten Anzahl von Vergleiche und Swaps.^[7] Jon Bentley und Doug McIlroy Integrierte verschiedene Verbesserungen für die Verwendung in Programmierbibliotheken, einschließlich einer Technik, um mit gleichen Elementen und einem Pivot -Schema zu handeln, das als bekannt ist Pseudomedian von neun, Wenn eine Stichprobe von neun Elementen in Gruppen von drei unterteilt ist und dann der Median der drei Mediane aus drei Gruppen ausgewählt wird.^[7] Bentley beschrieb ein anderes einfacheres und kompaktes Partitionierungsschema in seinem Buch Programmierperlen programmieren dass er Nico Lomuto zugeschrieben hat. Später schrieb Bentley, dass er Hoares Version jahrelang benutzte, es aber nie wirklich verstanden habe, aber Lomutos Version war einfach genug, um sich als richtig zu erweisen.^[9] Bentley beschrieb Quicksort als den "schönsten Code, den ich jemals geschrieben hatte" im selben Aufsatz. Lomutos Partitionsschema wurde auch vom Lehrbuch populär gemacht Einführung in Algorithmen Obwohl es Hoares Schema unterlegen ist, weil es im Durchschnitt dreimal mehr Swaps macht und sich verschlechtert O(n²) Laufzeit, wenn alle Elemente gleich sind.^{[10][Selbstveröffentlichte Quelle?]}

Im Jahr 2009 schlug Vladimir Yaroslavskiy eine neue Quicksort -Implementierung mit zwei Pivots anstelle von einem vor.^[11] In den Mailing -Listen der Java Core Library leitete er eine Diskussion ein, in der er behauptete, sein neuer Algorithmus sei der Sortiermethode der Laufzeitbibliothek überlegen, die zu dieser Zeit auf der weit verbreiteten und sorgfältig abgestimmten Variante von Classic Quicksort von Bentley und McIlroy beruhte.^[12] Yaroslavskiys Quicksort wurde als neuer Standardsortieralgorithmus in der Java 7 -Laufzeitbibliothek von Oracle ausgewählt^[13] nach umfangreichen empirischen Leistungstests.^[14]

Algorithmus

Vollständiges Beispiel für Quicksort auf einem zufälligen Satz von Zahlen. Das schattierte Element ist der Drehpunkt. Es wird immer als das letzte Element der Partition ausgewählt. Die Auswahl des letzten Elements in der Partition als Drehzahl auf diese Weise führt jedoch zu einer schlechten Leistung (O(n²)) an bereits sortiert Arrays oder Arrays identischer Elemente. Seit Sub-Arrays sortierter / identischer Elemente gegen Ende eines Sortierverfahrens auf einem großen Satz viel auftauchen große Zahlensätze.

Quicksort ist eine Art von Art von Algorithmus teilen und erobern zum Sortieren eines Arrays basierend auf einer Partitionierungsroutine; Die Details dieser Partitionierung können etwas variieren, so dass Quicksort wirklich eine Familie eng verwandter Algorithmen ist. Die Partitionierung wird auf eine Reihe von mindestens zwei Elementen angewendet und erzeugt eine Teilung in zwei aufeinanderfolgende nicht leere Unterbereitungen, so dass kein Element des ersten Unterbereichs größer ist als jedes Element des zweiten Unterbereichs. Nach der Anwendung dieser Partition sortiert Quicksort dann die Teilbereiche rekursiv, möglicherweise nach dem Ausschluss eines Elements am Punkt der Division, von dem an diesem Punkt bekannt ist, von dem bekannt ist, dass er sich bereits an seinem endgültigen Standort befindet. Aufgrund seiner rekursiven Natur muss Quicksort (wie die Partitionsroutine) so formuliert werden, dass für einen Bereich innerhalb eines größeren Arrays abgerufen werden kann, auch wenn das ultimative Ziel darin besteht, ein vollständiges Array zu sortieren. Die Schritte für an Ort und Stelle Quicksort sind:

1. Wenn der Bereich weniger als zwei Elemente hat, kehren Sie sofort zurück, da nichts zu tun ist. Möglicherweise wird für andere sehr kurze Längen eine Sortiermethode für Spezialpurien angewendet und der Rest dieser Schritte übersprungen.
2. Wählen Sie sonst einen Wert aus, der a genannt wird Drehzahl, dies tritt im Bereich auf (die genaue Art der Wahl hängt von der Partitionsroutine ab und kann Zufälligkeit beinhalten).
3. Trennwand Der Bereich: Stellen Sie seine Elemente neu an, während ein Punkt der Teilung festgelegt wird, so dass alle Elemente mit weniger als der Drehpunkt vor der Teilung vorhanden sind, während alle Elemente mit Werten, die größer als der Drehpunkt sind, danach kommen; Elemente, die dem Drehpunkt entsprechen, können in beide Richtungen gehen. Da mindestens eine Instanz des Drehzweihs vorhanden ist, stellen die meisten Partitionsroutinen sicher, dass der Wert, der am Punkt der Teilung landet Solange Unterbereiche streng kleiner als das Original erzeugt werden).
4. Rekursiv Wenden Sie die Quicksort auf den Unterbereich bis zum Punkt der Division und auf den Unterbereich an, möglicherweise ohne Ausnahme des Elements, das dem Drehpunkt am Punkt der Teilung entspricht. (Wenn die Partition in der Nähe der Grenze einen möglicherweise größeren Unterbereich erzeugt, in dem alle Elemente gleich dem Drehpunkt sind, können diese ebenfalls ausgeschlossen werden.)

Die Auswahl der Partitionroutine (einschließlich der Pivot -Auswahl) und anderer Details, die nicht vollständig angegeben sind, kann die Leistung des Algorithmus beeinflussen, möglicherweise in hohem Maße für bestimmte Eingabearrays. Bei der Erörterung der Effizienz von Quicksort ist es daher erforderlich, zuerst diese Entscheidungen anzugeben. Hier erwähnen wir zwei spezifische Partitionsmethoden.

Lomuto Partitionschema

Dieses Schema wird Nico Lomuto zugeschrieben und von Bentley in seinem Buch populär gemacht Programmierperlen programmieren^[15] und Cormen et al. in their book Einführung in Algorithmen.^[16] In den meisten Formulierungen wählt dieses Schema das letzte Element im Array. Der Algorithmus verwaltet den Index i Wenn es das Array mit einem anderen Index scannt j so dass die Elemente bei LO durch I-1 (inklusive) sind geringer als der Drehpunkt und die Elemente bei i durch j (inklusive) sind gleich oder größer als der Drehzahl. Da dieses Schema kompakter und leicht verständlicher ist, wird es häufig im Einführungsmaterial verwendet, obwohl es weniger effizient ist als das ursprüngliche Schema von Hoare, z. B. wenn alle Elemente gleich sind.^[17] Dieses Schema verschlechtert sich zu O(n²) Wenn das Array bereits in Ordnung ist.^[10] Es wurden verschiedene Varianten vorgeschlagen, um die Leistung zu steigern, einschließlich verschiedener Möglichkeiten, Pivot auszuwählen, mit gleichen Elementen umzugehen, andere Sortieralgorithmen wie z. Sortieren durch Einfügen Für kleine Arrays und so weiter. Im Pseudocode, eine Quicksort, die Elemente sortiert bei LO durch hallo (inklusiv) eines Arrays A kann ausgedrückt werden als:^[16]

// sortiert ein (Teil eines) Arrays, teilt es in Partitionen und sortiert diese dann diese Algorithmus Quicksort (a, lo, hi) ist   // Stellen Sie sicher, dass die Indizes in korrekter Reihenfolge sind  wenn lo> = hi || lo <0 dann      Rückkehr // Partitionsarray und den Pivot -Index erhalten   P: = Partition (a, lo, hi) // Sortieren Sie die beiden Partitionen   Quicksort (a, lo, p - 1) // linke Seite von Pivot   Quicksort (a, p + 1, hi) // rechte Seite von Pivot // Unterteilen Sie Array in zwei Partitionen Algorithmus Partition (a, lo, hi) ist    Pivot: = a [Hi] // Wählen Sie das letzte Element als Pivot aus  // Temporary Pivot Index   i: = lo - 1 zum J: = lo zu Hi - 1 tun   // Wenn das aktuelle Element kleiner oder gleich dem Drehpunkt ist  wenn A [j] <= Pivot dann   // Verschieben Sie den temporären Pivot -Index vorwärts       i: = i + 1 // Tauschen Sie das aktuelle Element mit dem Element am temporären Pivot -Index aus       Tauschen Sie A [i] mit A [j] // Bewegen Sie das Pivot -Element in die richtige Pivot -Position (zwischen den kleineren und größeren Elementen)   i: = i + 1 tausche a [i] mit A [hi] Rückkehr i // der Pivot -Index 

Das Sortieren des gesamten Arrays wird durch erreicht Quicksort (a, 0, Länge (a) - 1).

Hoare Partitionschema

Eine animierte Demonstration von Quicksort unter Verwendung von Hoares Partitionsschema. Die roten Umrisse zeigen die Positionen der linken und rechten Zeiger (i und j Die schwarzen Umrisse zeigen die Positionen der sortierten Elemente, und das gefüllte schwarze Quadrat zeigt den Wert, der verglichen wird (mit (Drehzahl).

Das ursprüngliche Partitionsschema beschrieben von Tony Hoare Verwendet zwei Zeiger (Indizes in den Bereich), die an beiden Enden des zu verteilenden Arrays beginnen, und bewegen Sie sich dann aufeinander zu, bis sie eine Inversion erkennen: ein Elementpaar, eins größer als die gebundene (Hoare -Begriffe für den Pivot -Wert) am ersten Zeiger und eine weniger als die gebundene am zweiten Zeiger; Wenn der erste Zeiger zu diesem Zeitpunkt noch vor dem zweiten ist, befinden sich diese Elemente in der falschen Reihenfolge im Verhältnis zueinander und werden dann ausgetauscht.^[18] Danach werden die Zeiger nach innen bewegt, und die Suche nach einer Inversion wird wiederholt; Wenn sich die Zeiger schließlich überqueren (die ersten Punkte nach dem zweiten), wird kein Austausch durchgeführt; Es wird eine gültige Partition gefunden, wobei der Punkt der Trennung zwischen den gekreuzten Zeigern (alle Einträge, die streng zwischen den gekreuzten Zeigern liegen könnten, gleich dem Drehpunkt sind und von beiden gebildeten Unterabläufen ausgeschlossen werden können). Mit dieser Formulierung ist es möglich, dass sich ein Unterbereich als der gesamte ursprüngliche Bereich herausstellt, was verhindern würde, dass der Algorithmus voranschreitet. Hoare sieht daher fest, dass am Ende der Unterbereich, der das Pivot-Element enthält (das sich noch in seiner ursprünglichen Position befindet), durch Ausschluss dieses Pivots nach dem (falls erforderlich) aus dem Austausch mit dem Unterbereichselement verringert werden kann die Trennung; Daher wird die Beendigung von Quicksort sichergestellt.

In Bezug auf diese ursprüngliche Beschreibung machen Implementierungen häufig geringfügige, aber wichtige Variationen. Bemerkenswerterweise enthält das nachstehend dargestellte Schema Elemente, die dem Drehpunkt unter den Kandidaten für eine Inversion entsprechen (so "größer als oder gleich" und "weniger als oder gleich" -Tests werden anstelle von "größer als" bzw. "weniger als" verwendet. Da die Formulierung verwendet tun...während statt wiederholen...bis um Dies spiegelt sich tatsächlich durch die Verwendung strenger Vergleichsbetreiber wider. Obwohl es keinen Grund gibt, Elemente zu tauschen, die der Grenze entsprechen, ermöglicht diese Änderung die Tests auf den Zeigern selbst, die ansonsten erforderlich sind, um sicherzustellen, dass sie nicht außerhalb der Reichweite liegen. Da mindestens eine Instanz des Pivot -Wertes im Bereich vorhanden ist, kann der erste Fortschritt eines beiden Zeigers diese Instanz nicht übergeben, wenn ein integrativer Test verwendet wird. Sobald ein Austausch durchgeführt wurde, sind diese ausgetauschten Elemente jetzt beide streng vor dem Zeiger, der sie gefunden hat, und verhindern, dass dieser Zeiger abgelaufen ist. (Letzteres ist unabhängig vom verwendeten Test wahr, daher wäre es möglich, den integrativen Test nur bei der Suche nach der ersten Inversion zu verwenden. Wenn Sie jedoch einen integrativen Test durchgehend verwenden, wird auch sichergestellt Der Bereich ist gleich, was einen wichtigen Effizienzgewinn für die Sortierung von Arrays mit vielen gleichen Elementen ergibt.) Das Risiko einer nicht berücksichtigenden Trennung wird in unterschiedlicher Weise vermieden als von Hoare beschrieben. Eine solche Trennung kann sich nur ergeben, wenn keine Inversionen gefunden werden, wobei beide Zeiger bei der ersten Iteration zum Pivot -Element vorgehen (sie werden dann als gekreuzt angesehen und kein Austausch findet statt). Die zurückgegebene Division ist nach der endgültigen Position des zweiten Zeigers, daher ist der Fall, wo der Drehpunkt das endgültige Element des Bereichs ist und alle anderen kleiner sind als sie. Daher muss die Pivot -Wahl das endgültige Element vermeiden (in der Beschreibung von Hoare könnte es jedes Element im Bereich sein). Dies geschieht hier durch Runden Nieder die mittlere Position unter Verwendung der Boden Funktion.^[19] Dies zeigt, dass das Argument für die Korrektheit einer Implementierung des Hoare -Partitionschemas subtil sein kann und es leicht ist, es falsch zu machen.

Im Pseudocode,^[16]

// sortiert ein (Teil eines) Arrays, teilt es in Partitionen und sortiert diese dann diese Algorithmus Quicksort (a, lo, hi) ist   wenn lo> = 0 && hi> = 0 && lo <hi hi dann     P: = Partition (a, lo, hi) Quicksort (a, lo, p) // Hinweis: Der Drehpunkt ist jetzt QuickSort (A, P + 1, HI) enthalten// Unterteilen Sie Array in zwei Partitionen Algorithmus Partition (a, lo, hi) ist   // Drehwert   Pivot: = A [Boden ((Hi + lo) / 2)] // der Wert in der Mitte des Arrays  // linker Index   i: = lo - 1 // Rechtsindex   J: = Hi + 1 Schleife für immer   // Bewegen Sie den linken Index mindestens einmal und während das Element bei  // Der linke Index ist geringer als der Drehpunkt  tun i: = i + 1 während A [i] <Pivot // Bewegen Sie den rechten Index mindestens einmal und während des Elements bei links nach links  // Der richtige Index ist größer als der Pivot  tun J: = j - 1 während A [j]> Pivot // Wenn die Indizes gekreuzt werden, kehren Sie zurück  wenn i ≥ j dann Rückkehr j // Tauschen Sie die Elemente am linken und rechten Indizes aus  Tauschen A [i] mit A [j]

Das gesamte Array ist sortiert nach Quicksort (a, 0, Länge (a) - 1).

Hoares Schema ist effizienter als das Partitionschema von Lomuto, da es im Durchschnitt dreimal weniger Swaps macht. Wie bereits erwähnt, erzeugt die angegebene Implementierung auch eine ausgewogene Partition, auch wenn alle Werte gleich sind.^{[10][Selbstveröffentlichte Quelle?]}, welches Lomutos Schema nicht. Wie Lomutos Partitionsschema würde auch Hoare's Partitioning dazu führen, dass Quicksort sich verschlechtert O(n²) Bei bereits sortierter Eingabe, wenn der Drehpunkt als erste oder das letzte Element ausgewählt wurde. Mit dem mittleren Element als Pivot sortierten die Datenergebnisse jedoch mit (fast) keine Swaps in gleichgroßen Partitionen, die zum besten Fallverhalten von Quicksort, d. H. O(n Protokoll(n)). Wie andere erzeugt Hoare's Partitioning keine stabile Art. In diesem Schema befindet sich der endgültige Standort des Pivot nicht unbedingt an dem zurückgegebenen Index, da der Dreh- und Angelpunkt und die Elemente, die dem Drehpunkt entsprechen Die Partition mit einem einzelnen Element wird durch Rekursion erreicht. Die nächsten beiden Segmente, auf die sich der Hauptalgorithmus wiederholt (stutzen) (Elemente ≤ Pivot) und (p+1..hi) (Elemente ≥ Pivot) im Gegensatz zu (lo..p-1) und (p+1..hi) wie in Lomutos Schema.^[warum?]

Nachfolgende Rekursionen (Expansion im vorherigen Absatz)

Lassen Sie uns in den nächsten beiden Segmenten, auf denen der Hauptalgorithmus wiederholt, ein wenig erweitern. Weil wir strenge Komparatoren (>, <) in der verwenden "Tu ... während" Loops, um zu verhindern, dass wir außer Reichweite lief, besteht die Möglichkeit, dass der Drehpunkt selbst mit anderen Elementen in der Partitionsfunktion ausgetauscht wird. Deswegen, Der in der Partitionsfunktion zurückgegebene Index ist nicht unbedingt der Ort, an dem sich der tatsächliche Drehpunkt befindet. Betrachten Sie das Beispiel von [5, 2, 3, 1, 0]Nach dem Schema nach der ersten Partition wird das Array [0, 2, 1, 3, 5], Der zurückgegebene "Index" ist 2, was die Nummer 1 ist. Wenn der reale Drehpunkt, der wir uns entschieden haben, die Partition zu beginnen Die Partitionsfunktion in unseren nachfolgenden Rekursionen. Infolgedessen werden wir mit den Auswahl (stutzen) und (p+1..hi), oder (lo..p - 1) und (p..hi). Welche der beiden Optionen, die wir wählen, hängt von welchem ​​Index ab (Index (i oder j) Wir kehren in der Partitionsfunktion zurück, wenn sich die Indizes kreuzen und wie wir unseren Drehpunkt in der Partitionsfunktion wählen (Boden V.S. Decke).

Lassen Sie uns zunächst die Wahl der Wiederholung untersuchen (stutzen) und (p+1..hi)Mit dem Beispiel, ein Array zu sortieren, in dem mehrere identische Elemente existieren [0, 0]. Wenn der Index I (der "letztere" Index) nach dem Übergang der Indizes in der Partitionsfunktion zurückgegeben wird, würde der Index 1 nach der ersten Partition zurückgegeben. Die anschließende Rekursion auf (stutzen)wäre auf (0, 1), was genau dem gleichen Array entspricht [0, 0]. Eine nicht berücksichtigte Trennung, die eine unendliche Rekursion verursacht, wird erzeugt. Es ist daher offensichtlich, dass Beim Wiederholung (stutzen) und (p+1..hi)Da die linke Hälfte der Rekursion den zurückgegebenen Index enthält, ist es die Aufgabe der Partitionsfunktion, den "Schwanz" in nicht berücksichtigten Szenarien auszuschließen. Das heißt, der Index J (der "frühere" Index, wenn Indizes kreuzen) sollte anstelle von i zurückgegeben werden. Mit einer ähnlichen Logik eingehen, wenn Sie das Beispiel eines bereits sortierten Arrays berücksichtigen [0, 1], Die Wahl des Drehzahl muss "Boden" sein, um sicherzustellen, dass die Zeiger auf dem "ersteren" anstelle des "letzteren" anhalten (stutzen) unendliche Rekursion verursachen). Es ist genau den gleichen Grund, warum die Wahl des letzten Elements als Pivot vermieden werden muss.

Die Wahl der Wiederholung 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 berücksichtigenden Szenarien auszuschließen. Der Index I (der "letztere" Index nach dem Kreuz der Indizes) in der Partitionsfunktion muss zurückgegeben werden, und die "Decke" muss als Drehpunkt ausgewählt werden. Die beiden Nuancen sind wiederum klar, wenn man die Beispiele für die Sortierung eines Arrays berücksichtigt, in dem mehrere identische Elemente existieren ( [0, 0]) und ein bereits sortiertes Array [0, 1] beziehungsweise. Es ist bemerkenswert, dass mit der Version der Rekursion aus dem gleichen Grund die Wahl des ersten Elements als Pivot vermieden werden muss.

Umsetzungsfragen

Auswahl des Drehzahl

In den sehr frühen Versionen von Quicksort wurde das linksste Element der Partition oft als Pivot -Element ausgewählt. Leider verursacht dies bei bereits sortierten Arrays, was ein eher häufiger Anwendungsfall ist.^[20] Das Problem wurde leicht gelöst, indem entweder ein zufälliger Index für den Pivot, die Auswahl des mittleren Index der Partition oder (insbesondere für längere Partitionen) ausgewählt wurde Median des ersten, mittleren und letzten Elements der Partition für den Pivot (wie von empfohlen von empfohlen Sedgebick).^[21] Diese "Median-of-Drei" -Regel kontert den Fall sortierter (oder umgekehrter) Eingabe und liefert eine bessere Schätzung des optimalen Drehzahl (der wahre Median) als die Auswahl eines einzelnen Elements, wenn keine Informationen über die Reihenfolge des Eingabe ist bekannt.

Median-of-Drei-Code-Snippet für die Lomuto-Partition:

Mitte: = ⌊ (lo + hi) / 2⌋wenn A [Mid] <a [lo] tauschen Sie A [lo] mit einem [Mid] tauschenwenn A [hi] <a [lo] tauschen Sie A [lo] mit einem [hi] tauschenwenn A [Mid] <a [hi] tauschen Sie A [Mid] mit einem [hi] pivot: = a [hi]

Es bringt einen Median in A [hi] Zuerst dann dieser neue Wert von A [hi] wird für einen Drehpunkt verwendet, wie in einem grundlegenden Algorithmus, der oben dargestellt wird.

Insbesondere die erwartete Anzahl der Vergleiche, die zur Sortierung erforderlich sind n Elemente (siehe § Analyse von randomisierten Quicksort) mit zufälliger Pivot -Auswahl ist 1.386 n Protokoll n. Median von drei drehbar C_{n, 2} ≈ 1,188 n Protokoll nAuf Kosten einer dreiprozentigen Zunahme der erwarteten Anzahl von Swaps.^[7] Eine noch stärkere Schwingungsregel für größere Arrays ist die Auswahl der Auswahl NINTHER, ein rekursiver Median von drei (MO3), definiert als^[7]

NINTHER (a) = Median (MO3 (zuerst 1/3 von a), MO3 (Mitte 1/3 von a), MO3 (endgültig 1/3 von a))

Die Auswahl eines Drehelements wird auch durch die Existenz von kompliziert Ganzzahlüberlauf. Wenn die Grenzindizes der Sortierung der Subarray ausreichend groß sind, der naive Ausdruck für den mittleren Index, (LO + hallo)/2, verursacht Überlauf und liefert einen ungültigen Pivot -Index. Dies kann beispielsweise durch Verwendung von Verwendung überwunden werden LO + (hallo−LO)/2 das mittlere Element auf Kosten einer komplexeren Arithmetik zu indizieren. Ähnliche Probleme treten bei einigen anderen Methoden zur Auswahl des Pivot -Elements auf.

Wiederholte Elemente

Mit einem Partitionierungsalgorithmus wie dem oben beschriebenen Lomuto -Partitionsschema (auch eines, das gute Drehwerte wählt), weist Quicksort eine schlechte Leistung für Eingaben auf, die viele wiederholte Elemente enthalten. Das Problem ist deutlich zu erkennen, wenn alle Eingangselemente gleich sind: Bei jeder Rekursion ist die linke Partition leer (keine Eingangswerte sind geringer als der Drehzahl) und die rechte Partition hat nur durch ein Element verringert (der Drehpunkt wird entfernt). Folglich nimmt das Lomuto -Partitionschema ein Quadratische Zeit Ein Array von Gleichwerten sortieren. Mit einem Partitionierungsalgorithmus wie dem Hoare -Partitionsschema führen wiederholte Elemente im Allgemeinen zu einer besseren Partitionierung, und obwohl unnötige Swaps von Elementen, die dem Drehpunkt entsprechen Reduzierung des Tauschs über Kopf). In dem Fall, in dem alle Elemente gleich sind, wechselt das Hoare -Partitionschema unnötig Elemente, aber die Aufteilung selbst ist der beste Fall, wie im Abschnitt Hoare Partition oben erwähnt.

Um das Lomuto Partitions -Schema -Problem zu lösen (manchmal als das genannt Problem der niederländischen Nationalflagge^[7]) Es kann eine alternative Linear-Zeit-Partitionsroutine verwendet werden, die die Werte in drei Gruppen unterteilt: Werte weniger als der Drehpunkt, Werte, die dem Pivot entsprechen, und Werte, die größer als der Pivot sind. (Bentley und McIlroy nennen dies eine "fette Partition" und es wurde bereits in der implementiert QSORT von Version 7 Unix.^[7]) Die Werte, die dem Drehpunkt entsprechen, sind bereits sortiert, so dass nur die weniger als Partitionen rekursiv sortiert werden müssen. In Pseudocode wird der Quicksort -Algorithmus

Algorithmus Quicksort (a, lo, hi) ist  wenn LO <HI dann         P: = Pivot (a, lo, hi) links, rechts: = Partition (a, p, lo, hi) // Hinweis: Mehrere Rückgabewerte         Quicksort (a, lo, links - 1) QuickSort (a, rechts + 1, Hi)

Das Trennwand Der Algorithmus gibt Indizes zum ersten ('links “und zum letzten (' rechts ') Gegenstand der mittleren Partition zurück. Jeder Gegenstand der Partition ist gleich p und ist daher sortiert. Folglich müssen die Elemente der Partition nicht in die rekursiven Aufrufe einbezogen werden schnelle Sorte.

Der beste Fall für den Algorithmus tritt jetzt auf, wenn alle Elemente gleich sind (oder aus einem kleinen Satz von ausgewählt werden k ≪ n Elemente). Bei allen gleichen Elementen führt der modifizierte Quicksort nur zwei rekursive Aufrufe auf leere Subtarrys durch und beendet somit in linearer Zeit (unter der Annahme der Annahme der Trennwand Unterroutine dauert nicht länger als lineare Zeit).

Optimierungen

Zwei weitere wichtige Optimierungen, die ebenfalls von Sededwick vorgeschlagen und in der Praxis weit verbreitet sind, sind:^[22][23]

• Um höchstens sicherzustellen O(Protokoll n) Der Raum wird genutzt, zuerst in die kleinere Seite der Partition zurückkehren und dann a verwenden Schwanzanruf Um in den anderen zurückzukehren oder die Parameter zu aktualisieren, um die jetzt sortierte kleinere Seite nicht mehr einzuschließen, und die größere Seite zu sortieren.
• Wenn die Anzahl der Elemente unter einem Schwellenwert liegt (möglicherweise zehn Elemente), wechseln Sie zu einem nicht rekursiven Sortieralgorithmus wie z. Sortieren durch Einfügen Das führt weniger Swaps, Vergleiche oder andere Operationen auf solch kleinen Arrays durch. Der ideale "Schwellenwert" variiert je nach Einzelheiten der spezifischen Implementierung.
• Eine ältere Variante der vorherigen Optimierung: Wenn die Anzahl der Elemente geringer ist als der Schwellenwert kHalten Sie einfach auf; Führen Sie dann nach dem Verarbeitung des gesamten Arrays die Einfügungssorten darauf durch. Die frühe Rekursion verlässt das Array k-Sortiert, was bedeutet, dass jedes Element höchstens ist k Positionen von seiner endgültigen sortierten Position entfernt. In diesem Fall nimmt die Insertions -Sortier O(Kn) Zeit, um die Sortierung zu beenden, die linear ist, wenn k ist eine Konstante.^{[24][15]: 117} Im Vergleich zur Optimierung "viele kleine Arten" kann diese Version weniger Anweisungen ausführen, sie nutzt jedoch suboptimale Verwendung der Cache -Erinnerungen in modernen Computern.^[25]

Parallelisierung

Quicksorts Divide-and-Conquer-Formulierung macht es zugänglich für Parallelisierung Verwendung Aufgabe Parallelität. Der Verteilungsschritt wird durch die Verwendung von a erreicht Parallele Präfix -Summe Algorithmus zur Berechnung eines Index für jedes Array -Element in seinem Abschnitt des partitionierten Arrays.^[26][27] Bei einer Reihe von Größe n, der Partitionierungsschritt läuft Ö(n) in ... Arbeiten O(Protokoll n) Zeit und benötigt Ö(n) Zusätzlicher Kratzerraum. Nachdem das Array verteilt wurde, können die beiden Partitionen parallel rekursiv sortiert werden. Unter der Annahme einer idealen Auswahl an Drehzücht n in Ö(n Protokoll n) in ... Arbeiten O (Protokoll² n) Zeit mit Ö(n) zusätzlicher Raum.

Quicksort hat einige Nachteile im Vergleich zu alternativen Sortieralgorithmen wie Zusammenführen, sortieren, die seine effiziente Parallelisierung komplizieren. Die Tiefe des Teilen- und Konquer-Baums von Quicksort wirkt sich direkt auf die Skalierbarkeit des Algorithmus aus, und diese Tiefe hängt stark von der Wahl des Algorithmus ab. Darüber hinaus ist es schwierig, den Verteilungsschritt effizient einig zu parallelisieren. Die Verwendung des Kratzerraums vereinfacht den Partitionierungsschritt, erhöht jedoch den Speicherausdruck des Algorithmus und den ständigen Gemeinkosten.

Andere anspruchsvollere parallele Sortieralgorithmen können noch bessere Zeitgrenzen erreichen.^[28] Zum Beispiel beschrieb David Powers 1991 eine parallelisierte Quicksort (und eine verwandte Radix -Sortierung) das kann in Betrieb arbeiten O(Protokoll n) Zeit auf einem CRCW (gleichzeitiger Lesen und gleichzeitiger Schreiben) KINDERWAGEN (parallele Zufallszugriffsmaschine) mit n Prozessoren durch implizite Durchführung von Verteilungen.^[29]

Formale Analyse

Worst-Case-Analyse

Die unausgeglichenste Partition tritt auf n - 1.^[30] Dies kann auftreten, wenn der Drehpunkt das kleinste oder größte Element in der Liste oder in einigen Implementierungen (z. B. das Lomuto -Partitionschema wie oben beschrieben) ist, wenn alle Elemente gleich sind.

Wenn dies in jeder Partition wiederholt geschieht, verarbeitet jeder rekursive Anruf eine Liste von weniger als in der vorherigen Liste. Folglich können wir machen n - 1 verschachtelte Anrufe, bevor wir eine Liste der Größe 1. erreichen. Dies bedeutet, dass die Rufen Sie Baum an ist eine lineare Kette von n - 1 verschachtelte Anrufe. Das iDer Anruf tut O(n − i) arbeiten, um die Partition zu machen, und ${\ displaystyle \ textstyle \ sum _ {i = 0}^{n} (n-i) = o (n^{2})}$In diesem Fall nimmt Quicksort also O(n²) Zeit.

Best-Case-Analyse

Im ausgewogensten Fall teilen wir jedes Mal eine Partition in zwei fast gleiche Stücke auf. Dies bedeutet, dass jeder rekursive Anruf eine Liste mit einer Hälfte der Größe verarbeitet. Folglich können wir nur machen Protokoll₂ n verschachtelte Anrufe, bevor wir eine Liste der Größe 1 erreichen. Dies bedeutet, dass die Tiefe der Tiefe der Rufen Sie Baum an ist Protokoll₂ n. Aber keine zwei Anrufe auf derselben Ebene des Anrufbaums verarbeiten denselben Teil der ursprünglichen Liste; Somit braucht jede Niveau von Anrufen nur O(n) Zeit alles zusammen (jeder Anruf hat einen konstanten Overhead, aber da es nur gibt O(n) Anrufe auf jeder Ebene ist in der Subsum in der Subsum O(n) Faktor). Das Ergebnis ist, dass der Algorithmus nur verwendet O(n Protokoll n) Zeit.

Durchschnittsfallanalyse

Eine Reihe von einer Reihe von sortieren n verschiedene Elemente, Quicksort nimmt O(n Protokoll n) Zeit in der Erwartung, gemittelt über alle gemittelt n! Permutationen von n Elemente mit Gleiche Wahrscheinlichkeit. Wir listen hier drei gemeinsame Beweise für diese Behauptung auf, die unterschiedliche Einblicke in die Funktionsweise von Quicksort geben.

Mit Perzentilen

Wenn jeder Drehpunkt irgendwo in den mittleren 50 Prozent rangiert hat, dann zwischen dem 25. Perzentil und das 75. Perzentil, dann teilt es die Elemente mit mindestens 25% und höchstens 75% auf jeder Seite. Wenn wir solche Pivots konsequent wählen könnten, müssten wir die Liste höchstens teilen ${\ displayStyle \ log _ {4/3} n}$ Zeiten vor Erreichen von Listen der Größe 1 und ergeben eine O(n Protokoll n) Algorithmus.

Wenn die Eingabe eine zufällige Permutation ist, hat der Drehpunkt einen zufälligen Rang und ist daher nicht garantiert in den mittleren 50 Prozent. Wenn wir jedoch von einer zufälligen Permutation beginnen, hat der Pivot in jedem rekursiven Aufruf einen zufälligen Rang in seiner Liste, und so ist es in den mittleren 50 Prozent etwa die Hälfte der Zeit. Das ist gut genug. Stellen Sie sich vor, eine Münze wird umgedreht: Köpfe bedeutet, dass der Rang des Drehausfalls in den mittleren 50 Prozent liegt. Schwanz bedeutet, dass dies nicht der Fall ist. Stellen Sie sich nun vor, die Münze wird immer wieder umgedreht, bis sie wird k Köpfe. Obwohl dies durchschnittlich nur lange dauern könnte, nur durchschnittlich 2k Flips sind erforderlich, und die Chance, dass die Münze nicht bekommt k Köpfe danach 100k Flips ist höchst unwahrscheinlich (dies kann mit Verwendung streng gemacht werden Tschernoff Grenzen). Durch das gleiche Argument endet die Rekursion von Quicksort durchschnittlich in einer Anruftiefe von nur von ${\ displayStyle 2 \ log _ {4/3} n}$. Aber wenn seine durchschnittliche Anruftiefe ist O(Protokoll n)und jede Ebene des Anrufbaums verarbeitet höchstens n Elemente, der Gesamtbetrag der im Durchschnitt geleisteten Arbeit ist das Produkt. O(n Protokoll n). Der Algorithmus muss nicht überprüfen, ob sich der Drehpunkt in der mittleren Hälfte befindet - wenn wir ihn ständigen Bruchteil der Zeit treffen, reicht dies für die gewünschte Komplexität aus.

Rezidive

Ein alternativer Ansatz ist die Einrichtung a Rezidivbeziehung für die T(n) Faktor, die Zeit, die erforderlich ist, um eine Liste der Größe zu sortieren n. Im unausgeglichensten Fall beinhaltet ein einzelner Schnellsortaufruf O(n) Arbeit plus zwei rekursive Anrufe auf Listen der Größe 0 und n–1, also ist die Rezidivbeziehung

${\ displayStyle t (n) = o (n)+t (0)+t (n-1) = o (n)+t (n-1).}$

Dies ist die gleiche Beziehung wie für Sortieren durch Einfügen und Auswahlsortenund es löst zum schlimmsten Fall T(n) = O(n²).

Im ausgewogensten Fall beinhaltet ein einziger Schnellsortaufruf O(n) Arbeit plus zwei rekursive Anrufe auf Listen der Größe n/2, also ist die Rezidivbeziehung

${\ displayStyle t (n) = o (n)+2t \ links ({\ frac {n} {2}} \ rechts).}$

Das Master-Theorem für Teilen und Konquer-Rezidive sagt uns das T(n) = O(n Protokoll n).

Der Umriss eines formellen Beweises der O(n Protokoll n) Die erwartete Zeitkomplexität folgt. Angenommen, es gibt keine Duplikate, da Duplikate mit linearer Zeitvor- und Nachbearbeitung behandelt werden oder die Fälle leichter als die analysierten als die analysierten angesehen werden können. Wenn die Eingabe eine zufällige Permutation ist, ist der Rang des Drehzahl von 0 bis 0 einheitlich zufällig n - 1. Dann haben die resultierenden Teile der Partition Größen i und n − i - 1, und ich ist einheitlich zufällig von 0 bis n - 1. Die Mittelung aller möglichen Splits und der Anmerkung, dass die Anzahl der Vergleiche für die Partition ist n - 1Die durchschnittliche Anzahl der Vergleiche über alle Permutationen der Eingangssequenz kann durch Lösung der Rezidivbeziehung genau geschätzt werden:

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

${\ displayStyle nc (n) = n (n-1) +2 \ sum _ {i = 0}^{n-1} c (i)}$

${\ displayStyle nc (n)-(n-1) c (n-1) = n (n-1)-(n-1) (n-2)+2c (n-1)}$

${\ displayStyle nc (n) = (n+1) c (n-1)+2n-2}$

$oder +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}} \ appy 2 \ int _ {1}^{n} {\ frac {1} { x}} \ mathhrm {d} x = 2 \ ln n \ end {ausgerichtet}}}$

Lösung des Wiederauftretens gibt C(n) = 2n ln n ≈ 1,39n Protokoll₂ n.

Dies bedeutet, dass Quicksort im Durchschnitt nur etwa 39% schlechter ist als in seinem besten Fall. In diesem Sinne liegt es näher am besten als dem schlimmsten Fall. EIN Vergleichsart kann nicht weniger als verwenden als Protokoll₂(n!) Vergleiche durchschnittlich zu sortieren n Artikel (as im Artikelvergleichsart erklärt) und im Fall groß n, Stirlings Annäherung ergibt Protokoll₂(n!) ≈ n(Protokoll₂ n - log₂ e)So ist Quicksort nicht viel schlechter als eine ideale Vergleichsart. Diese schnelle Durchschnittszeit ist ein weiterer Grund für die praktische Dominanz von Quicksort gegenüber anderen Sortieralgorithmen.

Verwenden eines binären Suchbaums

Folgende Binärer Suchbaum (BST) entspricht jeder Ausführung von QuickSort: Der anfängliche Drehpunkt ist der Wurzelknoten; Der Drehpunkt der linken Hälfte ist die Wurzel des linken Unterbaums, der Drehpunkt der rechten Hälfte ist die Wurzel des rechten Subtree und so weiter. Die Anzahl der Vergleiche der Ausführung von Quicksort entspricht der Anzahl der Vergleiche während des Aufbaus des BST durch eine Abfolge von Insertionen. Die durchschnittliche Anzahl der Vergleiche für randomisierte Quicksort entspricht den durchschnittlichen Kosten für den Bau eines BST, wenn die eingefügten Werte eingefügt werden ${\ displayStyle (x_ {1}, x_ {2}, \ ldots, x_ {n})}$ eine zufällige Permutation bilden.

Betrachten Sie eine BST, die durch Einfügen einer Sequenz erzeugt wurde ${\ displayStyle (x_ {1}, x_ {2}, \ ldots, x_ {n})}$ von Werten, die eine zufällige Permutation bilden. Lassen C bezeichnen die Kosten für die Schaffung der BST. Wir haben ${\ displayStyle c = \ sum _ {i} \ sum _ {j <i} c_ {i, j}}$, wo ${\ displayStyle c_ {i, j}}$ ist eine binäre zufällige Variable, die ausdrückt, ob während der Einführung von ${\ displaystyle x_ {i}}$ Es gab einen Vergleich zu ${\ displayStyle x_ {j}}$.

Durch Linearität der Erwartung, der erwartete Wert ${\ displayStyle \ operatorname {e} [c]}$ von C ist $oder$.

Fix i und j<i. Die Werte ${\ displaystyle {x_ {1}, x_ {2}, \ ldots, x_ {j}}}$Einmal sortiert definieren j+1 Intervalle. Die kernstrukturelle Beobachtung ist das ${\ displaystyle x_ {i}}$ wird verglichen mit ${\ displayStyle x_ {j}}$ im Algorithmus, wenn und nur wenn ${\ displaystyle x_ {i}}$ fällt in eines der beiden Intervalle neben ${\ displayStyle x_ {j}}$.

Beobachten Sie das seitdem ${\ displayStyle (x_ {1}, x_ {2}, \ ldots, x_ {n})}$ ist eine zufällige Permutation, ${\ displayStyle (x_ {1}, x_ {2}, \ ldots, x_ {j}, x_ {i})}$ ist auch eine zufällige Permutation, also die Wahrscheinlichkeit, dass ${\ displaystyle x_ {i}}$ ist neben ${\ displayStyle x_ {j}}$ ist genau ${\ displayStyle {\ frac {2} {j+1}}}$.

Wir enden mit einer kurzen Berechnung:

$oder log i \ rechts) = o (n \ log n).}$

Raumkomplexität

Der von Quicksort verwendete Raum hängt von der verwendeten Version ab.

Die In-Place-Version von Quicksort hat eine Raumkomplexität von O(Protokoll n)selbst im schlimmsten Fall, wenn es mit den folgenden Strategien sorgfältig implementiert wird.

• Die Einteilung der Platzierung wird verwendet. Diese instabile Partition erfordert O(1) Platz.
• Nach der Aufteilung wird die Teilung mit den wenigsten Elementen (rekursiv) zuerst sortiert und muss höchstens erforderlich sein O(Protokoll n) Platz. Dann wird die andere Partition sortiert mithilfe Schwanzrekursion oder Iteration, die den Anrufstapel nicht hinzufügen. Diese Idee wurde, wie oben erläutert, von beschrieben von R. Sedgebickund hält die Stapeltiefe durch O(Protokoll n).^[21][24]

Quicksort mit an Ort und instabiler Partitionierung verwendet nur einen konstanten zusätzlichen Platz, bevor rekursive Anrufe erzielt werden. Quicksort muss für jeden verschachtelten rekursiven Anruf eine konstante Menge an Informationen speichern. Da macht der beste Fall höchstens O(Protokoll n) verschachtelte rekursive Anrufe, es verwendet es O(Protokoll n) Platz. Ohne Sedgewicks Trick, um die rekursiven Anrufe zu begrenzen O(n) verschachtelte rekursive Anrufe und Bedürfnisse O(n) Hilfsraum.

Aus Sicht einer Bit -Komplexität, Variablen wie z. LO und hallo Verwenden Sie keinen konstanten Raum; es braucht O(Protokoll n) Bits zu indexieren in eine Liste von n Artikel. Da es in jedem Stack -Rahmen solche Variablen gibt O((Protokoll n)²) Raumstücken. Diese Raumbedarf ist jedoch nicht zu schrecklich, da die Liste, wenn sie unterschiedliche Elemente enthielt, zumindest erforderlich wäre O(n Protokoll n) Raumstücken.

Eine andere, weniger häufig vorkommende Version von Quicksort verwendet die Version von Quicksort O(n) Platz für den Arbeitsplatz und kann eine stabile Sortierung implementieren. Mit dem Arbeitspeicher kann das Eingabearray leicht auf stabile Weise partitioniert und dann für aufeinanderfolgende rekursive Anrufe in das Eingabearray kopiert werden. Die Optimierung von Sedgewick ist immer noch angemessen.

Beziehung zu anderen Algorithmen

Quicksort ist eine platzoptimierte Version der Binärbaum -Sortierung. Anstatt Elemente nacheinander in einen expliziten Baum einzuführen, organisiert Quicksort sie gleichzeitig in einen Baum, der durch die rekursiven Anrufe impliziert wird. Die Algorithmen machen genau die gleichen Vergleiche, aber in einer anderen Reihenfolge. Ein oft wünschenswertes Eigentum von a Sortieren von Algorithmus ist Stabilität - das ist die Reihenfolge der Elemente, die gleich vergleichen, wird nicht geändert, was die Steuerung der Reihenfolge von Multikey -Tabellen (z. B. Verzeichnis- oder Ordnerlisten) auf natürliche Weise ermöglicht. Diese Eigenschaft ist für in situ (oder an Ort und Stelle) Quicksort schwer zu warten (die nur einen konstanten zusätzlichen Raum für Zeiger und Puffer nutzt, und O(Protokoll n) zusätzlicher Raum für die Verwaltung einer expliziten oder impliziten Rekursion). Für Varianten -Quicksorts, die zusätzlichen Speicher aufgrund von Darstellungen unter Verwendung von Zeigern (z. B. Listen oder Bäumen) oder Dateien (effektiv Listen) beinhalten, ist es trivial, die Stabilität aufrechtzuerhalten. Die komplexeren oder scheibengebundenen Datenstrukturen erhöhen die Zeitkosten tendenziell und machen im Allgemeinen zunehmend die Verwendung des virtuellen Speichers oder der Festplatte.

Der direkteste Konkurrent von Quicksort ist Haufen. Die Laufzeit von Heapsort ist O(n Protokoll n), aber die durchschnittliche Laufzeit von Haufen wird normalerweise als langsamer angesehen als in der Stelle.^[31] Dieses Ergebnis ist fraglich; Einige Veröffentlichungen zeigen das Gegenteil an.^[32][33] Introsort ist eine Variante von Quicksort, die zu Haufen umschaltet, wenn ein schlechter Fall erkannt wird, um die schlimmste Laufzeit von Quicksort zu vermeiden.

Quicksort konkurriert auch mit Zusammenführen, sortieren, Ein weiterer O(n Protokoll n) Sortieren von Algorithmus. Mergesort ist a stabile SorteIm Gegensatz zu Standard-In-Place-Quicksort und Heapsort und bietet eine hervorragende Leistung von Worst-Case. Der Hauptnachteil von Mergesort besteht darin, dass effiziente Implementierungen beim Betrieb auf Arrays erforderlich sind O(n) Hilfsraum, während die Variante von Quicksort mit der Einstellung und der Schwanzrekursion nur verwendet O(Protokoll n) Platz.

Mergesort funktioniert sehr gut auf verlinkte Listennur eine kleine, konstante Menge an Hilfspeicher. Obwohl Quicksort mithilfe verknüpfter Listen als stabile Sortierung implementiert werden kann, leiden sie häufig ohne Zufallszugriff an schlechten Drehauswahlmöglichkeiten. Mergesort ist auch der Algorithmus der Wahl für externe Sortierung von sehr großen Datensätzen, die auf langsamen Medien gespeichert sind, wie z. Festplattenspeicher oder Netzwerkspeicher.

Eimer -Sort mit zwei Eimern ist QuickSort sehr ähnlich; Der Drehpunkt in diesem Fall ist effektiv der Wert in der Mitte des Wertebereichs, was für gleichmäßig verteilte Eingaben durchschnittlich gut funktioniert.

Auswahlbasierte Drehung

A Auswahlalgorithmus wählt die kth kleinste einer Liste von Zahlen; Dies ist ein einfacheres Problem im Allgemeinen als das Sortieren. Ein einfacher, aber effektiver Selektionsalgorithmus funktioniert fast auf die gleiche Weise wie Quicksort und ist dementsprechend bekannt als Schnellauswahl. Der Unterschied besteht darin, dass anstatt rekursive Aufrufe beider Sublisten zu tätigen, nur einen einzelnen Schwanz-rezisiven Aufruf auf den Sublisten macht, der das gewünschte Element enthält. Diese Änderung verringert die durchschnittliche Komplexität auf linear oder verringert O(n) Zeit, die für die Auswahl optimal ist, der Auswahlalgorithmus ist jedoch immer noch O(n²) im schlimmsten Fall.

Eine Variante von QuickSelect, die Median der Mediane Algorithmus wählt Pivots sorgfältiger aus und stellt sicher, dass die Pivots in der Nähe der Mitte der Daten (zwischen dem 30. und 70. Perzentil) liegen und somit eine lineare Zeit garantiert haben. O(n). Die gleiche Pivot -Strategie kann verwendet werden, um eine Variante von Quicksort (Median der Medianer Quicksort) zu konstruieren O(n Protokoll n) Zeit. Der Overhead bei der Auswahl des Pivots ist jedoch signifikant, so dass dies in der Praxis im Allgemeinen nicht verwendet wird.

Abstrakter, mit gegebener O(n) Selektionsalgorithmus kann es verwenden, um den idealen Drehpunkt (den Median) bei jedem Schritt von Quicksort zu finden und somit einen Sortieralgorithmus mit zu erzeugen O(n Protokoll n) Laufzeit. Praktische Implementierungen dieser Variante sind im Durchschnitt erheblich langsamer, aber sie sind von theoretischem Interesse, da sie einen optimalen Selektionsalgorithmus zeigen, der einen optimalen Sortieralgorithmus ergeben kann.

Varianten

Multi-Pivot-Quicksort

Anstatt sich in zwei Subtarrays mit einem einzelnen Dreh- und Angelpunkt-Multi-Pivot-Quicksort zu unterscheiden (auch Multiquicksort^[25]) verteilt seine Eingabe in einige s Anzahl der Subtarrays verwenden s - 1 Pivots. Während der Dual-Pivot-Fall (s = 3) wurde von Sedgewick und anderen bereits Mitte der 1970er Jahre betrachtet, die resultierenden Algorithmen waren in der Praxis nicht schneller als das "klassische" Quicksort.^[34] Eine Bewertung eines Multiquicksorts von 1999 mit einer variablen Anzahl von Pivots, die auf die effiziente Verwendung von Prozessor -Caches abgestimmt wurden, stellte fest, dass die Anweisungszahl um etwa 20%erhöht wurde. Simulationsergebnisse deuteten jedoch darauf hin, dass sie bei sehr großen Eingaben effizienter wäre.^[25] Eine Version von Doppel-Pivot-Quicksort, die 2009 von Yaroslavskiy entwickelt wurde^[11] Es stellte sich heraus, dass es schnell genug war, um die Implementierung in der Umsetzung zu rechtfertigen Java 7als Standardalgorithmus zur Sortierung von Arrays von Primitive (Sortieren von Arrays von Objekte wird verwendet Timsort).^[35] Der Leistungsvorteil dieses Algorithmus wurde anschließend hauptsächlich mit der Cache -Leistung zusammenhängen.^[36] und experimentelle Ergebnisse zeigen, dass die Drei-Pivot-Variante bei modernen Maschinen noch besser abschneiden kann.^[37][38]

Externe Quicksort

Für Festplattendateien ist eine externe Sortierung, die auf der Partitionierung wie QuickSort basiert, möglich. Es ist langsamer als externe Zusammenführungssortierung, erfordert aber keinen zusätzlichen Speicherplatz. 4 Puffer werden verwendet, 2 für Eingabe, 2 für die Ausgabe. Sei n = Anzahl der Datensätze in der Datei, b = die Anzahl der Datensätze pro Puffer und m = n/b = die Anzahl der Puffersegmente in der Datei. Daten werden von beiden Enden der Datei nach innen gelesen (und geschrieben). Sei x die Segmente, die am Anfang der Datei beginnen, und y repräsentieren Segmente, die am Ende der Datei beginnen. Daten werden in die X- und Y -Lesepuffer gelesen. Ein Pivot -Datensatz wird ausgewählt und die Datensätze in den X- und Y -Puffern als dem Pivot -Datensatz werden in aufsteigender Reihenfolge in den X -Schreibpuffer und y Write Puffer in absteigender Reihenfolge kopiert. Sobald der 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 werden und ein Schreibpuffer verbleibt. Wenn dieser Puffer ein X -Schreibpuffer ist, wird der Pivot -Datensatz und der X -Puffer geschrieben. Wenn dieser Puffer ein Y -Schreibpuffer ist, wird der Pivot -Datensatz auf den Y -Puffer und den Y -Puffer vorbereitet. Dies stellt einen Partitionschritt der Datei aus, und die Datei besteht nun aus zwei Teildateien. Die Start- und Endpositionen jeder Subdatei werden über eine Rekursion in einen eigenständigen Stapel oder den Hauptstapel gedrückt/gesprungen. Um den Stapelraum auf O (log2 (n)) zu begrenzen, wird das kleinere Teildatei zuerst verarbeitet. Drücken Sie für einen eigenständigen Stapel die größeren Teildateiparameter auf den Stapel und iterieren Sie das kleinere Teildatei. Um die Rekursion zu erhalten, wieder auf dem kleineren Teildatei wieder aufnehmen und dann das größere Teildatei verarbeiten. Sobald eine Unterdatei kleiner oder gleich 4-B-Datensätzen beträgt, wird die Unterdatei über Quicksort sortiert und geschrieben. Diese Unterdatei ist jetzt sortiert und in der Datei an Ort und Stelle. Der Prozess wird fortgesetzt, bis alle Subakte sortiert und an Ort und Stelle sind. Die durchschnittliche Anzahl der Pässe in der Datei beträgt ungefähr 1 + ln (n + 1)/(4 b), das schlimmste Fallmuster ist jedoch N -Pässe (äquivalent zu O (n^2) für die schlimmste interne Sortierung).^[39]

Drei-Wege-Radix Quicksort

Dieser Algorithmus ist eine Kombination von Radix -Sortierung und Quicksort. Wählen Sie ein Element aus dem Array (dem Drehpunkt) und betrachten Sie das erste Zeichen (Schlüssel) der Zeichenfolge (Multikey). Partition Die verbleibenden Elemente in drei Sätze: diejenigen, deren entsprechender Charakter geringer ist, gleich, gleich und größer als der Zeichen des Pivots. Sortieren Sie rekursiv die "weniger als" und "größer als" Partitionen auf demselben Charakter. Sortieren Sie rekursiv die "Gleiche" der Partition durch das nächste Zeichen (Schlüssel). Da wir mit Bytes oder Längenwörtern sortieren, sortieren wir W Bits, der beste Fall ist O(Kn) und der schlimmste Fall O(2^KN) oder zumindest O(N²) für Standard -Quicksort, die für einzigartige Schlüssel angegeben ist N<2^K, und K ist eine versteckte Konstante im gesamten Standard Vergleichsart Algorithmen einschließlich Quicksort. Dies ist eine Art Drei-Wege exakt Gleich dem Drehpunkt.

Schnelle Radix -Sortierung

Auch von Powers als O(K) parallel KINDERWAGEN Algorithmus. Dies ist wieder eine Kombination von Radix -Sortierung und Quicksort, aber die Entscheidung von Quicksort Links/Right Partition wird auf aufeinanderfolgenden Teilen des Schlüssels getroffen und ist also O(Kn) zum N K-Bitschlüssel. Alle Vergleichsart Algorithmen implizit annehmen die Transdichotomes Modell mit K in Θ(Protokoll N), als ob K ist kleiner, wir können sortieren O(N) Zeit mit einer Hash -Tabelle oder Ganzzahlsortierung. Wenn K ≫ Protokoll N Aber Elemente sind innen einzigartig O(Protokoll N) Bits, die verbleibenden Bits werden weder durch Quicksort noch durch Quick Radix -Sortierung betrachtet. Wenn alle Vergleichssortierungsalgorithmen nicht überzogen sind O(K) Relativ nutzlose Teile, aber eine schnelle Radix -Sortierung vermeiden den schlimmsten Fall O(N²) Verhaltensweisen von Standard -Quicksort- und Radix Quicksort und werden auch im besten Fall dieser Vergleichsalgorithmen unter diesen Bedingungen schneller sein uniqueprefix (K) ≫ log N. Siehe Kräfte^[40] Zur weiteren Diskussion der verborgenen Gemeinkosten im Vergleich, Radix und paralleler Sortierung.

Blockquicksort

In jedem vergleichsbasierten Sortierungsalgorithmus erfordert die Minimierung der Anzahl der Vergleiche die Maximierung der aus jedem Vergleich gewonnenen Informationen, was bedeutet, dass die Vergleichsergebnisse unvorhersehbar sind. Dies verursacht häufig Zweig -Fehlverhalten, die Leistung einschränken.^[41] Blockquicksort^[42] ordnet die Berechnungen von Quicksort um Datenabhängigkeiten. Bei der Partitionierung ist der Eingang in mittelgroße Größe unterteilt Blöcke (die leicht in die passen Datencache) und zwei Arrays sind mit den Positionen von Elementen gefüllt, um auszutauschen. (Um bedingte Zweige zu vermeiden, wird die Position am Ende des Arrays bedingungslos gespeichert, und der Index des Endes wird erhöht, wenn ein Swap benötigt wird.) Ein zweiter Durchgang wechselt die Elemente an den in den Arrays angegebenen Positionen. Beide Schleifen haben nur einen bedingten Zweig, einen Test zur Beendigung, der normalerweise durchgeführt wird.

Partielle und inkrementelle Quicksort

Es gibt mehrere Varianten von Quicksort, die die trennen k Kleinste oder größte Elemente aus dem Rest des Eingangs.

Verallgemeinerung

Richard Cole und David C. Kandathil entdeckte 2004 eine Ein-Parameter-Familie mit Sortieren von Algorithmen, die als Partitionsarten bezeichnet werden und die im Durchschnitt (mit allen Eingangsreihenfolge gleich wahrscheinlich) höchst ${\ displayStyle n \ log n+{o} (n)}$ Vergleiche (nahe der Informationstheoretik unter der unteren Grenze) und ${\ displayStyle {\ theta} (n \ log n)}$ Operationen; Im schlimmsten Fall treten sie auf ${\ displayStyle {\ theta} (n \ log ^{2} n)}$ Vergleiche (und auch Operationen); Diese sind an Ort ${\ displayStyle {o} (\ log n)}$ Platz. Praktische Effizienz und geringere Leistungsabweichungen wurden gegen optimierte Quicksorts (von gezeigt Sedgebick und Bentley-McIlroy).^[43]

Siehe auch

• Introsort- Hybridsortieralgorithmus

Anmerkungen

Verweise

• Sedgewick, R. (1978). "Implementierung von Quicksort -Programmen". Comm. ACM. 21 (10): 847–857. doi:10.1145/359619.359631. S2CID 10020756.
• Dean, B. C. (2006). "Eine einfache erwartete Laufzeitanalyse für randomisierte" Divide- und Eroberung von Algorithmen ". Diskrete angewandte Mathematik. 154: 1–5. doi:10.1016/j.dam.2005.07.005.
• Hoare, C. A. R. (1961). "Algorithmus 63: Partition". Comm. ACM. 4 (7): 321. doi:10.1145/366622.366642. S2CID 52800011.
• Hoare, C. A. R. (1961)."Algorithmus 65: Find". Comm. ACM. 4 (7): 321–322. doi:10.1145/366622.366647.
• Hoare, C. A. R. (1962). "Schnelle Sorte". Computer. J. 5 (1): 10–16. doi:10.1093/comjnl/5.1.10. (Nachdruck in Hoare und Jones: Essays in Computer Science, 1989.)
• Musser, David R. (1997). "Introspektive Sortier- und Auswahlalgorithmen". Software: Übung und Erfahrung. 27 (8): 983–993. doi:10.1002/(SICI) 1097-024X (199708) 27: 8 <983 :: Aid-Spe117> 3.0.co; 2-#.
• Donald Knuth. Die Kunst der Computerprogrammierung, Band 3: Sortieren und Suchen, Dritte Edition. Addison-Wesley, 1997. ISBN0-201-89685-0. Seiten 113–122 von Abschnitt 5.2.2: Sortieren durch Austausch.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, und Clifford Stein. Einführung in Algorithmen, Zweite Ausgabe. MIT Press und McGraw-Hill, 2001. ISBN0-262-03293-7. Kapitel 7: Quicksort, S. 145–164.
• Faron Moller. Analyse von Quicksort. CS 332: Entwerfen von Algorithmen. Abteilung für Computerwissenschaften, Swansea University.
• Martínez, C.; Roura, S. (2001). "Optimale Stichprobenstrategien in Quicksort und QuickSelect". Siam J. Comput. 31 (3): 683–705. Citeseerx 10.1.1.17.4954. doi:10.1137/s0097539700382108.
• Bentley, J. L.; McIlroy, M. D. (1993). "Engineering eine Sortierfunktion". Software: Übung und Erfahrung. 23 (11): 1249–1265. Citeseerx 10.1.1.14.8162. doi:10.1002/spe.4380231105. S2CID 8822797.

Externe Links

• "Animierte Sortieralgorithmen: Schnelle Sortierung". Archiviert von das Original am 2. März 2015. Abgerufen 25. November 2008. - Grafische Demonstration
• "Animierte Sortieralgorithmen: Schnelle Sortierung (3-Wege-Partition)". Archiviert von das Original am 6. März 2015. Abgerufen 25. November 2008.
• Öffnen Sie Datenstrukturen - Abschnitt 11.1.2 - Quicksort, Pat Morin
• Interaktive Illustration von Quicksort, mit Code -Walkthrough