Warum ist quicksort besser als andere algorithmen zur Sortierung in der Praxis?

https://cs.stackexchange.com/questions/3

15-10-2019
|

Frage

In einem standard-algorithmen natürlich sind wir gelehrt, dass quicksort ist $O(n \log n)$ im Durchschnitt und $O(n^2)$, im schlimmsten Fall.Zur gleichen Zeit, andere Sortieren-algorithmen untersucht, die $O(n \log n)$ im schlimmsten Fall (wie mergesort und heapsort), und auch die lineare Zeit, im besten Fall (wie bubblesort), aber mit einigen zusätzlichen Bedarf an Speicher.

Nach einem kurzen Blick auf einige mehr mal es ist natürlich, zu sagen, dass quicksort sollten Sie nicht so effizient ist wie andere.

Bedenken Sie auch, dass die Studenten lernen, im basic-Programmierung-Kurse, die Rekursion ist nicht wirklich gut, im Allgemeinen, weil es könnte verwenden zu viel Speicher, etc.Daher (und das obwohl dies ist nicht ein echtes argument), das gibt die Idee, dass quicksort möglicherweise nicht wirklich gut, weil es ein rekursiver Algorithmus.

Aber warum hat quicksort übertreffen andere Sortier-algorithmen in der Praxis? Tut es haben zu tun mit der Struktur der real-world-Daten?Tut es haben zu tun mit der Art, wie Erinnerung funktioniert in Computern?Ich weiß, dass einige Erinnerungen sind schneller als andere, aber ich weiß nicht, ob das der eigentliche Grund für diese Zähler-intuitive performance (im Vergleich zu den theoretischen Schätzungen).

Update 1: eine kanonische Antwort ist zu sagen, dass die Konstanten beteiligt, die $O(n\log n)$ der Durchschnittliche Fall kleiner sind als die Konstanten, die andere $O(n\log n)$ - algorithmen.Ich habe jedoch noch eine ordentliche Begründung dieser, mit genauen Berechnungen anstelle von intuitiven Ideen nur.

In jedem Fall, wie es scheint, der eigentliche Unterschied tritt auf, da einige Antworten deuten auf Speicher-Ebene, wo Implementierungen nutzen Sie die interne Struktur von Rechnern, unter Verwendung, beispielsweise, dass die cache-Speicher ist schneller als der RAM.Die Diskussion ist schon interessant, aber ich würde immer noch gerne sehen, mehr detail in Bezug auf Speicher-management, da es scheint, dass die die Antwort hat zu tun mit es.

Update 2: Es gibt mehrere web-Seiten anbieten, ein Vergleich von algorithmen zur Sortierung, etwas schicker als andere (vor allem sorting-algorithms.com).Andere als präsentiert eine schöne visuelle Hilfe, mit diesem Ansatz nicht meine Frage beantworten.

Lösung

Kurze Antwort

Das Argument der Cache -Effizienz wurde bereits im Detail erläutert. Darüber hinaus gibt es ein intrinsisches Argument, warum Quicksort schnell ist. Wenn implementiert wie mit zwei „Kreuzungszeigern“, zB hier, Die inneren Schleifen haben einen sehr kleinen Körper. Da dies der Code ist, der am häufigsten ausgeführt wird, zahlt sich dies aus.

Lange Antwort

Zuerst,

Das Durchschnittlicher Fall existiert nicht!

Da der beste und schlimmste Fall häufig Extreme in der Praxis selten auftreten, erfolgt die durchschnittliche Fallanalyse. Aber jede durchschnittliche Fallanalyse nimmt einige an Verteilung der Eingänge! Zum Sortieren ist die typische Wahl die Zufälliger Permutationsmodell (stillschweigend angenommen auf Wikipedia).

Warum $ o $ -Notation?

Die Verwerfen von Konstanten bei der Analyse von Algorithmen erfolgt aus einem Hauptgrund: Wenn ich interessiert bin genau Laufzeiten, Ich brauche (relative) Kosten aller beteiligten grundlegenden Operationen (Es ignorieren auch immer noch Caching -Probleme, Pipelining in modernen Prozessoren ...). Mathematische Analyse kann zählen Wie oft jede Anweisung ausgeführt wird, aber die Laufzeiten einzelner Anweisungen hängen von Prozessordetails ab, z. B. ob eine 32-Bit-Ganzzahl-Multiplikation so viel Zeit in Anspruch genommen wird wie die Ergänzung.

Es gibt zwei Möglichkeiten:

Fix ein Maschinenmodell.

Dies geschieht in Don KnuthBuchserie "Die Kunst der Computerprogrammierung" Für einen vom Autor erfundenen künstlichen „typischen“ Computer. In Band 3 finden Sie genau Durchschnittliche Fallergebnisse Für viele Sortieralgorithmen, z. B.
- Quicksort: $ 11.667 (n+1) ln (n) -1,74n-18,74 $
- Mergesort: $ 12,5 n ln (n) $
- Haufen: $ 16 n ln (n) +0,01n $
- Insertionsort: $ 2,25N^2+7,75n-3ln (n) $
  ^[Quelle]
Diese Ergebnisse zeigen, dass Quicksort am schnellsten ist. Es wird jedoch nur auf Knuths künstlicher Maschine bewiesen, es bedeutet nicht unbedingt etwas für Ihren X86 -PC. Beachten Sie auch, dass sich die Algorithmen für kleine Eingänge unterschiedlich beziehen:

^[Quelle]
Zusammenfassung analysieren Grundoperationen.

Zum Vergleichsbasis sortieren dies normalerweise Swaps und Schlüsselvergleiche. In Robert Sedgewicks Büchern, z. B. "Algorithmen", Dieser Ansatz wird verfolgt. Sie finden dort
- Quicksort: $ 2n ln (n) $ Vergleiche und $ frac13n ln (n) $ swaps im Durchschnitt
- Mergesort: $ 1,44n ln (n) $ Vergleiche, aber bis zu 8,66n ln (n) $ array Accesses (Mergesort basiert nicht, also können wir das nicht zählen).
- Insertionsort: $ frac14n^2 $ Vergleiche und $ frac14n^2 $ Swaps im Durchschnitt.
Wie Sie sehen, erlaubt dies nicht ohne weiteres Vergleiche von Algorithmen als genaue Laufzeitanalyse, aber die Ergebnisse sind unabhängig von Maschinendetails.

Andere Eingangsverteilungen

Wie oben erwähnt, sind durchschnittliche Fälle immer in Bezug auf eine Eingangsverteilung, so dass man andere als zufällige Permutationen berücksichtigen kann. ZB Forschung wurde für durchgeführt Quicksort mit gleichen Elementen Und es gibt einen schönen Artikel über die Standard -Sortierfunktion in Java

Andere Tipps

In Bezug auf diese Frage können mehrere Punkte angegeben werden.

Quicksort ist normalerweise schnell

Obwohl Quicksort $ o (n^2) $ verhalten hat, ist es normalerweise schnell: Unter der Annahme einer zufälligen Pivot-Auswahl besteht eine sehr große Wahrscheinlichkeit will haben.

Insbesondere, selbst wenn wir einen Drehpunkt auswählen, der eine Spaltung von 10% -90% alle 10 Splits (was eine MEH-Spaltung ist) und ein 1-Element-$ N-1 $ Element Split ansonsten (die schlechteste geteilte Split Sie können, erzeugt Get), unsere Laufzeit beträgt immer noch $ o (n log n) $ (beachten Sie, dass dies die Konstanten bis zu einem Punkt in die Luft jagen würde, an dem die Zusammenführung wahrscheinlich schneller ist).

Quicksort ist normalerweise schneller als die meisten Arten

Quicksort ist normalerweise schneller als Sorten, die langsamer sind als $ O (N log n) $ (z. B. Einfügungssortierung mit seiner Laufzeit $ o (n^2) $), einfach weil für große $ n $ ihre Laufzeiten explodieren.

Ein guter Grund, warum Quicksort in der Praxis im Vergleich zu den meisten anderen $ O (N log n) $ -Algorithmen wie Heapsort so schnell ist, liegt darin, dass es relativ cacheeffizient ist. Die Laufzeit beträgt tatsächlich $ o ( frac {n} {b} log ( frac {n} {b})) $, wobei $ b $ die Blockgröße ist. Heapsort hingegen hat keine solche Beschleunigung: Es ist überhaupt nicht auf Speicher-Cache-effizientes Zugriff.

Der Grund für diese Cache -Effizienz ist, dass sie den Eingang linear scannt und linear die Eingabe verteilt. Dies bedeutet, dass wir das Beste aus jeder Cache -Last nutzen können, die wir tun, wenn wir jede Zahl in den Cache lesen, bevor wir diesen Cache gegen einen anderen tauschen. Insbesondere der Algorithmus ist cache-obliver, was für jede Cache-Ebene eine gute Cache-Leistung bietet, was ein weiterer Sieg ist.

Die Cache -Effizienz könnte weiter verbessert werden auf $ o ( frac {n} {b} log _ { frac {m} {b}} ( frac {n} {b})) $, wobei $ m $ die Größe ist Von unserem Hauptspeicher, wenn wir $ k $ -way Quicksort verwenden. Beachten Sie, dass Mergesort auch die gleiche Cache-Effizienz wie Quicksort und seine K-Way-Version tatsächlich eine bessere Leistung (durch niedrigere konstante Faktoren) aufweist, wenn das Gedächtnis ein schwerwiegendes Einschränkung ist. Dies führt zum nächsten Punkt: Wir müssen Quicksort mit Mergesort mit anderen Faktoren vergleichen.

Quicksort ist normalerweise schneller als Mergesort

In diesem Vergleich geht es vollständig um konstante Faktoren (wenn wir den typischen Fall betrachten). Insbesondere liegt die Wahl zwischen einer suboptimalen Wahl des Pivots für Quicksort und der Kopie des gesamten Eingangs für Mergesort (oder der Komplexität des Algorithmus, das erforderlich ist, um dieses Kopieren zu vermeiden). Es stellt sich heraus, dass ersterer effizienter ist: Es steckt keine Theorie dahinter, es ist zufällig schneller.

Beachten Sie, dass Quicksort rekursivere Anrufe tätigen wird, aber die Zuordnung von Stapelraum ist billig (in der Tat fast kostenlos, solange Sie den Stapel nicht blasen) und Sie ihn wiederverwenden. Zuordnen eines riesigen Blocks auf dem Haufen (oder Ihrer Festplatte, wenn $ n $ ist Ja wirklich groß) ist etwas teurer, aber beide sind $ o ( log n) $ Overheads, die im Vergleich zu den oben genannten $ o (n) $ $ verblassen.

Beachten Sie schließlich, dass Quicksort leicht empfindlich gegenüber Eingaben ist, die in der richtigen Reihenfolge befinden. In diesem Fall kann es einige Swaps überspringen. Mergesort hat keine solchen Optimierungen, was Quicksort auch etwas schneller macht als Mergesort.

Verwenden Sie die Art, die Ihren Anforderungen entspricht

Abschließend: Kein Sortieralgorithmus ist immer optimal. Wählen Sie, welches auch immer zu Ihren Bedürfnissen entspricht. Wenn Sie in den meisten Fällen einen Algorithmus benötigen, der am schnellsten ist, und es Ihnen nichts ausmacht, dass dies in seltenen Fällen etwas langsam ist und Sie keine stabile Sortierung benötigen, verwenden Sie QuickSort. Verwenden Sie ansonsten den Algorithmus, der Ihren Bedürfnissen besser entspricht.

In einem der Programmier-Tutorials an meiner Universität haben wir die Studenten gebeten, die Leistung von Quicksort, Mergesort, Insertion-Sortierung mit der integrierten Liste von Python zu vergleichen. Timsort). Die experimentellen Ergebnisse überraschten mich zutiefst, seit die integrierte Liste so viel besser abschnitten als andere Sortieralgorithmen, auch wenn Fälle, die Quicksort leicht gemacht haben, Mergesort-Absturz. Es ist also verfrüht zu dem Schluss, dass die übliche Quicksort -Implementierung die beste in der Praxis ist. Aber ich bin mir sicher, dass es eine viel bessere Implementierung von Quicksort oder einer hybriden Version davon gibt.

Dies ist ein schöner Blog -Artikel von David R. Maciver Timsort als eine Form von adaptivem Mergesort erklären.

Ich denke, einer der Hauptgründe, warum Quicksort im Vergleich zu anderen Sortieralgorithmen so schnell ist, ist, dass es cache-freundlich ist. Wenn QS ein Segment eines Arrays verarbeitet, greift es zu Beginn und am Ende des Segments auf Elemente zu und bewegt sich in Richtung der Mitte des Segments.

Wenn Sie also anfangen, greifen Sie auf das erste Element im Array zu, und ein Stück Speicher („Position“) wird in den Cache geladen. Und wenn Sie versuchen, auf das zweite Element zuzugreifen, ist es (höchstwahrscheinlich) bereits im Cache, so dass es sehr schnell ist.

Andere Algorithmen wie Heapsort funktionieren nicht so, sie springen viel in das Array, was sie langsamer macht.

Andere haben bereits gesagt, dass das Asymptotiker Durchschnitt Die Laufzeit von Quicksort ist (in Konstante) besser als die anderer Sortieralgorithmen (in bestimmten Einstellungen).

Was bedeutet das? Angenommen, eine Permutation wird zufällig ausgewählt (unter der Annahme einer einheitlichen Verteilung). In diesem Fall liefern typische Pivot -Auswahlmethoden Pivots, die in Erwartung Teilen Sie die Liste/das Array ungefähr in zwei Hälften; Das bringt uns auf $ cal {o} (n log n) $ runter. Aber zusätzlich, Verschmelzung Partielle Lösungen, die durch Wiederholung erhalten wurden, benötigt nur eine konstante Zeit (im Gegensatz zur linearen Zeit im Fall von Mergesort). Die Trennung der Eingabe in zwei Listen entsprechend dem Drehpunkt ist natürlich in der linearen Zeit, erfordert jedoch häufig nur wenige tatsächliche Swaps.

Beachten Sie, dass es viele Varianten von Quicksort gibt (siehe EG Sedgewicks Dissertation). Sie funktionieren bei verschiedenen Eingangsverteilungen unterschiedlich (einheitlich, fast sortiert, fast umgekehrt sortiert, viele Duplikate, ...) und andere Algorithmen könnten für einige besser sein.

Eine andere Tatsache, die erwähnenswert ist, ist, dass Quicksort ist langsam Bei kurzen Eingängen im Vergleich zu Simper -Algorithmen mit weniger Overhead. Gute Bibliotheken werden daher nicht auf Listen der Länge einhergehen, sondern verwenden (z. B. die Einfügungssortierung, wenn die Eingabelänge kleiner als einige $ k ca. 10 $ ist.

Im Vergleich zu anderen vergleichsbasierten Sortierungsalgorithmen mit $ O (N lg n) $ Time-Komplexität wird Schnellsort häufig als besser angesehen als andere Algorithmen wie Merge-Sort, da es sich um einen Ort-Sortieralgorithmus handelt. Mit anderen Worten, wir brauchen keine (viel mehr) Speicher, um die Mitglieder des Arrays zu speichern.

PS: Um genau zu sein, ist es aufgabenabhängig, besser zu sein als andere Algorithmen. Für einige Aufgaben ist es möglicherweise besser, andere Sortieralgorithmen zu verwenden.

Siehe auch:

Auch wenn Quick-Sort eine schlechteste Laufzeit von $ theta (n^2) $ hat, gilt Quicksort als die beste Sortierung, da es im Durchschnitt sehr effizient ist: Die erwartete Laufzeit beträgt $ theta (n log n ) $ wo die Konstanten im Vergleich zu anderen Sortieralgorithmen sehr klein sind. Dies ist der Hauptgrund für die Verwendung der schnellen Sortierung über andere Sortieralgorithmen.

Der zweite Grund ist, dass es funktioniert in-place Sortieren und funktioniert sehr gut mit virtuellen Memory-Umgebungen.

AKTUALISIEREN: : (Nach Janomas und Svicks Kommentaren)

Um dies besser zu veranschaulichen, lassen Sie mich ein Beispiel mit der Zusammenführungssortierung geben (weil die Zusammenführungsart der nächste weit verbreitete Sort -Algorithmus nach schneller Sortierung ist) und sagen Sie Ihnen, woher die zusätzlichen Konstanten kommen (nach bestem Wissen und warum ich denke, warum ich denke, warum ich denke und warum ich denke, warum ich denke und warum ich denke, Schnelle Sortierung ist besser):

Betrachten Sie den folgenden Seqcece:

12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

Wenn Sie sich voll und ganz ansehen, wie die letzte Stufe stattfindet, ist die ersten 12 mit 8 und 8 kleiner, sodass es zuerst geht. Jetzt wird 12 wieder mit 21 und 12 verglichen, geht als nächstes und so weiter und so weiter. Wenn Sie den endgültigen Zusammenführungs -IE 4 Elemente mit 4 anderen Elementen einnehmen, entstehen viele zusätzliche Vergleiche als Konstanten, die nicht schnell anfallen. Dies ist der Grund, warum Schnellsorten bevorzugt wird.

Meine Erfahrung in der Arbeit mit Daten aus der realen Welt ist, dass quicksort ist eine schlechte Wahl.Quicksort funktioniert gut mit zufälligen Daten, aber Daten aus der realen Welt meist nicht zufällig.

Zurück im Jahr 2008, spürte ich einen hängenden software-bug nach unten, um der Verwendung von quicksort.Eine Weile später schrieb ich einfach implentations von insertion sort, quicksort, heap-sort und merge-sort und testeten diese.Mein merge-sort-besser als alle anderen während der Arbeit mit großen Datenmengen.

Seit dann, merge-sort ist mein Algorithmus Sortieren der Wahl.Es ist elegant.Es ist einfach zu implementieren.Es ist ein stabiles Sortieren.Es muss nicht entarten zu quadratischen Verhalten wie quicksort funktioniert.Wechsle ich zu insertion sort zu Sortieren kleinen arrays.

Bei vielen Gelegenheiten habe ich gefunden, mein selbst, zu denken, dass eine gegebene Implementierung funktioniert überraschend gut für quicksort nur um herauszufinden, dass es nicht tatsächlich quicksort.Manchmal ist die Umsetzung schaltet zwischen quicksort und anderen Algorithmus und manchmal ist es nicht die Verwendung von quicksort an alle.Als ein Beispiel, GLibc die qsort () - Funktionen verwendet, merge-sort.Nur, wenn die Aufteilung der Arbeitszeit Speicherplatz fehlschlägt, fällt es zurück auf die in-place-quicksort die einem code-Kommentar fordert, "die langsameren Algorithmus".

Edit:Programmiersprachen wie Java, Python und Perl auch verwenden, merge-sort, oder genauer gesagt, ein Derivat, wie Timsort oder merge-sort für große Mengen und insertion sort für kleine Gruppen.(Java auch verwendet dual-pivot quicksort, welche schneller ist als die einfache quicksort.)

1 - Schnelle Sortierung ist innen (braucht kein zusätzliches Memmory als eine konstante Menge.)

2 - Schnelle Sortierung ist einfacher zu implementieren als andere effiziente Sortieralgorithmen.

3 - Schnelle Sortierung hat in seiner Laufzeit kleinere konstante Faktoren als andere effiziente Sortieralgorithmen.

Update: Für die Zusammenführungssorte müssen Sie einige "Zusammenführungen" durchführen, die zusätzliche Arrays benötigen, um die Daten vor dem Zusammenführen zu speichern. Aber schnell nicht. Deshalb ist Quick Sort an der Stelle. Es gibt auch einige zusätzliche Vergleiche für das Zusammenführen, die die konstanten Faktoren bei der Zusammenführung erhöhen.

Unter welchen Bedingungen ist ein spezifischer Sortieralgorithmus tatsächlich der schnellste?

1) Muss es eine einigermaßen geringe Latenz haben, wenn sie parallel in der Hardware implementiert wird, während sie so wenige Gates wie möglich benötigt? Ja -> Verwenden Sie einen Bitonic Sortierer oder Batcher Odd -Even Mergesort, Latenz sind $ theta ( log (n)^2) $ und die Anzahl der Komparatoren und Multiplexer ist $ theta (n cdot log (n)^ 2) $.

2) Wie viele verschiedene Werte kann jedes Element haben? CANs Jeder mögliche Wert hat einen eindeutigen Ort im Speicher oder Cache Ja -> Verwenden Sie die Zählsart oder die Radix -Sortierung. Diese haben normalerweise eine lineare Laufzeit von $ theta (n cdot k) $ (zählende Sortierung) oder $ theta (n) cdot m) $ (Bucket -Sortierung), aber verlangsamen Sie eine große Anzahl verschiedener Werte, da $ k = 2^{#Nummer _of _possible _values} $ und $ m = #maximum _Length _of _Keys $.

3) Besteht die zugrunde liegende Datenstruktur aus verknüpften Elementen? JA -> WELL -SORGE -SORT. Es gibt sowohl leicht feste Größe als auch adaptive (auch bekannt als natürliche) Bottom-up-Verschmelzungsarten verschiedener Arten für verknüpfte Datenstrukturen, und da sie nie die gesamten Daten in jedem Schritt kopieren müssen und auch nie Rekursionen benötigen, sind sie es auch schneller als jede andere allgemeine Vergleichsbasis, noch schneller als schnelle Sortierung.

4) Muss die Sortierung stabil sein? Ja -> Verwenden Sie die Zusammenführungssortierung, entweder an Ort und Stelle oder nicht, fest oder adaptiv, abhängig von der zugrunde liegenden Datenstruktur und der Art der zu erwartenden Daten, selbst in Fällen, in denen eine schnelle Sortierung ansonsten bevorzugt wird, um eine willkürliche Sortierung zu stabilisieren Der Algorithmus erfordert $ theta (n) $ zusätzlicher Speicher im schlimmsten Fall, der aus ursprünglichen Indizes besteht, die auch mit jedem Swap, der an den Eingabedaten ausgeführt werden soll Have Over -Merge -Sortierung wird wahrscheinlich vereitelt.

5) Kann die Größe der zugrunde liegenden Daten an eine kleine bis mittlere Größe gebunden werden? zB ist n <10.000 ... 100.000.000 (abhängig von der zugrunde liegenden Architektur und Datenstruktur)? Ja -> Verwenden Sie Bitonic Sort oder Batcher Odd -Even Mergesort. Goto 1)

6) Kannst du noch einen $ theta (n) $ Memory ersparen? Ja -> a) Besteht die Eingabedaten aus großen Stücken bereits sortierter sequentieller Daten? -> Verwenden Sie adaptive (auch bekannt als natürliche) Zusammenführungsart oder TIM -Sortierung Ja -> B) Besteht die Eingangsdaten hauptsächlich aus Elementen, die fast an der richtigen Stelle sind? -> Bubble -Sortier- oder Insertions -Sortierung verwenden. Wenn Sie ihre $ theta (n^2) $ Zeitkomplexität (was für fast sortierte Daten pathologisch ist), erwägen Sie möglicherweise, mit einer (fast) asymptotisch optimalen Sequenz von Lücken auf die Shell -Sortierung zu wechseln, einige Sequenzen, die $ theta ($ theta (($ theta) bringen) ($ theta (). N CDOT log (n)^2) $ Worst Case Laufen sind bekannt oder versuchen Sie es vielleicht mit Kammsart. Ich bin mir nicht sicher, ob eine Shell -Sortierung oder eine Kamm -Sortierung in der Praxis einigermaßen gut funktionieren würde.

Nein -> 7) Kannst du einen weiteren $ theta ( log (n)) $ MADEILSCHAFT? Ja -> a) Ermöglicht die unkomplizierte Datenstruktur einen gerichteten sequentiellen Zugriff oder besser? Ja -> Ermöglicht es jeweils nur eine einzelne Folge von Lese-/Schreibzugriffe, bis das Ende der Daten erreicht wurde (z. B. gerichteter Bandzugriff)? Ja -> i) Verwenden Sie die Zusammenführungssorte, aber es gibt keinen offensichtlichen Weg, um diesen Fall zu erstellen, sodass möglicherweise zusätzliche $ theta (n) $ Memory erforderlich ist. Wenn Sie jedoch Zeit und die Bälle haben, können Sie 2 Arrays in $ theta (n) $ Zeit mit nur $ theta ( log (n)) $ Space auf stabil Donald E. Knuth "Die Kunst der Computerprogrammierung, Band 3: Sortieren und Suchen", Übung 5.5.3. Gibt an, dass es einen Algorithmus von L. trabb-Parkes gibt, der dies tut. Ich bezweifle jedoch, dass dies schneller sein würde als die naive Mergesort -Version oder die Quicksort aus dem obigen Fall. Nein, es ermöglicht mehrere gleichzeitige Zugriffe auf eine Abfolge von Daten (z. B. ist kein Bandlaufwerk) -> ii) Verwenden Sie QuickSort. Für praktische Zwecke würde ich entweder einen randomisierten oder einen approximierten Median empfehlen. Wenn Sie sich vor pathologischen $ theta (n^2) $ -Fällen beachten, sollten Sie die Intro -Sortierung verwenden. Wenn Sie sich auf deterministisches Verhalten auswirken, sollten Sie den Median Algorithmus verwenden, um das Pivot-Element auszuwählen ), während es implementiert werden kann, um nur $ theta ( log (n)) $ Space (nicht parallelisierbar) zu erfordern. Der Median-medianer Algorithmus bietet Ihnen jedoch eine deterministische Quicksort, die $ theta (N cdot log (n)) $ Run-Time hat. Nein -> Sie sind geschraubt (Entschuldigung, wir brauchen mindestens einen Weg, um einmal auf jedes Datenelement zugreifen zu können)

Nein -> 8) Können Sie eine kleine konstante Menge an Speicher ersparen? Ja -> Ermöglicht die zugrunde liegende Datenstruktur einen Zufallszugriff? Ja -> Verwenden Sie Heapsort, es hat eine asymptotische optimale Laufzeit von $ theta (n cdot log (n)) $, aber düstere Cache -Kohärenz und parallel nicht gut. Nein -> Sie sind geschraubt Nein -> Sie sind geschraubt

Implementierungshinweise für Quicksort:

1) Naive Binary Quicksort erfordert $ theta (n) $ zusätzlicher Speicher. Es ist jedoch relativ einfach, dies auf $ theta ( log (n)) $ zu reduzieren, indem der letzte Reursionsaufruf in eine Schleife umgeschrieben wird. Das Gleiche für k-ary Quicksorts für K> 2 erfordert $ theta (n^{ log_k (k-1)}) $ space (gemäß dem Master-Theorem), so dass binärer Quicksort die geringste Menge an Speicher benötigt, aber aber Ich würde mich freuen zu hören, wenn jemand weiß, ob K-Ary Quicksort für K> 2 bei einem realen Setup schneller als binäre Quicksort sein könnte.

2) Es gibt Bottom-up-iterative Varianten von Quicksort, aber Afaik, sie haben die gleichen asymptotischen Raum- und Zeitgrenzen wie die Top-Down-Seite, wobei die zusätzlichen Abwärtsseiten der Implementierung schwer zu implementieren sind (z. B. explizit verwalten eine Warteschlange). Meine Erfahrung ist, dass diese für praktische Zwecke nie in Betracht gezogen werden.

Implementierungshinweise für Mergesort:

1) Bottum-up Mergesort ist immer schneller als Top-Down-Mergesort, da es keine Rekursionsanrufe erfordert.

2) Die sehr naive Mergesort kann mit einem Doppelpuffer und dem Puffer umgestellt werden, anstatt die Daten nach jedem Schritt aus dem zeitlichen Array zurück zu kopieren.

3) Für viele reale Daten ist adaptive Mergesort viel schneller als ein Mergesort mit fester Größe.

4) Der Merge-Algorithmus kann leicht parallelisiert werden, indem die Eingangsdaten in k ungefähr gleichgroße Teile aufgeteilt werden. Dies erfordert K -Referenzen in Daten, und es ist gut, k zu wählen, so dass alle k (oder c*k für eine kleine konstante c> = 1) in die nächste Speicherhierarchie (normalerweise L1 -Datencache) passen. Die Auswahl der kleinsten aus K-Elementen Die naive Art (lineare Suche) erfordert $ theta (k) $ Zeit, während der Aufbau eines Min-Heuels in diesen K-Elementen und die Auswahl des kleinsten erforderlich ist, erfordert nur amortisierte $ theta ( log (log (log (log) ( log (log) ( log (log) ( log ((log) ( log (log) ( log ((log) ( log) ( log) ( log (( log (() auszuwählen. k)) $ time (das Minimum zu wählen ist $ theta (1) $ natürlich, aber wir müssen ein wenig Wartung durchführen, da ein Element in jedem Schritt entfernt und durch einen anderen ersetzt wird). Die parallelisierte Zusammenführung erfordert immer $ theta (n) $ memory unabhängig von k.

Nach dem, was ich geschrieben habe, ist klar, dass Quicksort oft nicht der schnellste Algorithmus ist, außer wenn die folgenden Bedingungen alle gelten:

1) Es gibt mehr als einige "wenige" mögliche Werte

2) Die zugrunde liegende Datenstruktur ist nicht verknüpft

3) Wir brauchen keine stabile Bestellung

4) Die Daten sind groß genug, dass die leichte suboptimale asymptotische Laufzeit eines Bitonischen Sortierers oder Batcher-Odd-Even-Mergesorts eintrifft

5) Die Daten sind nicht fast sortiert und bestehen nicht aus größeren, bereits sortierten Teilen

6) Wir können gleichzeitig auf die Datensequenz von mehreren Stellen zugreifen

7) {Speicherschreibungen sind besonders teuer (da dies der Hauptnachteil von Mergesort ist), soweit er den Algorithmus über die wahrscheinliche suboptimale Trennung eines Quicksorts hinaus verlangsamt. } oder {wir können nur $ theta ( log (n)) $ zusätzlicher Speicher haben, $ theta (n) $ ist zu viel (z. B. externer Speicher)}}

PS: Jemand muss mir bei der Formatierung des Textes helfen.

Die meisten Sendungen -Methoden müssen Daten in kurzen Schritten verschieben (z. B. Zusammenführungssortieren ändert sich lokal und verschmelzen dann dieses kleine Daten und verschmelzen dann eine größere.). Infolgedessen benötigen Sie viele Datenbewegungen, wenn Daten weit von ihrem Ziel entfernt sind.

Quicksort, auf der anderen Seite, versucht, Zahlen zu vertauschen, die im ersten Teil des Speichers und groß sind, mit Zahlen im zweiten Teil des Arrays und klein (wenn Sie $ a le b $ sortieren, die, die, die Das Argument ist im anderen Sinne gleich), so dass sie schnell in der Nähe ihres endgültigen Ziels zugewiesen werden.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit cs.stackexchange