Warum ist Quicksort in der Praxis besser als andere Sortieralgorithmen?

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

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.

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

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.

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 .

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.

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.