Warum ist Quicksort in der Praxis besser als andere Sortieralgorithmen?

308

In einem Standard - Algorithmen Kurs werden wir gelehrt , dass quicksort ist im Durchschnitt und im schlimmsten Fall. Gleichzeitig werden andere Sortieralgorithmen untersucht, die im schlimmsten Fall (wie Mergesort und Heapsort ) und im besten Fall sogar eine lineare Zeit (wie Bubblesort ) sind, jedoch einige zusätzliche Speicheranforderungen haben.O ( n 2 ) O ( n log n )O(nlogn)O(n2)O(nlogn)

Nach einem kurzen Blick auf einige weitere Laufzeiten ist es selbstverständlich, dass Quicksort nicht so effizient sein sollte wie andere.

Bedenken Sie auch, dass die Schüler in grundlegenden Programmierkursen lernen, dass Rekursion im Allgemeinen nicht sehr gut ist, da sie zu viel Speicher usw. beanspruchen kann. Daher (und auch wenn dies kein wirkliches Argument ist) lässt dies den Schluss zu, dass Quicksort möglicherweise nicht geeignet ist Wirklich gut, weil es ein rekursiver Algorithmus ist.

Warum übertrifft dann Quicksort in der Praxis andere Sortieralgorithmen? Hat es mit der Struktur realer Daten zu tun ? Hat es mit der Funktionsweise des Speichers in Computern zu tun? Ich weiß, dass manche Erinnerungen viel schneller sind als andere, aber ich weiß nicht, ob dies der wahre Grund für diese kontraintuitive Leistung ist (im Vergleich zu theoretischen Schätzungen).


Update 1: Eine kanonische Antwort besagt, dass die Konstanten im des Durchschnittsfalls kleiner sind als die Konstanten in anderen -Algorithmen. Allerdings muss ich noch eine angemessene Begründung dafür finden, mit präzisen Berechnungen anstatt nur intuitiven Ideen.O ( n log n )O(nlogn)O(nlogn)

In jedem Fall scheint der wirkliche Unterschied, wie einige Antworten vermuten lassen, auf der Speicherebene zu liegen, wo Implementierungen die interne Struktur von Computern ausnutzen, indem zum Beispiel der Cache-Speicher schneller ist als der RAM-Speicher. Die Diskussion ist bereits interessant, aber ich würde gerne mehr Details zum Speichermanagement sehen, da es den Anschein hat, dass die Antwort damit zu tun hat.


Update 2: Es gibt mehrere Webseiten, die einen Vergleich von Sortieralgorithmen anbieten, von denen einige ausgefallener sind als andere (insbesondere sorting-algorithms.com ). Abgesehen davon, dass es sich um eine nette visuelle Hilfe handelt, beantwortet dieser Ansatz meine Frage nicht.

Janoma
quelle
2
Die Zusammenführungssortierung ist im schlimmsten Fall , und das Sortieren eines Arrays von Ganzzahlen, bei denen eine bekannte Grenze für die Größe der Ganzzahlen besteht, kann in -Zeit mit einer Zählsortierung durchgeführt werden. O ( n )O(nlogn)O(n)
Carl Mummert
13
sorting-algorithms.com bietet einen ziemlich gründlichen Vergleich von Sortieralgorithmen.
Joe
2
Anzeigenaktualisierung 1: Ich gehe davon aus, dass Sie entweder strenge Analysen oder realistische Annahmen treffen können. Beides habe ich nicht gesehen. Beispielsweise zählen die meisten formalen Analysen nur Vergleiche.
Raphael
9
Diese Frage hat kürzlich einen Wettbewerb für Programmierer gewonnen.SE !
Raphael
3
Interessante Frage. Ich habe vor einiger Zeit einige Tests mit zufälligen Daten und einer naiven Implementierung von Quick Sort und Merge Sort durchgeführt. Beide Algorithmen haben bei kleinen Datenmengen (bis zu 100000 Elemente) ziemlich gute Ergebnisse erzielt, aber nach dieser Zusammenführung erwies sich die Sortierung als viel besser. Dies scheint der allgemeinen Annahme zu widersprechen, dass schnelle Sortierung so gut ist und ich immer noch keine Erklärung dafür gefunden habe. Die einzige Idee, die ich mir einfallen lassen könnte, ist, dass der Begriff Schnellsortierung normalerweise für komplexere Algorithmen wie Intro-Sortierung verwendet wird und dass die naive Implementierung von Schnellsortierung mit zufälligem Pivot nicht so gut ist.
Giorgio

Antworten:

215

Kurze Antwort

Das Argument der Cache-Effizienz wurde bereits ausführlich erläutert. Darüber hinaus gibt es ein eigentümliches Argument, warum Quicksort schnell ist. Bei der Implementierung wie bei zwei „Kreuzungszeigern“, z. B. hier , haben die inneren Schleifen einen sehr kleinen Körper. Da dies der am häufigsten ausgeführte Code ist, zahlt sich dies aus.

Lange Antwort

Als erstes,

Der Average Case existiert nicht!

Da es sich in der Praxis häufig um Extremfälle handelt, die nur selten auftreten, wird eine Durchschnittsfallanalyse durchgeführt. Bei einer durchschnittlichen Fallanalyse wird jedoch von einer gewissen Verteilung der Eingaben ausgegangen ! Typisch für die Sortierung ist das Zufallspermutationsmodell (stillschweigend bei Wikipedia angenommen).

Warum -Notation?O

Das Verwerfen von Konstanten bei der Analyse von Algorithmen geschieht aus einem Hauptgrund: Wenn ich an exakten Laufzeiten interessiert bin, benötige ich (relative) Kosten aller beteiligten Grundoperationen (auch ohne Berücksichtigung von Caching-Problemen, Pipelining in modernen Prozessoren ...). Die mathematische Analyse kann zählen, wie oft jeder Befehl ausgeführt wird. Die Ausführungszeiten einzelner Befehle hängen jedoch von den Prozessordetails ab, z.

Es gibt zwei Möglichkeiten:

  1. Reparieren Sie ein Maschinenmodell.

    Dies geschieht in Don Knuths Buchreihe "Die Kunst der Computerprogrammierung" für einen künstlichen "typischen" Computer, den der Autor erfunden hat. In Band 3 finden Sie genaue durchschnittliche Fallergebnisse für viele Sortieralgorithmen, z

    • Quicksort:11.667(n+1)ln(n)1.74n18.74
    • Mergesort:12.5nln(n)
    • Heapsort: 16nln(n)+0.01n
    • Insertionsort: [ Quelle ]2.25n2+7.75n3ln(n) Laufzeiten mehrerer Sortieralgorithmen

    Diese Ergebnisse zeigen, dass Quicksort am schnellsten ist. Dies ist jedoch nur auf Knuths künstlichem Computer bewiesen. Dies bedeutet nicht unbedingt, dass Sie Ihren x86-PC verwenden. Beachten Sie auch , dass die Algorithmen beziehen sich unterschiedlich für kleine Eingänge:
    Laufzeiten mehrerer Sortieralgorithmen für kleine Eingaben
    [ Quelle ]

  2. Analysieren Sie abstrakte Grundoperationen .

    Bei der vergleichsbasierten Sortierung handelt es sich in der Regel um Swaps und Schlüsselvergleiche . In Robert Sedgewicks Büchern, zB „Algorithmen“ , wird dieser Ansatz verfolgt. Sie finden dort

    • Quicksort: Vergleiche und Swaps im Durchschnitt12nln(n)13nln(n)
    • Mergesort: Vergleiche, aber bis zu Array-Zugriffe (Mergesort ist nicht Swap-basiert, daher können wir das nicht zählen).8,66 n ln ( n )1.44nln(n)8.66nln(n)
    • Insertionsort: Vergleiche und Swaps im Durchschnitt.114n214n2

    Wie Sie sehen, können Algorithmen nicht ohne weiteres als exakte Laufzeitanalyse verglichen werden, die Ergebnisse sind jedoch unabhängig von Maschinendetails.

Andere Eingabeverteilungen

Wie oben erwähnt, beziehen sich Durchschnittsfälle immer auf eine bestimmte Eingabeverteilung, sodass andere als zufällige Permutationen in Betracht gezogen werden können. Zum Beispiel wurde für Quicksort mit gleichen Elementen geforscht und es gibt einen schönen Artikel über die Standardsortierfunktion in Java

Sebastian
quelle
8
Ergebnisse vom Typ 2. können durch Einfügen maschinenabhängiger Konstanten in Ergebnisse vom Typ 1. umgewandelt werden. Daher würde ich argumentieren, 2. ist ein überlegener Ansatz.
Raphael
2
@ Raffael +1. Ich nehme an, Sie gehen davon aus, dass maschinenabhängig auch implementierungsabhängig ist, oder? Ich meine, schnelle Maschine + schlechte Implementierung ist wahrscheinlich nicht sehr effizient.
Janoma
2
@Janoma Ich ging davon aus, dass der analysierte Algorithmus in sehr detaillierter Form angegeben wird (da die Analyse detailliert ist) und die Implementierung so genau wie möglich ist. Aber ja, die Implementierung würde auch einfließen.
Raphael
3
Tatsächlich ist die Typ-2-Analyse in der Praxis unterlegen. Reale Maschinen sind so kompliziert, dass die Ergebnisse von Typ 2 nicht in Typ 1 übersetzt werden können. Vergleichen Sie das mit Typ 1: Das Zeichnen von experimentellen Laufzeiten dauert 5 Minuten.
Jules
4
@Jules: "experimentelle Laufzeit aufzeichnen" ist nicht Typ 1; Es ist keine formale Analyse und nicht auf andere Maschinen übertragbar. Aus diesem Grund führen wir schließlich eine formale Analyse durch.
Raphael
78

Es gibt mehrere Punkte, die in Bezug auf diese Frage gemacht werden können.

Quicksort ist normalerweise schnell

O(n2)

n1O(nlogn)

Quicksort ist normalerweise schneller als die meisten Sorten

O(nlogn)O(n2)n

O(nlogn)O(nBlog(nB))B

Der Grund für diese Cache-Effizienz liegt darin, dass die Eingabe linear gescannt und die Eingabe linear partitioniert wird. Dies bedeutet, dass wir das Beste aus jeder Cache-Last machen können, indem wir jede Zahl, die wir in den Cache laden, lesen, bevor wir diesen Cache gegen einen anderen austauschen. Insbesondere ist der Algorithmus nicht Cache-fähig, was eine gute Cache-Leistung für jede Cache-Ebene ergibt, was ein weiterer Gewinn ist.

Die Cache - Effizienz konnte weiter auf verbessert werdenO(nBlogMB(nB))Mk

Quicksort ist normalerweise schneller als Mergesort

Bei diesem Vergleich geht es ausschließlich um konstante Faktoren (wenn wir den typischen Fall betrachten). Insbesondere besteht die Wahl zwischen einer suboptimalen Auswahl des Pivots für Quicksort und der Kopie der gesamten Eingabe für Mergesort (oder der Komplexität des Algorithmus, der zur Vermeidung dieses Kopiervorgangs erforderlich ist). Es stellt sich heraus, dass Ersteres effizienter ist: Es gibt keine Theorie dahinter, es ist einfach schneller.

nO(logn)O(n)

Beachten Sie zum Schluss, dass Quicksort etwas empfindlich gegenüber Eingaben ist, die zufällig in der richtigen Reihenfolge vorliegen. In diesem Fall können einige Auslagerungen übersprungen werden. Mergesort hat keine derartigen Optimierungen, was Quicksort im Vergleich zu Mergesort auch etwas schneller macht.

Verwenden Sie die Sortierung, die Ihren Anforderungen entspricht

Fazit: Kein Sortieralgorithmus ist immer optimal. Wählen Sie, was Ihren Bedürfnissen entspricht. Wenn Sie einen Algorithmus benötigen, der in den meisten Fällen am schnellsten ist, und es Ihnen nichts ausmacht, dass er in seltenen Fällen etwas langsam ist und Sie keine stabile Sortierung benötigen, verwenden Sie Quicksort. Verwenden Sie andernfalls den Algorithmus, der Ihren Anforderungen besser entspricht.

Alex ten Brink
quelle
3
Ihre letzte Bemerkung ist besonders wertvoll. Ein Kollege von mir analysiert derzeit Quicksort-Implementierungen unter verschiedenen Eingabeverteilungen. Einige von ihnen brechen beispielsweise für viele Duplikate zusammen.
Raphael
4
O(n2)
8
"[T] hier steckt keine Theorie dahinter, es ist einfach schneller." Diese Aussage ist aus wissenschaftlicher Sicht höchst unbefriedigend. Stellen Sie sich vor, Newton sagt: "Schmetterlinge fliegen hoch, Äpfel fallen herunter: Es gibt keine Theorie dahinter, Äpfel fallen einfach."
David Richerby
2
@Alex ten Brink, was meinst du mit "Insbesondere ist der Algorithmus Cache-vergessen "?
Hibou57
4
@David Richerby, "Diese Aussage ist aus wissenschaftlicher Sicht höchst unbefriedigend": Er kann nur Zeuge einer Tatsache sein, ohne vorzutäuschen, dass wir damit zufrieden sein sollten. Einige Algorithmusfamilien leiden unter einem Mangel an vollständiger Formalisierung. Hashing-Funktionen sind ein Beispielfall.
Hibou57
45

In einem der Programmier-Tutorials an meiner Universität haben wir die Schüler gebeten, die Leistung von QuickSort, Mergesort und Einfügesortierung mit der in Python integrierten list.sort (genannt Timsort ) zu vergleichen. Die experimentellen Ergebnisse haben mich zutiefst überrascht, da die integrierte list.sort-Funktion selbst bei Instanzen, bei denen es leicht zu einem Absturz von Quicksort und Mergesort kam, eine wesentlich bessere Leistung als andere Sortieralgorithmen erbrachte. Es ist also verfrüht zu folgern, dass die übliche Implementierung von Quicksort die beste in der Praxis ist. Aber ich bin mir sicher, dass es eine viel bessere Implementierung von QuickSort oder einer Hybridversion davon gibt.

Dies ist ein netter Blog-Artikel von David R. MacIver , der Timsort als eine Form von adaptivem Mergesort erklärt.

Dai
quelle
17
@Raphael Um es kurz zu machen, Timsort ist Merge-Sortierung für die Asymptotik plus Einfügesortierung für kurze Eingaben plus einige Heuristiken, um effizient mit Daten umzugehen, die gelegentlich bereits sortierte Bursts aufweisen (was in der Praxis häufig vorkommt). Dai: Zusätzlich zum Algorithmus list.sortprofitiert es von einer von Profis optimierten eingebauten Funktion. Bei einem faireren Vergleich wären alle Funktionen mit gleichem Aufwand in derselben Sprache geschrieben.
Gilles
1
@Dai: Sie könnten zumindest beschreiben, mit welchen Eingaben (bzw. deren Verteilung) unter welchen Umständen (wenig RAM, hat eine Implementierung parallelisiert, ...) Sie Ihre Ergebnisse erzielt haben.
Raphael
7
Wir haben eine Liste von Zufallszahlen getestet und teilweise sortiert, vollständig sortiert und umgekehrt sortiert. Es war ein Einführungskurs im ersten Jahr, es war also keine tiefe empirische Studie. Die Tatsache, dass es jetzt offiziell zum Sortieren von Arrays in Java SE 7 und auf der Android-Plattform verwendet wird, bedeutet jedoch etwas.
Dai
3
Dies wurde auch hier besprochen: cstheory.stackexchange.com/a/927/74
Jukka Suomela
34

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 auf Elemente am Anfang und Ende des Segments 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 Teil des Speichers ("Speicherort") wird in den Cache geladen. Und wenn Sie versuchen, auf das zweite Element zuzugreifen, befindet es sich (höchstwahrscheinlich) bereits im Cache, sodass es sehr schnell ist.

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

svick
quelle
5
Das ist eine umstrittene Erklärung: Mergesort ist auch Cache-freundlich.
Dmytro Korduban
2
Ich denke, diese Antwort ist im Grunde richtig, aber hier sind einige Details youtube.com/watch?v=aMnn0Jq0J-E
rgrig
3
wahrscheinlich ist auch die multiplikative Konstante für die durchschnittliche Komplexität der Fallzeit der schnellen Sortierung besser (unabhängig von dem Cache-Faktor, den Sie erwähnt haben).
Kaveh
1
Der Punkt, den Sie angesprochen haben, ist im Vergleich zu anderen guten Eigenschaften der schnellen Sortierung nicht so wichtig.
MMS
1
@Kaveh: "die multiplikative Konstante für die durchschnittliche Fallzeitkomplexität der schnellen Sortierung ist auch besser" Haben Sie irgendwelche Daten dazu?
Giorgio
29

Andere haben bereits gesagt, dass die asymptotische durchschnittliche Laufzeit von Quicksort (in der Konstante) besser ist als die anderer Sortieralgorithmen (in bestimmten Einstellungen).

O(nlogn)

Beachten Sie, dass es viele Varianten von Quicksort gibt (siehe zB Sedgewicks Dissertation). Sie funktionieren bei verschiedenen Eingabeverteilungen unterschiedlich (einheitlich, fast sortiert, fast umgekehrt sortiert, viele Duplikate, ...), und andere Algorithmen sind für einige möglicherweise besser.

k10

Raphael
quelle
20

O(nlgn)

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

Siehe auch:

Kaveh
quelle
3
@Janoma Dies ist eine Frage der Sprache und des Compilers, die Sie verwenden. Fast alle funktionalen Sprachen (ML, Lisp, Haskell) können Optimierungen vornehmen, die ein Anwachsen des Stacks verhindern, und intelligentere Compiler für imperative Sprachen können dasselbe tun (GCC, G ++ und ich glaube, MSVC tun dies alle). Die bemerkenswerte Ausnahme ist Java, das diese Optimierung niemals durchführen wird. Daher ist es in Java sinnvoll, Ihre Rekursion als Iteration umzuschreiben.
Rafe Kettler
4
@JD, Sie können die Tail Call-Optimierung nicht mit QuickSort verwenden (zumindest nicht vollständig), da es sich selbst zweimal aufruft. Sie können den zweiten Anruf, aber nicht den ersten Anruf optimieren.
Svick
1
@ Janoma, du brauchst die rekursive Implementierung nicht wirklich. Wenn Sie sich beispielsweise die Implementierung der Funktion qsort in C ansehen, werden keine rekursiven Aufrufe verwendet, und die Implementierung wird daher viel schneller.
Kaveh
1
Heapsort ist ebenfalls vorhanden. Warum ist QS oft schneller?
Kevin
6
23240
16

Θ(n2)Θ(nlogn)

Der zweite Grund ist, dass es eine in-placeSortierung durchführt und in Umgebungen mit virtuellem Speicher sehr gut funktioniert.

UPDATE :: (Nach den Kommentaren von Janoma und Svick)

Um dies besser zu veranschaulichen, möchte ich ein Beispiel mit Merge Sort (da Merge Sort der nächste weit verbreitete Sortieralgorithmus nach Quick Sort ist, denke ich) geben und Ihnen sagen, woher die zusätzlichen Konstanten kommen (nach meinem besten Wissen und warum ich denke) Schnelle Sortierung ist besser):

Betrachten Sie die folgende Sequenz:

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 genau hinschauen, wie die letzte Phase abläuft, werden die ersten 12 mit 8 verglichen, und die 8 ist kleiner, sodass sie zuerst ausgeführt wird. Jetzt ist 12 WIEDER im Vergleich zu 21 und 12 geht weiter und so weiter und so fort. Wenn Sie die endgültige Zusammenführung vornehmen, dh 4 Elemente mit 4 anderen Elementen, entstehen viele EXTRA-Vergleiche als Konstanten, die bei der schnellen Sortierung NICHT anfallen. Dies ist der Grund, warum eine schnelle Sortierung bevorzugt wird.

0x0
quelle
1
Aber was macht die Konstanten so klein?
Svick
1
@svick Da sie sortiert sind in-place, wird kein zusätzlicher Speicher benötigt.
0x0
Θ(nlgn)
15

Meine Erfahrung mit realen Daten ist, dass Quicksort eine schlechte Wahl ist . Quicksort funktioniert gut mit zufälligen Daten, aber reale Daten sind meistens nicht zufällig.

Im Jahr 2008 habe ich einen hängenden Softwarefehler gefunden, der auf die Verwendung von Quicksort zurückzuführen war. Eine Weile später schrieb ich einfache Implementierungen von Insertion Sort, QuickSort, Heap Sort und Merge Sort und testete diese. Meine Zusammenführungssortierung hat alle anderen bei der Arbeit an großen Datenmengen übertroffen.

Seitdem ist Merge Sort mein bevorzugter Sortieralgorithmus. Es ist elegant. Es ist einfach zu implementieren. Es ist eine stabile Sorte. Es degeneriert nicht wie Quicksort zu quadratischem Verhalten. Ich wechsle zu Insertion Sort, um kleine Arrays zu sortieren.

Bei vielen Gelegenheiten habe ich gedacht, dass eine bestimmte Implementierung überraschend gut für Quicksort geeignet ist, nur um herauszufinden, dass es sich tatsächlich nicht um Quicksort handelt. Manchmal wechselt die Implementierung zwischen Quicksort und einem anderen Algorithmus und manchmal wird überhaupt kein Quicksort verwendet. Beispielsweise verwenden die qsort () - Funktionen von GLibc die Sortierung nach Zusammenführung. Nur wenn die Zuweisung des Arbeitsbereichs fehlschlägt, wird auf die vorhandene QuickSort zurückgegriffen, die ein Codekommentar als "den langsameren Algorithmus" bezeichnet .

Bearbeiten: Programmiersprachen wie Java, Python und Perl verwenden ebenfalls die Zusammenführungssortierung oder genauer eine Ableitung wie Timsort oder die Zusammenführungssortierung für große Mengen und die Einfügungssortierung für kleine Mengen. (Java verwendet auch Dual-Pivot-QuickSort, das schneller ist als einfaches QuickSort.)

Erwan Legrand
quelle
Ich hatte etwas Ähnliches gesehen, weil wir ständig anhängten / zurückgingen, um Daten in einen Stapel bereits sortierter Daten einzufügen. Sie können dies im Durchschnitt umgehen, indem Sie eine zufällige Quicksortierung verwenden (und sich von einer seltenen und zufälligen furchtbar langsamen Sortierung überraschen lassen), oder Sie können eine immer langsamere Sortierung tolerieren, deren Fertigstellung niemals überraschend viel Zeit in Anspruch nimmt. Manchmal benötigen Sie auch Sortierstabilität. Java hat von einer Sortierung nach Zusammenführung zu einer Quicksort-Variante gewechselt.
Rob
@Rob Dies ist nicht korrekt. Java verwendet bis heute eine Variante von Mergesort (Timsort). Es wird auch eine Variante von Quicksort verwendet (Dual-Pivot-Quicksort).
Erwan Legrand
14

1 - Schnelle Sortierung ist vorhanden (außer einer konstanten Menge wird kein zusätzlicher Speicher benötigt.)

2 - Schnelles Sortieren ist einfacher zu implementieren als andere effiziente Sortieralgorithmen.

3 - Schnelles Sortieren hat kleinere konstante Faktoren in seiner Laufzeit als andere effiziente Sortieralgorithmen.

Update: Für die Zusammenführungssortierung müssen Sie einige "Zusammenführungsvorgänge" ausführen, für die zusätzliche Arrays erforderlich sind, um die Daten vor der Zusammenführung zu speichern. aber in der schnellen Art tun Sie nicht. Deshalb gibt es eine schnelle Sortierung. Es gibt auch einige zusätzliche Zusammenführungsvergleiche, die die konstanten Faktoren bei der Zusammenführungssortierung erhöhen.

MMS
quelle
3
Haben Sie gesehen an Ort und Stelle, iterativen Quicksort Implementierungen fortgeschritten? Das sind viele Dinge, aber nicht "einfach".
Raphael
2
Nummer 2 ist nicht beantwortet meine Frage überhaupt, und Nummern 1 und 3 angemessene Begründung brauchen, meiner Meinung nach .
Janoma
@ Raffael: Sie sind einfach. Es ist viel einfacher, eine schnelle direkte Sortierung mithilfe eines Arrays anstelle von Zeigern zu implementieren. Und es muss nicht iterativ sein, um an Ort und Stelle zu sein.
MMS
Die Arrays zum Zusammenführen sind nicht so schlecht. Sobald Sie einen Gegenstand von einem Quellstapel auf den Zielstapel verschoben haben, muss er nicht mehr dort sein. Wenn Sie dynamische Arrays verwenden, entsteht beim Zusammenführen ein konstanter Speicherbedarf.
Oskar Skog
@ 1 Mergesort kann ebenfalls vorhanden sein. @ 2 Was macht effizient aus? Ich mag das Sortieren von Zusammenführungen, weil es meiner Meinung nach sehr einfach und dennoch effizient ist. @ 3 Nicht relevant, wenn Sie große Datenmengen sortieren und der Algorithmus effizient implementiert werden muss.
Oskar Skog
11

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

Θ(log(n)2)Θ(nlog(n)2)

Θ(nk)Θ(nm)k=2#number_of_Possible_valuesm=#maximum_length_of_keys

3) Besteht die zugrunde liegende Datenstruktur aus verknüpften Elementen? Ja -> benutze immer "in place merge sort". Es gibt sowohl einfach zu implementierende, festgelegte Größen als auch adaptive (oder auch natürliche) Bottom-up-Zusammenführungsarten für verknüpfte Datenstrukturen, und da sie niemals das Kopieren der gesamten Daten in jedem Schritt erfordern und auch keine Rekursionen erfordern, sind sie es auch schneller als alle anderen allgemeinen vergleichsbasierten Sortierungen, sogar schneller als die schnelle Sortierung.

Θ(n)

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 -> Bitonische Sortierung oder Batcher Odd Even Mergesort verwenden. Gehe zu 1)

Θ(n)Θ(n2)Θ(nlog(n)2)Worst-Case-Laufzeiten sind bekannt, oder vielleicht versuchen Sie es mit Kammsortierung. Ich bin nicht sicher, ob Shell Sort oder Comb Sort in der Praxis einigermaßen gut funktionieren würden.

Θ(log(n))Θ(n)Θ(n)Θ(log(n))Θ(n2)Θ(n)Θ(n)Θ(log(n))Θ(nlog(n))

Θ(nlog(n))

Implementierungshinweise für quicksort:

Θ(n)Θ(log(n))Θ(nlogk(k1))

2) Es gibt Bottom-up-iterative Varianten von Quicksort, aber AFAIK, sie haben die gleichen asymptotischen Raum- und Zeitgrenzen wie die Top-down-Varianten, mit den zusätzlichen Nachteilen, dass sie schwierig zu implementieren sind (z. B. das explizite Verwalten einer Warteschlange). Ich habe die Erfahrung gemacht, dass diese für praktische Zwecke niemals in Betracht gezogen werden sollten.

Implementierungshinweise für Mergesort:

1) Bottom-Up-Mergesort ist immer schneller als Top-Down-Mergesort, da keine Rekursionsaufrufe erforderlich sind.

2) Die sehr naive Zusammenführungssortierung kann beschleunigt werden, indem ein Doppelpuffer verwendet und der Puffer umgeschaltet wird, anstatt die Daten nach jedem Schritt aus dem zeitlichen Array zurück zu kopieren.

3) Bei vielen realen Daten ist die adaptive Zusammenführung viel schneller als eine Zusammenführung mit fester Größe.

Θ(k)Θ(log(k))Θ(1)Θ(n)

Aus dem, was ich geschrieben habe, geht hervor, dass Quicksort oft nicht der schnellste Algorithmus ist, außer wenn die folgenden Bedingungen zutreffen:

1) Es gibt mehr als "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 geringfügig suboptimale asymptotische Laufzeit eines bitonischen Sortierers oder eines Batcher Odd Even Mergesort einsetzt

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

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

Θ(log(n))Θ(n)

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

Franki
quelle
(5): Die Sortierimplementierung von Apple überprüft zuerst einen Lauf in aufsteigender oder absteigender Reihenfolge sowohl am Anfang als auch am Ende des Arrays. Dies ist sehr schnell, wenn es nicht viele solcher Elemente gibt, und kann diese Elemente sehr effektiv handhaben, wenn es mehr als n / ln n von ihnen gibt. Wenn Sie zwei sortierte Arrays
verketten
8

Bei den meisten Sortierungsmethoden müssen die Daten in kurzen Schritten verschoben werden (z. B. führt das Zusammenführen der Sortierung Änderungen lokal durch, führt dann dieses kleine Datenelement zusammen und führt dann ein größeres zusammen ...). Infolgedessen benötigen Sie viele Datenbewegungen, wenn die Daten weit vom Ziel entfernt sind.

ab

fernand0
quelle
5
Dein Streit über Quicksort vs. Mergesort ist nicht schlagkräftig. Quicksort beginnt mit einem großen Zug und macht dann immer kleinere Züge (bei jedem Schritt etwa halb so groß). Die Zusammenführungssortierung beginnt mit einer kleinen Bewegung und führt dann immer größere Bewegungen aus (bei jedem Schritt ungefähr doppelt so groß). Dies bedeutet nicht, dass einer effizienter ist als der andere.
Gilles