Warum ist Quicksort besser als Mergesort?

Diese Frage wurde mir während eines Interviews gestellt. Sie sind beide O (nlogn) und dennoch verwenden die meisten Leute Quicksort anstelle von Mergesort. Warum ist das so?

Quicksort hat eine O ( n ² ) Worst-Case-Laufzeit und eine O ( n log n ) durchschnittliche Case-Laufzeit. In vielen Szenarien ist es jedoch überlegen, die Sortierung zusammenzuführen, da viele Faktoren die Laufzeit eines Algorithmus beeinflussen und Quicksort gewinnt, wenn alle zusammen genommen werden.

Insbesondere bezieht sich die häufig zitierte Laufzeit von Sortieralgorithmen auf die Anzahl der Vergleiche oder die Anzahl der Swaps, die zum Sortieren der Daten erforderlich sind. Dies ist in der Tat ein gutes Maß für die Leistung, zumal es unabhängig vom zugrunde liegenden Hardware-Design ist. Andere Dinge - wie die Referenzlokalität (dh lesen wir viele Elemente, die sich wahrscheinlich im Cache befinden?) - spielen auf der aktuellen Hardware ebenfalls eine wichtige Rolle. Insbesondere Quicksort benötigt wenig zusätzlichen Speicherplatz und weist eine gute Cache-Lokalität auf. Dies macht es in vielen Fällen schneller als das Zusammenführen von Sortierungen.

Darüber hinaus ist es sehr einfach, die Worst-Case-Laufzeit von O ( n ² ) von QuickSort fast vollständig zu vermeiden, indem Sie eine geeignete Auswahl des Pivots treffen - beispielsweise eine zufällige Auswahl (dies ist eine hervorragende Strategie).

In der Praxis sind viele moderne Implementierungen von Quicksort (insbesondere libstdc ++ std::sort) tatsächlich Introsort , dessen theoretischer Worst-Case O ( n log n ) ist, genau wie Merge Sort. Dies wird erreicht, indem die Rekursionstiefe begrenzt und auf einen anderen Algorithmus ( Heapsort ) umgeschaltet wird, sobald log n überschritten wird .

Wie viele Leute bemerkt haben, ist die durchschnittliche Fallleistung für Quicksort schneller als für Mergesort. Aber das ist nur wahr , wenn Sie konstante Zeit davon aus bei Bedarf jedes Stück Speicher zuzugreifen.

Im RAM ist diese Annahme im Allgemeinen nicht schlecht (sie ist aufgrund von Caches nicht immer wahr, aber nicht schlecht). Allerdings , wenn Sie Ihre Datenstruktur groß genug , um zu leben , auf der Festplatte ist, dann wird quicksort getötet durch die Tatsache , dass Ihre durchschnittliche Scheibe etwas tut , wie 200 zufällig ausgewählte pro Sekunde sucht. Dieselbe Festplatte hat jedoch keine Probleme, Daten nacheinander Megabyte pro Sekunde zu lesen oder zu schreiben. Welches ist genau das, was Mergesort tut.

Wenn also Daten auf der Festplatte sortiert werden müssen, möchten Sie wirklich, wirklich eine Variation von Mergesort verwenden. (Im Allgemeinen sortieren Sie Unterlisten schnell und beginnen dann, sie oberhalb eines Größenschwellenwerts zusammenzuführen.)

Wenn Sie mit Datensätzen dieser Größe etwas zu tun haben, sollten Sie sich überlegen, wie Sie vermeiden können, auf der Festplatte zu suchen. Aus diesem Grund wird standardmäßig empfohlen, Indizes zu löschen, bevor große Datenmengen in Datenbanken geladen werden, und den Index später neu zu erstellen. Das Aufrechterhalten des Index während des Ladens bedeutet, ständig nach einer Festplatte zu suchen. Wenn Sie dagegen die Indizes löschen, kann die Datenbank den Index neu erstellen, indem Sie zuerst die zu behandelnden Informationen sortieren (natürlich unter Verwendung eines Mergesorts!) Und sie dann in eine BTREE-Datenstruktur für den Index laden. (BTREEs werden natürlich in Ordnung gehalten, sodass Sie einen aus einem sortierten Datensatz mit wenigen Suchvorgängen auf die Festplatte laden können.)

Es gab eine Reihe von Fällen, in denen ich durch das Verständnis, wie Festplattensuchen vermieden werden können, Datenverarbeitungsaufträge eher Stunden als Tage oder Wochen in Anspruch nehmen konnte.

Tatsächlich ist QuickSort O (n ² ). Die durchschnittliche Laufzeit des Falls beträgt O (nlog (n)), der schlechteste Fall jedoch O (n ² ). Dies tritt auf, wenn Sie es in einer Liste ausführen, die nur wenige eindeutige Elemente enthält. Die Randomisierung nimmt O (n). Dies ändert natürlich nichts an seinem schlimmsten Fall, sondern verhindert lediglich, dass ein böswilliger Benutzer Ihre Sortierung lange dauert.

QuickSort ist beliebter, weil es:

1. Ist vorhanden (MergeSort erfordert zusätzlichen Speicher, der linear zur Anzahl der zu sortierenden Elemente ist).
2. Hat eine kleine versteckte Konstante.

"Und doch verwenden die meisten Leute Quicksort anstelle von Mergesort. Warum ist das so?"

Ein psychologischer Grund, der nicht angegeben wurde, ist einfach, dass Quicksort klüger benannt ist. dh gutes Marketing.

Ja, Quicksort mit dreifacher Partitionierung ist wahrscheinlich einer der besten Sortieralgorithmen für allgemeine Zwecke, aber es kommt nicht darüber hinweg, dass die Sortierung "Schnell" viel leistungsfähiger klingt als die Sortierung "Zusammenführen".

Wie andere angemerkt haben, ist der schlimmste Fall von Quicksort O (n ^ 2), während Mergesort und Heapsort bei O (nlogn) bleiben. Im Durchschnitt sind jedoch alle drei O (nlogn); Sie sind also für die überwiegende Mehrheit der Fälle vergleichbar.

Was Quicksort im Durchschnitt besser macht, ist, dass die innere Schleife den Vergleich mehrerer Werte mit einem einzigen impliziert, während bei den beiden anderen beiden Begriffen für jeden Vergleich unterschiedlich sind. Mit anderen Worten, Quicksort führt halb so viele Lesevorgänge durch wie die beiden anderen Algorithmen. Bei modernen CPUs wird die Leistung stark von den Zugriffszeiten dominiert, sodass Quicksort letztendlich eine gute erste Wahl ist.

Ich möchte hinzufügen, dass von den drei bisher genannten Algorithmen (Mergesort, Quicksort und Heap-Sortierung) nur Mergesort stabil ist. Das heißt, die Reihenfolge ändert sich nicht für diejenigen Werte, die denselben Schlüssel haben. In einigen Fällen ist dies wünschenswert.

Aber um ehrlich zu sein, in praktischen Situationen brauchen die meisten Menschen nur eine gute durchschnittliche Leistung und Quicksort ist ... schnell =)

Alle Sortieralgorithmen haben ihre Höhen und Tiefen. Eine gute Übersicht finden Sie im Wikipedia-Artikel zum Sortieren von Algorithmen .

Aus dem Wikipedia-Eintrag zu Quicksort :

Quicksort konkurriert auch mit Mergesort, einem anderen rekursiven Sortieralgorithmus, jedoch mit dem Vorteil der Worst-Case-Laufzeit (nlogn). Mergesort ist im Gegensatz zu Quicksort und Heapsort eine stabile Sorte und kann problemlos an verknüpfte Listen und sehr große Listen angepasst werden, die auf langsam zugänglichen Medien wie Festplattenspeicher oder Netzwerkspeicher gespeichert sind. Obwohl Quicksort geschrieben werden kann, um mit verknüpften Listen zu arbeiten, leidet es häufig unter schlechten Pivot-Entscheidungen ohne wahlfreien Zugriff. Der Hauptnachteil von Mergesort besteht darin, dass beim Betrieb auf Arrays im besten Fall Θ (n) Hilfsraum benötigt wird, während die Variante von Quicksort mit In-Place-Partitionierung und Tail-Rekursion nur Θ (logn) Raum verwendet. (Beachten Sie, dass beim Zusammenführen von verknüpften Listen für Mergesort nur eine geringe, konstante Menge an Zusatzspeicher erforderlich ist.)

Mu! Quicksort ist nicht besser, es eignet sich gut für eine andere Art von Anwendung als Mergesort.

Mergesort ist eine Überlegung wert, wenn Geschwindigkeit von entscheidender Bedeutung ist, eine schlechte Leistung im ungünstigsten Fall nicht toleriert werden kann und zusätzlicher Speicherplatz verfügbar ist. 1

Sie sagten, dass sie «Sie sind beide O (nlogn) […]». Das ist falsch. «Quicksort verwendet im schlimmsten Fall etwa n ^ 2/2 Vergleiche.» 1 .

Die meiner Erfahrung nach wichtigste Eigenschaft ist jedoch die einfache Implementierung des sequentiellen Zugriffs, den Sie beim Sortieren verwenden können, wenn Sie Programmiersprachen mit dem imperativen Paradigma verwenden.

1 Sedgewick, Algorithmen

Quicksort ist der schnellste Sortieralgorithmus in der Praxis, weist jedoch eine Reihe von pathologischen Fällen auf, die dazu führen können, dass er genauso schlecht funktioniert wie O (n2).

Heapsort läuft garantiert in O (n * ln (n)) und benötigt nur begrenzten zusätzlichen Speicher. Es gibt jedoch viele Zitate von Tests in der realen Welt, die zeigen, dass Heapsort im Durchschnitt erheblich langsamer als QuickSort ist.

Die Erklärung von Wikipedia lautet:

In der Praxis ist Quicksort in der Praxis erheblich schneller als andere Θ (nlogn) -Algorithmen, da seine innere Schleife auf den meisten Architekturen effizient implementiert werden kann und in den meisten realen Daten Entwurfsentscheidungen getroffen werden können, die die Wahrscheinlichkeit minimieren, dass quadratische Zeit erforderlich ist .

Schnelle Sorte

Zusammenführen, sortieren

Ich denke, es gibt auch Probleme mit der für Mergesort benötigten Speichermenge (Ω (n)), die Quicksort-Implementierungen nicht haben. Im schlimmsten Fall haben sie dieselbe algorithmische Zeit, aber Mergesort erfordert mehr Speicherplatz.

Ich möchte zu den vorhandenen großartigen Antworten einige Berechnungen hinzufügen, wie QuickSort funktioniert, wenn es vom besten Fall abweicht, und wie wahrscheinlich dies ist. Ich hoffe, dass dies den Menschen hilft, ein wenig besser zu verstehen, warum der O (n ^ 2) -Fall nicht real ist Bedenken bei den komplexeren Implementierungen von QuickSort.

Abgesehen von Problemen mit wahlfreiem Zugriff gibt es zwei Hauptfaktoren, die sich auf die Leistung von QuickSort auswirken können. Beide hängen davon ab, wie der Pivot mit den zu sortierenden Daten verglichen wird.

1) Eine kleine Anzahl von Schlüsseln in den Daten. Ein Datensatz mit demselben Wert wird auf einem Vanilla 2-Partitions-QuickSort in n ^ 2-mal sortiert, da alle Werte außer der Pivot-Position jedes Mal auf einer Seite platziert werden. Moderne Implementierungen adressieren dies durch Methoden wie die Verwendung einer 3-Partitions-Sortierung. Diese Methoden werden in O (n) Zeit für einen Datensatz mit demselben Wert ausgeführt. Die Verwendung einer solchen Implementierung bedeutet also, dass eine Eingabe mit einer kleinen Anzahl von Schlüsseln tatsächlich die Leistungszeit verbessert und kein Problem mehr darstellt.

2) Eine extrem schlechte Pivot-Auswahl kann zu einer Worst-Case-Leistung führen. Im Idealfall ist der Drehpunkt immer so, dass 50% der Daten kleiner und 50% der Daten größer sind, sodass die Eingabe bei jeder Iteration in zwei Hälften geteilt wird. Dies gibt uns n Vergleiche und tauscht Zeiten log-2 (n) Rekursionen gegen O (n * logn) Zeit aus.

Inwieweit wirkt sich eine nicht ideale Pivot-Auswahl auf die Ausführungszeit aus?

Betrachten wir einen Fall, in dem der Pivot konsistent so gewählt wird, dass sich 75% der Daten auf einer Seite des Pivots befinden. Es ist immer noch O (n * logn), aber jetzt hat sich die Basis des Protokolls auf 1 / 0,75 oder 1,33 geändert. Die Beziehung in der Leistung beim Ändern der Basis ist immer eine Konstante, die durch log (2) / log (newBase) dargestellt wird. In diesem Fall beträgt diese Konstante 2,4. Diese Qualität der Pivot-Auswahl dauert also 2,4-mal länger als das Ideal.

Wie schnell wird das schlimmer?

Nicht sehr schnell, bis die Auswahl des Pivots (durchweg) sehr schlecht wird:

• 50% auf einer Seite: (Idealfall)
• 75% auf einer Seite: 2,4-mal so lang
• 90% auf einer Seite: 6,6 mal so lang
• 95% auf einer Seite: 13,5 mal so lang
• 99% auf einer Seite: 69 mal so lang

Wenn wir uns 100% auf einer Seite nähern, nähert sich der logarithmische Teil der Ausführung n und die gesamte Ausführung nähert sich asymptotisch O (n ^ 2).

In einer naiven Implementierung von QuickSort erzeugen Fälle wie ein sortiertes Array (für den Pivot des ersten Elements) oder ein Array mit umgekehrter Sortierung (für den Pivot des letzten Elements) zuverlässig eine Ausführungszeit im ungünstigsten Fall O (n ^ 2). Darüber hinaus können Implementierungen mit einer vorhersagbaren Pivot-Auswahl einem DoS-Angriff durch Daten ausgesetzt werden, die für die Ausführung im ungünstigsten Fall ausgelegt sind. Moderne Implementierungen vermeiden dies durch eine Vielzahl von Methoden, z. B. durch Randomisieren der Daten vor dem Sortieren, Auswählen des Medians von 3 zufällig ausgewählten Indizes usw. Mit dieser Randomisierung im Mix haben wir zwei Fälle:

• Kleiner Datensatz. Der schlimmste Fall ist vernünftigerweise möglich, aber O (n ^ 2) ist nicht katastrophal, da n klein genug ist, dass n ^ 2 ebenfalls klein ist.
• Großer Datensatz. Der schlimmste Fall ist theoretisch möglich, aber nicht in der Praxis.

Wie wahrscheinlich ist es, dass wir eine schreckliche Leistung sehen?

Die Chancen sind verschwindend gering . Betrachten wir eine Art von 5.000 Werten:

Unsere hypothetische Implementierung wählt einen Pivot unter Verwendung eines Medians von 3 zufällig ausgewählten Indizes. Wir werden Pivots im Bereich von 25% bis 75% als "gut" und Pivots im Bereich von 0% bis 25% oder 75% bis 100% als "schlecht" betrachten. Wenn Sie die Wahrscheinlichkeitsverteilung anhand des Medians von 3 zufälligen Indizes betrachten, hat jede Rekursion eine Chance von 11/16, einen guten Pivot zu erhalten. Lassen Sie uns zwei konservative (und falsche) Annahmen treffen, um die Mathematik zu vereinfachen:

1. Gute Drehpunkte sind immer genau zu 25% / 75% aufgeteilt und arbeiten im Idealfall 2,4 *. Wir bekommen nie einen idealen Split oder einen Split, der besser als 25/75 ist.

2. Schlechte Drehpunkte sind immer der schlimmste Fall und tragen im Wesentlichen nichts zur Lösung bei.

Unsere QuickSort-Implementierung stoppt bei n = 10 und wechselt zu einer Einfügesortierung. Daher benötigen wir 22 Pivot-Partitionen mit 25% / 75%, um die Eingabe mit 5.000 Werten so weit aufzuschlüsseln. (10 * 1.333333 ^ 22> 5000) Oder wir benötigen 4990 Worst-Case-Pivots. Denken Sie daran, dass, wenn wir zu irgendeinem Zeitpunkt 22 gute Drehpunkte sammeln, die Sortierung abgeschlossen ist. Der schlimmste Fall oder etwas in der Nähe erfordert daher extrem viel Pech. Wenn wir 88 Rekursionen benötigen würden, um tatsächlich die 22 guten Drehpunkte zu erreichen, die erforderlich sind, um auf n = 10 zu sortieren, wäre dies ein 4 * 2,4 * Idealfall oder etwa das 10-fache der Ausführungszeit des Idealfalls. Wie wahrscheinlich ist es, dass wir nach 88 Rekursionen nicht die erforderlichen 22 guten Drehpunkte erreichen?

Binomiale Wahrscheinlichkeitsverteilungen können darauf antworten, und die Antwort ist ungefähr 10 ^ -18. (n ist 88, k ist 21, p ist 0,6875) Ihr Benutzer wird in der 1 Sekunde, die zum Klicken auf [SORTIEREN] benötigt wird, ungefähr tausendmal häufiger vom Blitz getroffen, als zu sehen, dass die Sortierung von 5.000 Elementen schlechter läuft als 10 * Idealfall. Diese Chance wird kleiner, wenn der Datensatz größer wird. Hier sind einige Array-Größen und ihre entsprechenden Chancen, länger als 10 * zu laufen, ideal:

• Array von 640 Elementen: 10 ^ -13 (erfordert 15 gute Drehpunkte aus 60 Versuchen)
• Array von 5.000 Elementen: 10 ^ -18 (erfordert 22 gute Pivots von 88 Versuchen)
• Array von 40.000 Elementen: 10 ^ -23 (erfordert 29 gute Drehpunkte von 116)

Denken Sie daran, dass dies mit zwei konservativen Annahmen geschieht, die schlechter als die Realität sind. Die tatsächliche Leistung ist also noch besser, und das Gleichgewicht der verbleibenden Wahrscheinlichkeit ist näher am Ideal als nicht.

Schließlich können, wie andere bereits erwähnt haben, selbst diese absurd unwahrscheinlichen Fälle durch Umschalten auf eine Heap-Sortierung beseitigt werden, wenn der Rekursionsstapel zu tief geht. Das TLDR ist also, dass für gute Implementierungen von QuickSort der schlimmste Fall nicht wirklich existiert, da er ausgearbeitet wurde und die Ausführung in O (n * logn) Zeit abgeschlossen ist.

Warum ist Quicksort gut?

• QuickSort nimmt im schlimmsten Fall N ^ 2 und im Durchschnitt NlogN. Der schlimmste Fall tritt auf, wenn Daten sortiert werden. Dies kann durch zufälliges Mischen gemildert werden, bevor die Sortierung gestartet wird.
• QuickSort benötigt keinen zusätzlichen Speicher, der durch Zusammenführungssortierung belegt wird.
• Wenn der Datensatz groß ist und identische Elemente vorhanden sind, wird die Komplexität von Quicksort durch die Verwendung einer 3-Wege-Partition verringert. Je mehr identische Artikel vorhanden sind, desto besser ist die Sortierung. Wenn alle Elemente identisch sind, wird in linearer Zeit sortiert. [Dies ist die Standardimplementierung in den meisten Bibliotheken]

Ist Quicksort immer besser als Mergesort?

Nicht wirklich.

• Mergesort ist stabil, Quicksort jedoch nicht. Wenn Sie also Stabilität in der Ausgabe benötigen, würden Sie Mergesort verwenden. Stabilität ist in vielen praktischen Anwendungen erforderlich.
• Speicher ist heutzutage billig. Wenn der von Mergesort verwendete zusätzliche Speicher für Ihre Anwendung nicht kritisch ist, kann die Verwendung von Mergesort keinen Schaden anrichten.

Hinweis: In Java verwendet die Funktion Arrays.sort () Quicksort für primitive Datentypen und Mergesort für Objektdatentypen. Da Objekte Speicher-Overhead verbrauchen, ist ein zusätzlicher Overhead für Mergesort aus Sicht der Leistung möglicherweise kein Problem.

Referenz : Sehen Sie sich die QuickSort-Videos von Woche 3, Princeton Algorithms Course bei Coursera an

Quicksort ist NICHT besser als Mergesort. Mit O (n ^ 2) (der schlimmste Fall, der selten auftritt) ist Quicksort möglicherweise weitaus langsamer als das O (nlogn) der Zusammenführungssorte. Quicksort hat weniger Overhead, daher ist es bei kleinen n und langsamen Computern besser. Computer sind heute jedoch so schnell, dass der zusätzliche Overhead eines Mergesorts vernachlässigbar ist und das Risiko eines sehr langsamen QuickSorts in den meisten Fällen den unbedeutenden Overhead eines Mergesorts bei weitem überwiegt.

Darüber hinaus hinterlässt ein Mergesort Elemente mit identischen Schlüsseln in ihrer ursprünglichen Reihenfolge, ein nützliches Attribut.

Die Antwort würde sich leicht in Richtung Quicksort ändern, wenn Änderungen mit DualPivotQuickSort für primitive Werte vorgenommen werden. Es wird in JAVA 7 zum Sortieren in java.util.Arrays verwendet

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

Die JAVA7-Implementierung finden Sie hier - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Weitere großartige Lektüre auf DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Bei der Zusammenführungssortierung lautet der allgemeine Algorithmus:

1. Sortieren Sie das linke Unterarray
2. Sortieren Sie das richtige Unterarray
3. Führen Sie die 2 sortierten Unterarrays zusammen

Auf der obersten Ebene werden beim Zusammenführen der beiden sortierten Unterarrays N Elemente behandelt.

Eine Stufe darunter beinhaltet jede Iteration von Schritt 3 den Umgang mit N / 2 Elementen, aber Sie müssen diesen Vorgang zweimal wiederholen. Sie haben es also immer noch mit 2 * N / 2 == N Elementen zu tun.

Eine Ebene darunter führen Sie 4 * N / 4 == N Elemente usw. zusammen. Jede Tiefe im rekursiven Stapel beinhaltet das Zusammenführen der gleichen Anzahl von Elementen über alle Aufrufe für diese Tiefe.

Betrachten Sie stattdessen den Schnellsortierungsalgorithmus:

1. Wählen Sie einen Drehpunkt
2. Platzieren Sie den Drehpunkt an der richtigen Stelle im Array, mit allen kleineren Elementen links und größeren Elementen rechts
3. Sortieren Sie das linke Subarray
4. Sortieren Sie das rechte Subarray

Auf der obersten Ebene handelt es sich um ein Array der Größe N. Anschließend wählen Sie einen Drehpunkt aus, setzen ihn an die richtige Position und können ihn für den Rest des Algorithmus vollständig ignorieren.

Eine Ebene darunter haben Sie es mit 2 Sub-Arrays zu tun, die eine kombinierte Größe von N-1 haben (dh den früheren Drehpunkt subtrahieren). Sie wählen für jedes Subarray einen Drehpunkt aus, der bis zu 2 zusätzliche Drehpunkte umfasst.

Eine Ebene darunter haben Sie es aus den gleichen Gründen wie oben mit 4 Sub-Arrays mit der kombinierten Größe N-3 zu tun.

Dann N-7 ... Dann N-15 ... Dann N-32 ...

Die Tiefe Ihres rekursiven Stapels bleibt ungefähr gleich (logN). Bei der Zusammenführungssortierung handelt es sich immer um eine Zusammenführung von N-Elementen auf jeder Ebene des rekursiven Stapels. Beim schnellen Sortieren verringert sich jedoch die Anzahl der Elemente, mit denen Sie sich befassen, wenn Sie den Stapel hinuntergehen. Wenn Sie beispielsweise die Tiefe in der Mitte des rekursiven Stapels betrachten, ist die Anzahl der Elemente, mit denen Sie sich befassen, N - 2 ^ ((logN) / 2)) == N - sqrt (N).

Haftungsausschluss: Beim Zusammenführen ist die rekursive Tiefe genau logN, da Sie das Array jedes Mal in zwei genau gleiche Blöcke aufteilen. Beim schnellen Sortieren ist die Tiefe Ihres rekursiven Stapels möglicherweise etwas größer als logN, da es unwahrscheinlich ist, dass sich Ihr Drehpunkt genau in der Mitte des Arrays befindet. Ich habe nicht nachgerechnet, welche Rolle dieser Faktor und der oben beschriebene Faktor tatsächlich für die Komplexität des Algorithmus spielen.

Im Gegensatz zur Zusammenführungssortierung verwendet die Schnellsortierung kein zusätzliches Leerzeichen. Während Merge Sort einen Hilfsraum O (n) verwendet. Merge Sort hat jedoch die Worst-Case-Zeitkomplexität von O (nlogn), während die Worst-Case-Komplexität von Quick Sort O (n ^ 2) ist, was passiert, wenn das Array bereits sortiert ist.

Quicksort hat eine bessere durchschnittliche Fallkomplexität, aber in einigen Anwendungen ist es die falsche Wahl. Quicksort ist anfällig für Denial-of-Service-Angriffe. Wenn ein Angreifer die zu sortierende Eingabe auswählen kann, kann er leicht eine Menge erstellen, die die Zeitkomplexität von o (n ^ 2) im ungünstigsten Fall benötigt.

Die durchschnittliche Fallkomplexität und die Worst-Case-Komplexität von Mergesort sind gleich und weisen als solche nicht das gleiche Problem auf. Diese Eigenschaft der Zusammenführungssortierung macht es auch zur überlegenen Wahl für Echtzeitsysteme - gerade weil es keine pathologischen Fälle gibt, die dazu führen, dass es viel, viel langsamer läuft.

Aus diesen Gründen bin ich ein größerer Fan von Mergesort als von Quicksort.

Das ist schwer zu sagen. Das schlechteste von MergeSort ist n (log2n) -n + 1, was genau ist, wenn n gleich 2 ^ k ist (das habe ich bereits bewiesen). Und für jedes n liegt es zwischen (n lg n - n +) 1) und (n lg n + n + O (lg n)). Aber für quickSort ist nlog2n am besten (auch n ist gleich 2 ^ k). Wenn Sie Mergesort durch quickSort teilen, ist es gleich eins, wenn n unendlich ist Es ist, als ob der schlechteste Fall von MergeSort besser ist als der beste Fall von QuickSort. Warum verwenden wir Quicksort? Aber denken Sie daran, MergeSort ist nicht vorhanden, es benötigt 2n Speicherplatz. Und MergeSort muss auch viele Array-Kopien erstellen, die wir ausführen Nicht in die Analyse des Algorithmus einbeziehen. Mit einem Wort, MergeSort ist wirklich schneller als Quicksort in Theroy, aber in Wirklichkeit müssen Sie den Speicherplatz berücksichtigen, die Kosten für die Array-Kopie, die Fusion ist langsamer als die schnelle Sortierung Experiment, bei dem mir von der Zufallsklasse 1000000 Stellen in Java gegeben wurden,und es dauerte 2610 ms per Mergesort, 1370 ms per Quicksort.

Schnelle Sortierung ist der schlechteste Fall O (n ^ 2), jedoch führt der durchweg ausgefallene Durchschnittsfall eine Zusammenführungssortierung durch. Jeder Algorithmus ist O (nlogn), aber Sie müssen sich daran erinnern, dass wir bei Big O die Faktoren mit geringerer Komplexität weglassen. Die schnelle Sortierung hat erhebliche Verbesserungen gegenüber der Sortierung beim Zusammenführen, wenn es um konstante Faktoren geht.

Die Zusammenführungssortierung erfordert auch O (2n) -Speicher, während eine schnelle Sortierung an Ort und Stelle durchgeführt werden kann (nur O (n) erforderlich). Dies ist ein weiterer Grund, warum die schnelle Sortierung im Allgemeinen der Zusammenführungssortierung vorgezogen wird.

Zusatzinformation:

Der schlimmste Fall einer schnellen Sortierung tritt auf, wenn der Drehpunkt schlecht gewählt ist. Betrachten Sie das folgende Beispiel:

[5, 4, 3, 2, 1]

Wenn der Drehpunkt als kleinste oder größte Zahl in der Gruppe ausgewählt wird, wird die schnelle Sortierung in O (n ^ 2) ausgeführt. Die Wahrscheinlichkeit, das Element auszuwählen, das sich in den größten oder kleinsten 25% der Liste befindet, beträgt 0,5. Dies gibt dem Algorithmus eine Chance von 0,5, ein guter Pivot zu sein. Wenn wir einen typischen Pivot-Auswahlalgorithmus verwenden (z. B. Auswahl eines zufälligen Elements), haben wir eine Chance von 0,5, für jede Auswahl eines Pivots einen guten Pivot auszuwählen. Bei großen Sammlungen beträgt die Wahrscheinlichkeit, immer einen schlechten Drehpunkt zu wählen, 0,5 * n. Basierend auf dieser Wahrscheinlichkeit ist eine schnelle Sortierung für den durchschnittlichen (und typischen) Fall effizient.

Dies ist eine ziemlich alte Frage, aber da ich mich in letzter Zeit mit beiden befasst habe, sind hier meine 2c:

Der Sortierbedarf für das Zusammenführen erfordert durchschnittlich ~ N log N Vergleiche. Für bereits (fast) sortierte sortierte Arrays ergibt sich ein Wert von 1/2 N log N, da wir beim Zusammenführen (fast) immer 1/2 N mal den "linken" Teil auswählen und dann einfach die rechten 1/2 N Elemente kopieren. Außerdem kann ich spekulieren, dass bereits sortierte Eingaben den Verzweigungsprädiktor des Prozessors zum Leuchten bringen, aber fast alle Verzweigungen richtig erraten, wodurch Pipeline-Stillstände verhindert werden.

Eine schnelle Sortierung erfordert im Durchschnitt ~ 1,38 N log N Vergleiche. Es profitiert nicht stark von bereits sortierten Arrays in Bezug auf Vergleiche (jedoch in Bezug auf Swaps und wahrscheinlich in Bezug auf Verzweigungsvorhersagen innerhalb der CPU).

Meine Benchmarks für ziemlich moderne Prozessoren zeigen Folgendes:

Wenn die Vergleichsfunktion eine Rückruffunktion ist (wie in der Implementierung von qsort () libc), ist Quicksort bei zufälliger Eingabe um 15% langsamer als Mergesort und bei bereits sortiertem Array für 64-Bit-Ganzzahlen um 30%.

Wenn der Vergleich jedoch kein Rückruf ist, ist meine Erfahrung, dass Quicksort Mergesort um bis zu 25% übertrifft.

Wenn Ihr (großes) Array jedoch nur sehr wenige eindeutige Werte aufweist, gewinnt die Zusammenführungssortierung in jedem Fall gegenüber der Quicksortierung.

Das Fazit lautet also vielleicht: Wenn der Vergleich teuer ist (z. B. Rückruffunktion, Vergleichen von Zeichenfolgen, Vergleichen vieler Teile einer Struktur, meistens mit einem zweiten Drittel "Wenn", um einen Unterschied zu machen), sind Sie wahrscheinlich besser mit Zusammenführungssortierung. Für einfachere Aufgaben ist Quicksort schneller.

Das heißt, alles zuvor Gesagte ist wahr: - Quicksort kann N ^ 2 sein, aber Sedgewick behauptet, dass eine gute randomisierte Implementierung mehr Chancen hat, dass ein Computer, der eine Sortierung durchführt, von einem Blitz getroffen wird, als N ^ 2 - Mergesort benötigt zusätzlichen Speicherplatz

Wenn ich mit beiden Sortieralgorithmen experimentiert habe und die Anzahl der rekursiven Aufrufe gezählt habe, hat Quicksort durchweg weniger rekursive Aufrufe als Mergesort. Dies liegt daran, dass Quicksort Pivots hat und Pivots nicht in den nächsten rekursiven Aufrufen enthalten sind. Auf diese Weise kann Quicksort schneller zum rekursiven Basisfall gelangen als Mergesort.

Dies ist eine häufig gestellte Frage in den Interviews, dass Quicksort trotz der besseren Worst-Case-Leistung der Zusammenführungssortierung als besser als die Zusammenführungssortierung angesehen wird, insbesondere bei großen Eingaben. Es gibt bestimmte Gründe, aus denen Quicksort besser ist:

1- Hilfsraum: schnelle Sortierung ist ein In-Place-Sortieralgorithmus. In-Place-Sortierung bedeutet, dass kein zusätzlicher Speicherplatz für die Sortierung erforderlich ist. Die Zusammenführungssortierung erfordert andererseits ein temporäres Array, um die sortierten Arrays zusammenzuführen, und ist daher nicht vorhanden.

2- Schlimmster Fall: Der schlimmste Fall von Quicksort O(n^2)kann durch die Verwendung einer randomisierten Quicksortierung vermieden werden. Es kann leicht mit hoher Wahrscheinlichkeit vermieden werden, indem der richtige Drehpunkt gewählt wird. Wenn Sie durch Auswahl des richtigen Pivot-Elements ein durchschnittliches Fallverhalten erzielen, wird die Leistung verbessert und es wird so effizient wie beim Sortieren.

3- Referenzort: Insbesondere Quicksort weist eine gute Cache-Lokalität auf, wodurch es in vielen Fällen schneller als die Zusammenführungssortierung ist, wie in einer virtuellen Speicherumgebung.

4- Schwanzrekursion : QuickSort ist Schwanzrekursion, Mergesortierung nicht. Eine rekursive Schwanzfunktion ist eine Funktion, bei der der rekursive Aufruf das letzte ist, was von der Funktion ausgeführt wird. Die rekursiven Schwanzfunktionen werden als besser angesehen als die rekursiven Nicht-Schwanzfunktionen, da die Schwanzrekursion vom Compiler optimiert werden kann.

Obwohl beide in derselben Komplexitätsklasse sind, bedeutet dies nicht, dass beide dieselbe Laufzeit haben. Quicksort ist normalerweise schneller als Mergesort, nur weil es einfacher ist, eine straffe Implementierung zu codieren, und die damit verbundenen Vorgänge schneller ablaufen können. Weil dieser Quicksort im Allgemeinen schneller ist, verwenden die Leute ihn anstelle von Mergesort.

Jedoch! Ich persönlich verwende oft Mergesort oder eine Quicksort-Variante, die sich zu Mergesort verschlechtert, wenn Quicksort schlecht abschneidet. Merken. Quicksort ist im Durchschnitt nur O (n log n) . Der schlimmste Fall ist O (n ^ 2)! Mergesort ist immer O (n log n). In Fällen, in denen Echtzeitleistung oder Reaktionsfähigkeit ein Muss sind und Ihre Eingabedaten möglicherweise aus einer böswilligen Quelle stammen, sollten Sie keine einfache Quicksortierung verwenden.

Wenn alle Dinge gleich sind, würde ich erwarten, dass die meisten Leute das verwenden, was am bequemsten verfügbar ist, und das ist in der Regel qsort (3). Abgesehen davon ist bekannt, dass Quicksort auf Arrays sehr schnell ist, genau wie Mergesort die häufigste Wahl für Listen ist.

Ich frage mich, warum es so selten ist, Radix zu sehen oder Eimersorten . Sie sind O (n), zumindest in verknüpften Listen, und es ist nur eine Methode erforderlich, um den Schlüssel in eine Ordnungszahl umzuwandeln. (Strings und Floats funktionieren einwandfrei.)

Ich denke, der Grund hat damit zu tun, wie Informatik unterrichtet wird. Ich musste meinem Dozenten für Algorithmusanalyse sogar zeigen, dass es tatsächlich möglich war, schneller als O (n log (n)) zu sortieren. (Er hatte den Beweis , dass man nicht Vergleich Art schneller als O (n log (n)), was wahr ist.)

In anderen Nachrichten können Floats als Ganzzahlen sortiert werden, aber Sie müssen die negativen Zahlen danach umdrehen.

Bearbeiten: Tatsächlich ist hier eine noch bösartigere Methode zum Sortieren von Floats als Ganzzahlen: http://www.stereopsis.com/radix.html . Beachten Sie, dass der Bit-Flipping-Trick unabhängig davon verwendet werden kann, welchen Sortieralgorithmus Sie tatsächlich verwenden ...

Kleine Ergänzungen zu Quick vs Merge-Sortierungen.

Es kann auch von der Art der Sortierung der Elemente abhängen. Wenn der Zugriff auf Elemente, das Austauschen und Vergleichen keine einfachen Operationen sind, wie das Vergleichen von Ganzzahlen im Ebenenspeicher, kann die Zusammenführungssortierung ein vorzuziehender Algorithmus sein.

Zum Beispiel sortieren wir Elemente mithilfe des Netzwerkprotokolls auf dem Remote-Server.

Auch in benutzerdefinierten Containern wie "verknüpfte Liste" ist das schnelle Sortieren kein Vorteil.
1. Sortierung auf verknüpfter Liste zusammenführen, keinen zusätzlichen Speicher benötigen. 2. Der schnelle Zugriff auf Elemente erfolgt nicht sequentiell (im Speicher).

Die schnelle Sortierung ist ein In-Place-Sortieralgorithmus und daher besser für Arrays geeignet. Die Zusammenführungssortierung erfordert andererseits zusätzlichen Speicher von O (N) und ist besser für verknüpfte Listen geeignet.

Im Gegensatz zu Arrays können wir in der Liste "Gefällt mir" Elemente in der Mitte mit O (1) Leerzeichen und O (1) Zeit einfügen. Daher kann die Zusammenführungsoperation in der Zusammenführungssortierung ohne zusätzlichen Leerzeichen implementiert werden. Das Zuweisen und Aufheben der Zuweisung von zusätzlichem Speicherplatz für Arrays wirkt sich jedoch nachteilig auf die Laufzeit der Zusammenführungssortierung aus. Die Zusammenführungssortierung begünstigt auch die verknüpfte Liste, da auf Daten nacheinander ohne viel zufälligen Speicherzugriff zugegriffen wird.

Eine schnelle Sortierung erfordert andererseits viel zufälligen Speicherzugriff, und mit einem Array können wir direkt auf den Speicher zugreifen, ohne dass die von verknüpften Listen geforderten Durchläufe erforderlich sind. Auch die schnelle Sortierung bei Verwendung für Arrays weist eine gute Referenzlokalität auf, da Arrays zusammenhängend im Speicher gespeichert werden.

Obwohl die durchschnittliche Komplexität beider Sortieralgorithmen O (NlogN) ist, verwenden Benutzer für normale Aufgaben normalerweise ein Array zur Speicherung. Aus diesem Grund sollte die schnelle Sortierung der Algorithmus der Wahl sein.

BEARBEITEN: Ich habe gerade herausgefunden, dass der schlechteste / beste / durchschnittliche Fall der Zusammenführungssortierung immer nlogn ist, aber die schnelle Sortierung kann von n2 (schlechtester Fall, wenn Elemente bereits sortiert sind) bis nlogn (durchschnittlicher / bester Fall, wenn Pivot das Array immer in zwei Teile teilt) variieren Hälften).

Berücksichtigen Sie sowohl die zeitliche als auch die räumliche Komplexität. Für Zusammenführungssortierung: Zeitkomplexität: O (nlogn), Raumkomplexität: O (nlogn)

Für die schnelle Sortierung: Zeitkomplexität: O (n ^ 2), Raumkomplexität: O (n)

Jetzt gewinnen beide in jeweils einem Szenario. Mit einem zufälligen Pivot können Sie jedoch die Zeitkomplexität der Schnellsortierung fast immer auf O (nlogn) reduzieren.

Daher wird in vielen Anwendungen die schnelle Sortierung anstelle der Zusammenführungssortierung bevorzugt.

Wenn ich in c / c ++ Land keine stl-Container verwende, verwende ich meistens Quicksort, da es in die Laufzeit integriert ist, Mergesort jedoch nicht.

Daher glaube ich, dass dies in vielen Fällen einfach der Weg des geringsten Widerstands ist.

Darüber hinaus kann die Leistung beim schnellen Sortieren viel höher sein, wenn der gesamte Datensatz nicht in den Arbeitssatz passt.

Einer der Gründe ist philosophischer. Quicksort ist Top-> Down-Philosophie. Mit n zu sortierenden Elementen gibt es n! Möglichkeiten. Mit 2 Partitionen von m & nm, die sich gegenseitig ausschließen, sinkt die Anzahl der Möglichkeiten um mehrere Größenordnungen. m! * (nm)! ist um mehrere Ordnungen kleiner als n! allein. stell dir 5 vor! vs 3! * 2!. 5! hat 10 mal mehr Möglichkeiten als 2 Partitionen von je 2 & 3. und extrapoliere auf 1 Million Fakultät gegen 900K! * 100K! Anstatt sich also Gedanken über die Einrichtung einer Reihenfolge innerhalb eines Bereichs oder einer Partition zu machen, sollten Sie die Reihenfolge in Partitionen auf einer breiteren Ebene festlegen und die Möglichkeiten innerhalb einer Partition verringern. Jede früher innerhalb eines Bereichs festgelegte Reihenfolge wird später gestört, wenn sich die Partitionen selbst nicht gegenseitig ausschließen.

Jeder Bottom-up-Order-Ansatz wie Merge Sort oder Heap Sort ist wie ein Worker- oder Employee-Ansatz, bei dem frühzeitig mit dem Vergleichen auf mikroskopischer Ebene begonnen wird. Diese Ordnung geht jedoch verloren, sobald später ein Element dazwischen gefunden wird. Diese Ansätze sind sehr stabil und äußerst vorhersehbar, erfordern jedoch eine gewisse zusätzliche Arbeit.

Quick Sort ist wie ein Management-Ansatz, bei dem man sich anfangs nicht um eine Bestellung kümmert, sondern nur darum, ein breites Kriterium ohne Rücksicht auf die Bestellung zu erfüllen. Dann werden die Partitionen eingegrenzt, bis Sie einen sortierten Satz erhalten. Die eigentliche Herausforderung in Quicksort besteht darin, eine Partition oder ein Kriterium im Dunkeln zu finden, wenn Sie nichts über die zu sortierenden Elemente wissen. Aus diesem Grund müssen wir entweder einige Anstrengungen unternehmen, um einen Medianwert zu finden, oder zufällig 1 oder einen willkürlichen "Manager" -Ansatz auswählen. Das Finden eines perfekten Medians kann einen erheblichen Aufwand bedeuten und führt erneut zu einem dummen Bottom-up-Ansatz. Also sagt Quicksort nur einen zufälligen Drehpunkt und hofft, dass er irgendwo in der Mitte liegt oder arbeitet daran, einen Median von 3, 5 oder etwas mehr zu finden, um einen besseren Median zu finden, plant aber nicht, perfekt zu sein und nicht. Verschwenden Sie keine Zeit bei der Erstbestellung. Das scheint gut zu funktionieren, wenn Sie Glück haben oder sich manchmal auf n ^ 2 verschlechtern, wenn Sie keinen Median erhalten, sondern nur eine Chance nutzen. Auf jeden Fall sind Daten zufällig. Recht. Daher stimme ich dem logischen Top->-Down-Ansatz von Quicksort mehr zu und es stellt sich heraus, dass die Chance, die es für die Auswahl und Vergleiche von Pivots bietet, die früher gespeichert werden, öfter besser zu funktionieren scheint als jeder akribische und gründliche stabile Bottom-Up-Ansatz wie Zusammenführen, sortieren. Aber Vergleiche, die früher gespeichert werden, scheinen öfter besser zu funktionieren als jeder akribische und gründliche stabile Bottom-Up-Ansatz wie das Zusammenführen. Aber Vergleiche, die früher gespeichert werden, scheinen öfter besser zu funktionieren als jeder akribische und gründliche stabile Bottom-Up-Ansatz wie das Zusammenführen. Aber