Warum ist Quicksort in der Praxis besser als andere Sortieralgorithmen?

31

Dies ist ein Repost einer Frage zu cs.SE von Janoma . Volle Credits und Beute für ihn oder cs.SE.

In einem Standardkurs über Algorithmen wird uns beigebracht, dass Quicksort im Durchschnitt O (n log n) und im schlimmsten Fall O (n²) ist. Gleichzeitig werden andere Sortieralgorithmen untersucht, die im schlimmsten Fall (wie Mergesort und Heapsort ) O (n log n) und im besten Fall (wie Bubblesort ) sogar eine lineare Zeit sind, jedoch einige zusätzliche Speicheranforderungen aufweisen.

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).

Raphael
quelle
3
Die Quicksort-Reputation stammt aus einer Zeit, in der kein Cache vorhanden war.
Programmierer
9
"Warum übertrifft Quicksort in der Praxis andere Sortieralgorithmen?" Sicher, dass das wahr ist? Zeigen Sie uns die tatsächliche Implementierung, auf die Sie sich mit dieser Aussage beziehen, und die Community teilt Ihnen mit, warum sich diese bestimmte Implementierung so verhält, wie sie sich verhält. Alles andere wird zu wilden Vermutungen über nicht existierende Programme führen.
Doc Brown
1
@DocBrown: Viele Quicksort-Implementierungen (oder Varianten davon) werden in vielen Bibliotheken ausgewählt, wohl weil sie die beste Leistung erbringen (das hoffe ich). Vielleicht hat der Algorithmus etwas an sich , das Quicksort unabhängig von der Implementierung schnell macht .
Raphael
1
Jemand muss dies der Vollständigkeit halber sagen, also werde ich: Quicksort ist (normalerweise) nicht stabil. Aus diesem Grund möchten Sie es möglicherweise nicht verwenden. Aus diesem Grund ist Ihre Standardsortierung möglicherweise auch dann keine Quicksort-Sortierung, wenn Sie dies wünschen.
Ralph Chapin
1
@Raphael: Was oft als schnelle Sortierung bezeichnet wird, ist tatsächlich eine Variation wie die Intro-Sortierung (verwendet, afaik, in der C ++ - Standardbibliothek), nicht die reine schnelle Sortierung.
Giorgio,

Antworten:

21

Ich würde nicht zustimmen, dass Quicksort in der Praxis besser ist als andere Sortieralgorithmen.

Für die meisten Zwecke ist Timsort die Mischung aus Mergesort- / Einfügesortierung, bei der die Tatsache ausgenutzt wird, dass die von Ihnen sortierten Daten häufig fast sortiert oder umgekehrt sortiert beginnen.

Die einfachste Quicksorte (kein zufälliger Pivot) behandelt diesen potenziell häufigen Fall als O (N ^ 2) (reduziert auf O (N lg N) mit zufälligen Pivots), während TimSort diese Fälle in O (N) behandeln kann.

Gemäß diesen Benchmarks in C #, in denen die integrierte Quicksort-Funktion mit TimSort verglichen wird, ist Timsort in den meist sortierten Fällen erheblich schneller und in den Zufallsdaten etwas schneller, und TimSort wird besser, wenn die Vergleichsfunktion besonders langsam ist. Ich habe diese Benchmarks nicht wiederholt und würde mich nicht wundern, wenn QuickSort TimSort für eine Kombination von Zufallsdaten leicht schlagen würde oder wenn etwas Skurriles in der eingebauten Sortierung von C # (basierend auf QuickSort) es verlangsamt. TimSort bietet jedoch deutliche Vorteile, wenn Daten teilweise sortiert werden können, und entspricht hinsichtlich der Geschwindigkeit in etwa der Quicksortierung, wenn die Daten nicht teilweise sortiert werden.

TimSort hat auch den zusätzlichen Vorteil, dass es im Gegensatz zu QuickSort eine stabile Sorte ist. Der einzige Nachteil von TimSort ist, dass bei der üblichen (schnellen) Implementierung O (N) gegenüber O (lg N) Speicher verwendet wird.

Dr. Jimbob
quelle
18

Die schnelle Sortierung wird als schneller angesehen, da der Koeffizient kleiner als jeder andere bekannte Algorithmus ist. Es gibt keinen Grund oder Beweis dafür, es wurde lediglich kein Algorithmus mit einem kleineren Koeffizienten gefunden. Es ist wahr, dass andere Algorithmen auch O ( n log n ) -Zeit haben, aber in der realen Welt ist der Koeffizient auch wichtig.

Beachten Sie, dass die Sortierung beim Einfügen kleiner Daten (die Sortierung, die als O ( n 2 ) betrachtet wird) aufgrund der Art der mathematischen Funktionen schneller ist. Dies hängt von den spezifischen Koeffizienten ab, die von Maschine zu Maschine variieren. (Am Ende läuft wirklich nur die Montage.) Manchmal ist eine Mischung aus Schnell- und Einfügesortierung meiner Meinung nach die schnellste in der Praxis.

Ramzi Kahil
quelle
7
+ Richtig. Die Lehrer müssen sich der Tatsache bewusster sein (und ich war ein Lehrer), dass konstante Faktoren um Größenordnungen variieren können. Die Fähigkeit zur Leistungsoptimierung ist also wirklich wichtig, unabhängig von Big-O. Das Problem ist, dass sie weiterhin gprof unterrichten , nur weil sie den Punkt im Lehrplan überwinden müssen, der um 180 Grad falsch ist.
Mike Dunlavey
2
„Dafür gibt es keinen Grund oder einen Beweis“: Sicher gibt es das. Wenn Sie tief genug graben, werden Sie einen Grund finden.
Gilles 'SO- hör auf böse zu sein'
2
@B Seven: um vieles zu vereinfachen ... für einen O (n log n) Sortieralgorithmus gibt es (n log n) Iterationen der Sortierschleife, um n Elemente zu sortieren. Der Koeffizient gibt an, wie lange jeder Zyklus der Schleife dauert. Wenn n wirklich groß ist (mindestens Tausende), ist der Koeffizient nicht so wichtig wie O (), auch wenn der Koeffizient sehr groß ist. Aber wenn n klein ist, ist der Koeffizient wichtig - und kann das Wichtigste sein, wenn Sie nur 10 Elemente sortieren.
Matt Gallagher
4
@MikeDunlavey - ein gutes Beispiel ist, dass das Bauen der Pyramiden O (n) ist, während das Sortieren Ihrer Fotos von ihnen O (n ln n) ist, aber was ist schneller!
Martin Beckett
2
Es gibt garantierte O (n log n) -Algorithmen wie Heapsort und Mergesort, so dass Quicksort im asymptotischen Worst-Case nicht einmal so schnell ist wie die besten. In der Praxis eignen sich einige Quicksort-Varianten jedoch hervorragend. "Der Koeffizient ist kleiner" zu sagen ist wie "es ist schneller, weil es schneller ist". Warum sind die konstanten Faktoren so klein? Ein wichtiger Grund ist, dass Quicksort in Bezug auf die Lokalität sehr gut ist - es nutzt Caches sehr gut. Mergesort hat auch eine gute Lokalität, aber es ist sehr schwierig, dies vor Ort zu tun.
Steve314
16

Quicksort übertrifft nicht alle anderen Sortieralgorithmen. Beispielsweise übertrifft die Bottom-Up-Heap-Sortierung ( Wegener 2002 ) die Quicksort- Sortierung bei angemessenen Datenmengen und ist auch ein direkter Algorithmus. Es ist auch einfach zu implementieren (zumindest nicht schwerer als einige optimierte Quicksort-Varianten).

Es ist einfach nicht so bekannt und man findet es nicht in vielen Lehrbüchern, was möglicherweise erklärt, warum es nicht so beliebt ist wie Quicksort.

Doc Brown
quelle
+1: Ich habe einige Tests durchgeführt und die Sortierung beim Zusammenführen war definitiv besser als die schnelle Sortierung für große Arrays (> 100000 Elemente). Heap-Sortierung war etwas schlechter als Merge-Sortierung (Merge-Sortierung benötigt jedoch mehr Speicher). Ich denke, was die Leute als schnelle Sortierung bezeichnen, ist oft eine Variation, die als Intro-Sortierung bezeichnet wird: schnelle Sortierung, die auf Heap-Sortierung zurückgreift, wenn die Rekursionstiefe eine bestimmte Grenze überschreitet.
Giorgio
@ Giorgio: quicksort kann in gewisser Weise modifiziert werden, um es zu verbessern, siehe zum Beispiel hier: algs4.cs.princeton.edu/23quicksort Haben Sie diese Verbesserungen versucht?
Doc Brown
Interessant, können Sie einen Verweis auf ein Buch \ site speichern, um mehr darüber zu lesen? (vorzugsweise ein Buch)
Ramzi Kahil
@Martin: meinst du etwa Bottom-Up Heapsort? Nun, ich habe oben einen Hinweis gegeben. Wenn Sie eine kostenlose Ressource möchten, hat die deutsche Wikipedia einen Artikel darüber ( de.wikipedia.org/wiki/BottomUp-Heapsort ). Auch wenn Sie kein Deutsch sprechen, können Sie das C99-Beispiel trotzdem lesen.
Doc Brown
7

Sie sollten sich nicht nur auf den schlimmsten Fall und die zeitliche Komplexität konzentrieren. Es geht eher um Durchschnitt als um das Schlimmste, und es geht um Zeit und Raum.

Schnelle Sorte:

  • hat eine durchschnittliche zeitliche Komplexität von Θ ( n log n );
  • kann mit einer Raumkomplexität von Θ (log n ) implementiert werden ;

Berücksichtigen Sie auch, dass die große O- Notation keine Konstanten berücksichtigt, aber in der Praxis macht es einen Unterschied, ob der Algorithmus einige Male schneller ist. Θ ( n log n ) bedeutet, dass der Algorithmus in K  n  log ( n ) ausgeführt wird, wobei K konstant ist. Quicksort ist der Vergleich-Sortieralgorithmus mit der niedrigsten K .

vartec
quelle
1
@ Gilles: Es hat einen niedrigen K-Wert, weil es ein einfacher Algorithmus ist.
Vartec
5
WTF? Das ergibt keinen Sinn. Die Einfachheit eines Algorithmus steht in keinem Zusammenhang mit seiner Laufgeschwindigkeit. Die Auswahlsortierung ist einfacher als die Schnellsortierung, was sie nicht schneller macht.
Gilles 'SO- hör auf böse zu sein'
1
@Gilles: Auswahlsortierung ist in jedem Fall O (n ^ 2) (schlechteste, durchschnittliche und beste). Es ist also egal, wie einfach es ist. Quicksort ist O (n log n) für den Durchschnittsfall, und unter allen Algos mit O (n log n) ist es das einfachste.
Vartec
1
@Gilles: Wenn andere Dinge gleich sind, hilft die Einfachheit der Leistung. Angenommen, Sie vergleichen zwei Algorithmen, für die jeweils (K n log n) Iterationen der jeweiligen inneren Schleifen durchgeführt werden: Der Algorithmus, der weniger Aufgaben pro Schleife ausführen muss, hat einen Leistungsvorteil.
Kommensturm
1
@comingstorm: So formuliert ist deine Aussage eine Tautologie, aber sie bezieht sich nicht auf "Einfachheit". Es gibt zum Beispiel kompliziertere Varianten von Quicksort (Fallunterschiede!), Die zu einer geringeren Laufzeit führen (sowohl in der Theorie als auch in der Praxis).
Raphael
5

Quicksort ist häufig eine gute Wahl, da es relativ schnell und einfach zu implementieren ist.

Wenn Sie es ernst meinen, große Datenmengen sehr schnell zu sortieren, sind Sie mit einigen Variationen von MergeSort wahrscheinlich besser dran. Dies kann dazu genutzt werden, externen Speicher zu nutzen, mehrere Threads oder sogar Prozesse zu verwenden, ist jedoch für den Code nicht trivial.

James Anderson
quelle
1

Die tatsächliche Leistung von Algorithmen hängt von der Plattform, der Sprache, dem Compiler, der Aufmerksamkeit des Programmierers für Implementierungsdetails, dem spezifischen Optimierungsaufwand usw. ab. Daher ist der "konstante Faktor-Vorteil" von Quicksort nicht sehr genau definiert - es handelt sich um eine subjektive Beurteilung auf der Grundlage der derzeit verfügbaren Tools und eine grobe Schätzung des "äquivalenten Implementierungsaufwands" durch denjenigen, der tatsächlich die vergleichende Leistungsstudie durchführt. .

Ich glaube jedoch, dass Quicksort eine gute Leistung (für zufällige Eingaben) erbringt, weil es einfach ist und weil seine rekursive Struktur relativ cachefreundlich ist. Da der schlimmste Fall jedoch leicht auszulösen ist, muss die praktische Verwendung einer Quicksort-Software komplexer sein, als es in der Beschreibung des Lehrbuchs angegeben ist: Modifizierte Versionen wie Introsort.

Mit der Zeit, wenn sich die dominante Plattform ändert, können verschiedene Algorithmen ihren (schlecht definierten) relativen Vorteil gewinnen oder verlieren. Herkömmliche Erkenntnisse zur relativen Leistung können dieser Verschiebung durchaus hinterherhinken. Wenn Sie sich also nicht sicher sind, welcher Algorithmus für Ihre Anwendung am besten geeignet ist, sollten Sie beide implementieren und testen.

kommendes Gewitter
quelle
Ich denke, die "kleinere Konstante", auf die sich andere beziehen, ist die in der formalen Analyse, dh die Anzahl der Vergleiche oder Swaps. Dies ist sehr gut definiert, es ist jedoch unklar, wie sich dies auf die Laufzeit auswirkt. Ein Kollege recherchiert derzeit tatsächlich darüber.
Raphael
Mein Eindruck war, dass es um allgemeine Leistung ging, aber ich würde mich auch nicht darauf verlassen. Sie haben jedoch Recht: Wenn Ihr Vergleich besonders teuer ist, können Sie die Anzahl der erwarteten Vergleiche
nachschlagen
1
Aus dem Grund, den Sie angeben, ist es im Allgemeinen nicht sinnvoll, über die Gesamtleistung (zeitlich) zu sprechen, da zu viele Details berücksichtigt werden. Der Grund für die Zählung nur ausgewählter Operationen liegt nicht darin, dass sie teuer sind, sondern dass sie "am häufigsten auftreten" "im landau - notation (big - oh) sinne, also zählt man die asymptotiker. Sobald Sie Konstanten und / oder Laufzeit berücksichtigen, ist diese Strategie viel weniger interessant.
Raphael
Eine gute Implementierung von QuickSort wird so kompiliert, dass Ihre Pivot-Werte so lange in einem CPU-Register verbleiben, wie sie benötigt werden. Dies ist oft genug, um eine theoretisch schnellere Sortierung mit vergleichbaren Big-O-Zeiten zu übertreffen.
Dan Lyons
Unterschiedliche Sortieralgorithmen haben unterschiedliche Eigenschaften in Bezug auf die Anzahl der Vergleiche und die Anzahl der Austauschvorgänge. Und @DanLyons merkt an, dass eine typische Sortierung in einer Bibliothek ihre Vergleiche über vom Benutzer bereitgestellte Funktionen durchführt und es ziemlich schwierig ist, Werte in Registern über viele Funktionsaufrufe hinweg zu halten.
Pointy