Warum ist quicksort besser als Mergesort?

StackOverflow https://stackoverflow.com/questions/70402

Frage

Ich habe diese Frage in einem Interview gefragt. Sie sind beide O (n log n) und doch die meisten Leute benutzen Quicksort statt Mergesort. Warum das?

War es hilfreich?

Lösung

Quicksort hat O ( n 2 ) Worst-Case-Laufzeit und O ( n lügen n ) Durchschnitt Fall der Laufzeit. Es ist jedoch überlegen Art in vielen Szenarien zu fusionieren, weil viele Faktoren einen Algorithmus der Laufzeit beeinflussen, und, wenn sie alle zusammen nehmen, quicksort gewinnt aus.

Insbesondere die oft zitierte Laufzeit von Algorithmen Sortierung bezieht sich auf die Anzahl der Vergleiche oder die Anzahl der Swaps notwendig auszuführen, um die Daten zu sortieren. Dies ist in der Tat ein gutes Maß für die Leistung, zumal es von dem zugrunde liegenden Hardware-Design unabhängig ist. Aber auch andere Dinge - wie zum Beispiel Referenzlokalität (das heißt lesen wir viele Elemente, die wahrscheinlich im Cache sind?) - auch eine wichtige Rolle auf aktuelle Hardware spielen. Quicksort insbesondere erfordert wenig zusätzlichen Platz und zeigt eine gute Cache-Lokalität, und dies macht es als schneller Mergesort in vielen Fällen.

Darüber hinaus ist es sehr einfach quicksort die Worst-Case-Laufzeit von O ( n 2 ) zu vermeiden, fast vollständig durch eine geeignete Wahl des Dreh mit - wie Kommissionierung sie zufällig (dies ist eine ausgezeichnete Strategie).

In der Praxis viele moderne Implementierungen von quicksort (insbesondere libstdc ++ 's std::sort) sind eigentlich Introsort , deren theoretischen Worst-case-O ( n log n ), gleich wie Mergesort. Es erreicht dies durch die Rekursion Tiefe zu beschränken, und auf einen anderen Algorithmus Schalt ( Heapsort ), sobald es überschreitet log n .

Andere Tipps

Wie viele Menschen festgestellt haben, ist die durchschnittliche Fall Leistung für quicksort ist schneller als mergesort. Aber das ist nur wahr, wenn Sie konstante Zeit davon aus bei Bedarf jedes Stück Speicher zuzugreifen.

In RAM diese Annahme ist in der Regel nicht allzu schlecht (es wegen des Cache-Speichers nicht immer wahr ist, aber es ist nicht so schlimm). Allerdings, wenn Sie Ihre Datenstruktur groß genug ist, auf der Festplatte zu leben, dann quicksort bekommt getötet durch die Tatsache, dass Ihre durchschnittliche Scheibe etwas tut, wie 200 zufällig ausgewählte pro Sekunde sucht. Aber die gleiche Festplatte hat keine Probleme beim Lesen oder Schreiben Megabyte pro Sekunde von Daten sequentiell. Welches ist genau das, was mergesort der Fall ist.

Deshalb, wenn Daten auf der Festplatte sortiert werden muss, die Sie wirklich, wirklich wollen, eine gewisse Variation auf mergesort verwenden. (In der Regel Sie QuickSort Sublisten, dann beginnen sie zusammen über einige Größenschwelle zu verschmelzen.)

Darüber hinaus, wenn Sie zu tun haben, alles mit Datensätzen von dieser Größe denken, hart, wie sucht auf der Festplatte zu vermeiden. Zum Beispiel ist dies, warum ist es Standard-Beratung, die Sie Indizes, bevor Sie große Datenlasten in Datenbanken löschen und dann den Index später wieder aufzubauen. Die Aufrechterhaltung des Index während der Ladeeinrichtung, ständig auf der Suche auf der Festplatte. Im Gegensatz dazu, wenn Sie die Indizes fallen, dann kann die Datenbank, den Index neu erstellen, indem zuerst die Informationen Sortierung behandelt werden (einen mergesort natürlich mit!) Und dann in eine BTREE Datenstruktur für den Index zu laden. (BTREEs werden, um natürlich gehalten, so dass Sie kann man von einer sortierten Datenmenge laden mit wenigen sucht auf der Festplatte.)

Es gab eine Reihe von Gelegenheiten, wo das Verständnis, wie Scheibe zu vermeiden sucht hat lassen Sie mich Datenverarbeitungsaufträge nehmen Stunden machen, statt Tagen oder Wochen.

Eigentlich QuickSort ist O (n 2 ). Sein Durchschnitt Fall Laufzeit ist O (nlog (n)), aber seine worst-case O (n 2 ) ist, die auftritt, wenn Sie führen Sie es auf einer Liste, die einige einzigartige Elemente enthält. Randomisierung nimmt O (n). Natürlich ist dies nicht den schlimmsten Fall nicht ändert, sondern verhindert nur einen böswilligen Benutzer Ihre Art eine lange Zeit von zu machen.

QuickSort ist beliebt, weil es:

  1. Ist in-place (MergeSort erfordert zusätzliche Speicher linear Anzahl der Elemente sortiert werden).
  2. Hat eine kleine versteckte Konstante ist.

"und doch die meisten Leute benutzen Quicksort statt Mergesort. Warum ist das?"

Ein psychologischer Grund, nicht gegeben ist einfach, dass Quicksort mehr ist geschickt benannt. dh gutes Marketing.

Ja, Quicksort mit triple partioning ist wahrscheinlich eines der besten Allzweck-Sortieralgorithmen, aber Theres kein Weg über die Tatsache, dass „Quick“ Art klingt viel mächtiger als „Merge“ sortieren.

Wie andere erwähnt haben, schlimmster Fall von Quicksort ist O (n ^ 2), während mergesort und Heapsort bei O (n log n) zu bleiben. Auf den durchschnittlichen Fall, aber alle drei sind O (n log n); so dass sie für die überwiegende Mehrheit der Fälle vergleichbar sind.

Was macht Quicksort besser im Durchschnitt ist, dass die innere Schleife mehr Werte mit einem einzigen implizierten Vergleich, während auf der anderen Seite zwei beiden Begriffe für jeden Vergleich unterschiedlich sind. Mit anderen Worten, tut Quicksort halb so viele wie die beiden anderen Algorithmen liest. Auf modernen CPUs wird die Leistung stark von Zugriffszeiten dominiert, so dass am Ende Quicksort endet eine große erste Wahl zu sein.

Ich möchte, dass der drei Algorithmen, so weit (mergesort, quicksort und Heap-Art) erwähnt hinzufügen nur mergesort stabil ist. Das heißt, dass der Auftrag nicht für diese Werte ändern, die die gleichen Schlüssel haben. In einigen Fällen ist dies wünschenswert.

Aber, ehrlich gesagt, in praktischen Situationen die meisten Leute brauchen nur gute durchschnittliche Leistung und quicksort ist ... quick =)

Alle Sortieralgorithmen haben ihre Höhen und Tiefen. Siehe Wikipedia-Artikel für Sortieralgorithmen für einen guten Überblick.

der Wikipedia-Eintrag auf Quicksort :

  

Quicksort konkurriert auch mit   mergesort, eine andere rekursive Art   Algorithmus, aber mit dem Vorteil der   Worst-Case-Θ (n log n) Laufzeit.   Mergesort ist eine stabile Art, im Gegensatz zu   quicksort und Heapsort und kann sein   leicht angepasst auf verbunden zu bedienen   Listen und sehr große Listen gespeichert auf   slow-to-Zugangsmedien wie Festplatten   Lagerung oder Network Attached Storage.   Obwohl quicksort geschrieben werden kann   arbeiten auf verkettete Listen, wird es oft   leiden unter schlechten Dreh Entscheidungen ohne   Direktzugriff. Der Hauptnachteil   von mergesort ist, dass, wenn der Betrieb   auf Arrays erfordert es Θ (n) Hilfs   Raum im besten Fall, während der   Variante von Quicksort mit in-place   Partitionierung und Endrekursion Anwendungen   nur Θ (log n) Raum. (Beachten Sie, dass, wenn   auf verkettete Listen arbeiten, mergesort   nur erfordert eine kleine, konstante Menge   von Zusatzspeicher.)

Mu! Quicksort ist nicht besser, es für eine andere Art der Anwendung gut geeignet ist, als mergesort.

  

Mergesort ist eine Überlegung wert, wenn die Geschwindigkeit des Wesens ist, schlecht Worst-Case-Leistung kann nicht toleriert werden, und mehr Platz zur Verfügung steht. 1

Sie haben erklärt, dass sie «Sie sind beide O (n log n) [...]». Das ist falsch. «Quicksort verwendet etwa n ^ 2/2 Vergleiche im schlimmsten Fall.» 1 .

Doch die wichtigste Eigenschaft nach meiner Erfahrung ist die einfache Implementierung von sequenziellem Zugriff Sie verwenden können, während des Sortieren, wenn Programmiersprachen mit dem Imperativ Paradigma.

1 Sedgewick, Algorithmen

Quicksort ist der schnellste Sortieralgorithmus in der Praxis aber hat eine Reihe von pathologischen Fällen, dass es so schlecht wie O ausführen machen (n2).

Heapsort garantiert in O (n * ln (n)) und benötigt nur endlich zusätzliche Speicher laufen. Aber es gibt viele Zitate von realen Welt Tests, die zeigen, dass Heapsort ist deutlich langsamer als Quicksort im Durchschnitt.

Wikipedia Erklärung ist:

  

Normalerweise ist quicksort deutlich in der Praxis schneller als anderer Θ (n log n) Algorithmen, weil seine innere Schleife effizient auf den meisten Architekturen implementiert wird, und in den meisten realen Daten ist es möglich, Design-Entscheidungen zu treffen, die die Wahrscheinlichkeit minimieren erfordern quadratische Zeit.

Quicksort

Mergesort

Ich glaube, es gibt auch Probleme mit der Menge an Speicher für Mergesort benötigt (die Ω (n)), dass quicksort Implementierungen nicht haben. Im schlimmsten Fall sind sie die gleiche Menge an algorithmischer Zeit, aber mergesort erfordert mehr Speicher.

Quicksort ist nicht besser als Mergesort. Mit O (n ^ 2) (ungünstigster Fall, die selten geschieht), ist quicksort potenziell weit langsamer als die O (n log n) des Mergesort. Quicksort hat weniger Overhead, so mit kleinen n und langsamen Computern, ist es besser. Aber Computer sind so schnell heute, dass der zusätzliche Aufwand eines mergesort vernachlässigbar ist, und das Risiko eines sehr langsamen quicksort weit schwerer wiegt als die unbedeutende Overhead eines mergesort in den meisten Fällen.

Darüber hinaus ist eine mergesort verläßt Elemente mit identischen Schlüsseln in ihrer ursprünglichen Reihenfolge, ein nützliches Attribut.

Ich mag die bestehenden großen Antworten etwas Mathematik über hinzufügen, wie QuickSort durchführt, wenn aus bestem Fall divergierenden und wie wahrscheinlich das ist, was ich hoffe, die Menschen helfen, ein wenig besser verstehen, warum die O (n ^ 2) Fall nicht von echten Sorge in den anspruchsvolleren Implementierungen von QuickSort.

Außerhalb des Direktzugriffsproblems gibt es zwei Hauptfaktoren, die die Leistung von QuickSort auswirken können, und sie sind beide damit zusammen, wie der Schwenk vergleicht die Daten sortiert werden.

1) Eine kleine Anzahl von Tasten in den Daten. Ein Datensatz von alle den gleichen Wert wird n ^ 2 Mal auf einer Vanille 2-Partition QuickSort da alle Werte mit Ausnahme der Schwenkstelle sortieren in auf der einen Seite jeweils platziert sind. Moderne Implementierungen adressieren diese durch Verfahren wie eine 3-Partition Art verwenden. Diese Methoden ausführen auf einem Datensatz von alle den gleichen Wert in O (n) Zeit. So eine Implementierung solcher verwendet bedeutet, dass ein Eingang mit einer kleinen Anzahl von Tasten tatsächlich Leistungszeit verbessert und ist nicht mehr ein Problem.

2) Extrem schlechte Dreh Auswahl kann schlimmste Fall Leistung führen. Im Idealfall wird der Schwenk immer so sein, dass 50% der Daten kleiner und 50% größer ist die Daten, so dass der Eingang in der Hälfte während jeder Iteration wird aufgebrochen wird. Dies gibt uns n Vergleiche und Swaps mal log-2 (n) Rekursion für O (n * log n) Zeit.

Wie viel kostet nicht-ideale Dreh Auswahl beeinflusst Ausführungszeit?

Lassen Sie uns einen Fall betrachten, in dem die Dreh konsequent so gewählt wird, dass 75% der Daten auf einer Seite des Dreh ist. Es ist immer noch O (n * log n), aber jetzt die Basis des Protokolls 1 / 0,75 oder 1,33 hat sich geändert. Die Beziehung in der Leistung bei der Basiswechsel ist immer eine Konstante, die durch log (2) repräsentierte / log (Newbase). In diesem Fall ist, dass konstant 2.4. Also diese Qualität der Pivot-Wahl nimmt das 2,4-fache länger als die ideal.

Wie schnell dies noch schlimmer?

Nicht sehr schnell, bis die Dreh Wahl bekommt (konsequent) sehr schlecht:

  • 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

Wie wir 100% auf einer Seite des Protokollteil der Ausführungs nähern nähert n und die gesamten Ausführungs asymptotisch O (n ^ 2).

In einer naiven Umsetzung QuickSort, Fälle, wie beispielsweise einen sortierten Array (für 1.es Element Schwenk) oder einen Rückwärts sortierte Array (für die letzte Element Schwenk) werden zuverlässig ein Worst-Case-O (n ^ 2) Ausführungszeit erzeugen. Zusätzlich Implementierungen mit einer vorhersagbaren Dreh Auswahl kann durch Daten DoS-Angriff ausgesetzt werden, die ausgelegt ist, worst case execution herzustellen. Moderne Implementierungen diese Methoden durch eine Vielzahl vermeiden, wie die Daten vor der Randomisierung Art, den Median von 3 zufällig ausgewählten Indizes wählen, usw. Mit dieser Randomisierung in der Mischung, haben wir 2 Fälle:

  • Kleine Datensatz. Im schlimmsten Fall ist nicht auszuschließen, aber O (n ^ 2) nicht katastrophal ist, weil n klein genug ist, daß n ^ 2 auch klein ist.
  • Großer Datensatz. Im schlimmsten Fall ist theoretisch möglich, aber in der Praxis nicht.

Wie wahrscheinlich sind wir schreckliche Leistung sehen?

Die Chancen sind verschwindend klein . Lassen Sie uns eine Art von 5.000 Werte berücksichtigen:

Unsere hypothetische Implementierung wählt einen Dreh einen medianen Zeitraum von drei zufällig ausgewählten Indizes verwenden. Wir werden schwenken zu berücksichtigen, die in dem 25% -75% -Bereich sind „gut“ und schwenkt zu sein, die im Bereich von 0% bis 25% oder 75% -100% -Bereich sind „schlecht“ zu sein. Wenn man sich die Wahrscheinlichkeitsverteilung aussieht den Median von 3 zufälliger Indizes verwendet wird, hat jeder Rekursion eine 11/16 Chance, mit einem guten Dreh enden. Lassen Sie uns zwei konservative machen (und falschen) Annahmen, die Mathematik zu vereinfachen:

  1. Gute schwenkt immer genau bei 25% / 75% aufgeteilt und bei 2,4 * Idealfall arbeiten.Wir bekommen nie ein ideales Split oder jede Spaltung besser als 25/75.

  2. Bad schwenkt immer schlimmster Fall und im Wesentlichen trägt nichts zur Lösung.

Unsere QuickSort Implementierung wird eine Insertionsort bei n = 10 und Schaltern stoppen, so benötigen wir 22 25% / 75% Schwenk Partitionen den 5.000 Werteingang nach unten, so weit zu brechen. (10 * 1,333333 ^ 22> 5000) Oder benötigen wir 4990 schlimmsten Fall schwenkt. Beachten Sie, dass, wenn wir 22 gute schwenkt sammeln sich an jeder Punkt dann füllen die Art, so schlimmsten Fall oder irgendetwas in der Nähe es erfordert extrem Pech. Wenn es uns 88 Rekursion nimmt, um tatsächlich die 22 gut schwenkt zu erreichen erforderlich ist, um n zu sortieren nach unten = 10, würde 4 * 2.4 * Idealfall sein oder etwa 10-mal die Ausführungszeit des Idealfalls. Wie wahrscheinlich ist es, dass wir nicht erreichen die erforderlichen 22 gut schwenkt nach 88 Rekursion?

Binomial Wahrscheinlichkeitsverteilungen dass beantworten kann, und die Antwort ist etwa 10 ^ -18. (N 88, k 21, p 0,6875) Ihr Benutzer ist etwa tausendmal eher vom Blitz in 1 Sekunde geschlagen werden, darauf zu klicken nimmt [SORT], als sie sind zu sehen, dass 5.000 Artikel laufen sort schlechter als 10 * Idealfall. Diese Chance wird kleiner als der Datensatz wird größer. Hier sind einige Feldgrößen und die entsprechenden Chancen laufen länger als 10 * ideal:

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

Beachten Sie, dass dies mit zwei konservativen Annahmen, die schlimmer als die Realität sind. So tatsächliche Leistung ist noch besser, und der Rest der verbleibenden Wahrscheinlichkeit näher ist ideal als nicht.

Schließlich, wie andere schon erwähnt haben, auch diese absurden unwahrscheinlich Fällen kann durch den Wechsel zu einem Haufen Art beseitigt werden, wenn die Rekursion Stack zu tief geht. So ist die TLDR, dass für gute Implementierungen von QuickSort, schlimmsten Fall nicht wirklich existiert , weil es wurde entwickelt, und die Ausführung abgeschlossen hat in O (n * log n) Zeit.

Die Antwort leicht in Richtung quicksort mit DualPivotQuickSort für primitive Werte w.r.t auf Veränderungen kippen würde. Es wird in JAVA 7 verwendet sortieren in java.util.Arrays 

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.

Sie können die Java7 implmentation hier finden - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Weitere Ehrfürchtig Lesen auf DualPivotQuickSort - http: // permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

merge-Art, der allgemeine Algorithmus ist:

  1. Sortieren der linke Unterarray
  2. Sortieren Sie die rechte Unterarray
  3. Merge die 2 sortiert Unterfelder

Auf der obersten Ebene, die Zusammenführung der 2 sortiert Subanordnungen umfasst mit N Elementen handelt.

Eine Ebene darunter, jede Iteration von Schritt 3 beinhaltet die mit N / 2 Elementen zu tun, aber Sie haben diesen Prozess zweimal zu wiederholen. Sie sind also immer noch mit 2 * N / 2 == N Elementen handeln.

Eine Ebene darunter, Sie verschmelzenden 4 * N / 4 == N Elemente, und so weiter. Jede Tiefe in dem rekursiven Stapel beinhaltet die gleiche Anzahl von Elementen verschmelzen, über alle Anrufe für diese Tiefe.

Betrachten Sie den Schnellsortieralgorithmus statt:

  1. Wählen Sie einen Drehpunkt
  2. Stellen Sie den Drehpunkt an der richtigen Stelle in der Anordnung, wobei alle kleineren Elemente links und größere Elemente rechts
  3. Sortieren Sie die Links-Sub-Array
  4. Sortieren der rechten Sub-Array

Auf der obersten Ebene, die Sie mit einer Reihe von Größe N. tun Sie dann einen Drehpunkt auswählen, stecken es in der richtigen Position und kann es dann ignorieren vollständig für den Rest des Algorithmus.

Eine Ebene darunter, man es zu tun mit zwei Unteranordnungen, die eine Gesamtgröße von N-1 (dh, subtrahieren den früheren Drehpunkt). Sie wählen einen Drehpunkt für jeden Sub-Array, die bis zu 2 weiteren Drehpunkten kommen.

Eine Ebene darunter, man es zu tun mit 4 Sub-Arrays mit kombinierter Größe N-3, aus den gleichen Gründen wie oben.

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

Die Tiefe der rekursiven Stapel etwa gleich bleibt (log N). Mit merge-Art, es zu tun Sie immer mit einem N-Elemente verschmelzen, über jede Ebene des rekursiven Stapels. Mit Schnell Art aber die Anzahl der Elemente, die Sie mit abnimmt es zu tun, wie Sie den Stapel nach unten gehen. Zum Beispiel, wenn Sie in der Tiefe auf halbem Wege durch die rekursive Stapel aussehen, die Anzahl der Elemente, die Sie es zu tun ist N - 2 ^ ((log N) / 2)) == N -. Sqrt (N)

Haftungsausschluss: Auf merge-sort, weil Sie das Array in zwei genau gleiche Stücke jedes Mal teilen, die rekursive Tiefe ist genau logN. Auf quick-sort, weil Ihr Drehpunkt ist unwahrscheinlich, genau der Anordnung in der Mitte zu sein, kann die Tiefe der rekursiven Stapel kann etwas größer als log N. Ich habe nicht die Mathe getan, um zu sehen, wie groß eine Rolle dieser Faktor und der oben beschriebene Faktor, spielen tatsächlich in den Algorithmus der Komplexität.

Im Gegensatz zu Mergesort Quicksort keinen auxilary Raum verwendet. Wohingegen verwendet Merge Sort eine auxilary Raum O (n). Aber Merge Sort hat die schlimmste Fall Zeitkomplexität von O (n log n), während die ungünstigste Fall Komplexität der Schnellsortierung ist O (n ^ 2), das passiert, wenn das Array bereits sortiert ist.

Während sie beide im selben Komplexitätsklasse sind, dann bedeutet das nicht, sie beide die gleiche Laufzeit haben. Quicksort ist in der Regel schneller als mergesort, nur weil es einfacher ist, eine enge Implementierung zu codieren und die Operationen kann es schneller geht. Es ist, weil der quicksort schneller ist in der Regel, dass die Leute es verwenden, anstatt mergesort.

Allerdings! Ich persönlich häufig verwenden mergesort oder eine quicksort Variante, die mergesort verschlechtert, wenn quicksort schlecht macht. Merken. Quicksort ist nur O (n log n) auf Durchschnitt . Es ist schlimmster Fall O (n ^ 2)! Mergesort ist immer O (n log n). In Fällen, in denen Echtzeit-Performance oder Ansprechbarkeit ist ein Muss und Ihre Eingangsdaten kommen von einer böswilligen Quelle werden könnten, Sie sollen nicht schlicht quicksort verwenden.

Quicksort hat eine bessere durchschnittliche Fall Komplexität aber in einigen Anwendungen ist es die falsche Wahl. Quicksort ist anfällig für Denial-of-Service-Attacken. Wenn ein Angreifer die Eingabe wählen kann sortiert werden, kann er leicht einen Satz konstruieren, die die schlimmste Fall Zeit Komplexität o nimmt (n ^ 2).

Mergesort durchschnittliche Fall Komplexität und Worst-Case-Komplexität ist die gleiche, und als solche nicht das gleiche Problem leiden. Diese Eigenschaft des Merge-Art macht es auch die beste Wahl für Echtzeitsysteme - gerade weil es nicht pathologische Fälle sind, die sie verursachen viel laufen, viel langsamer.

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

Warum Quicksort ist gut?

  • QuickSort nimmt N ^ 2 im schlimmsten Fall und NlogN durchschnittlichen Fall. Der schlimmste Fall tritt auf, wenn Daten sortiert ist. Dies kann durch zufällige Shuffle gemildert werden, bevor gestartet Sortieren.
  • QuickSort nicht nimmt zusätzliche Speicher, der durch Mergesort genommen wird.
  • Wenn der Datensatz groß ist, und es gibt identische Elemente, die Komplexität von Quicksort reduziert durch die Verwendung 3-Wege-Partition. die mehr und nicht identischer Elemente besser die Art. Wenn alle Elemente identisch sind, sortiert sie in linearer Zeit. [Dies ist Default-Implementierung in den meisten Bibliotheken]

Ist Quicksort immer besser als Mergesort?

Nicht wirklich.

  • Mergesort ist stabil, aber Quicksort ist es nicht. Wenn Sie also die Stabilität in der Ausgabe benötigen, würden Sie Mergesort verwenden. Die Stabilität wird in vielen praktischen Anwendungen erforderlich ist.
  • Speicher ist heutzutage billig. Also, wenn zusätzliche Speicher verwendet von Mergesort ist nicht kritisch auf Ihre Bewerbung, gibt es keinen Schaden in Mergesort verwenden.

Hinweis: In Java Arrays.sort () Funktion verwendet Quicksort für primitive Datentypen und Mergesort für Objektdatentypen. Da Objekte Speicher-Overhead verbrauchen, gegeben, so ein wenig Aufwand für Mergesort keine Ausgabe für Performance-Sicht sein kann.

Referenz : Beobachten Sie die QuickSort Videos von Woche 3, Princeton Algorithmen Kurs bei Coursera

Schnellsortierung ist worst case O (n ^ 2), jedoch den Durchschnittsfall konsequent out Sortierung führt zu verschmelzen. Jeder Algorithmus ist O (n log n), aber Sie müssen bedenken, dass, wenn man über Big O sprechen wir die geringere Komplexität Faktoren weglassen. Kurze Art hat deutliche Verbesserungen gegenüber Mergesort, wenn es um konstante Faktoren kommt.

Merge erfordert Art auch O (2n) Speicher, während eine schnelle Art können an Ort und Stelle durchgeführt werden (erfordert nur O (n)). Dies ist ein weiterer Grund dafür, dass eine schnelle Art der Regel über Mergesort bevorzugt.

Zusätzliche Informationen:

Der schlimmste Fall von schnellen Art tritt auf, wenn der Dreh schlecht gewählt. Betrachten Sie das folgende Beispiel:

[5, 4, 3, 2, 1]

Wenn der Schwenk als kleinste oder größte Zahl in der Gruppe gewählt wird, dann wird in schnellen Sortier O läuft (n ^ 2). Die Wahrscheinlichkeit, dass das Element der Wahl, die in der größten oder kleinsten ist 25% der Liste ist 0,5. Das gibt den Algorithmus eine 0,5 Chance, einen guter Schwenk zu sein. Wenn wir einen typischen Dreh Auswahl-Algorithmus (sagt die Wahl ein Zufallselementes) verwenden, haben wir 0,5 Chance auf einen guten Schwenk für jede Wahl eines Dreh wählen. Für Sammlungen von großer Größe ist die Wahrscheinlichkeit immer eine schlechte Dreh Wahl 0,5 * n. Auf der Grundlage dieser Wahrscheinlichkeit ist Quicksort für eine effizienten den Durchschnitt (und typisch) Fall.

Dies ist eine ziemlich alte Frage, aber da ich mit beiden vor kurzem hier behandelt habe, sind meine 2c:

Merge muss Art im Durchschnitt ~ N N Vergleiche protokollieren. Für bereits (fast) sortierten Arrays sortiert wird dies auf 1/2 N log N nach unten, da während der Zusammenführung wir (fast) immer wählen „links“ Teil 1/2 N Mal und dann nach rechts 1/2 N Elemente einfach kopieren. Außerdem kann ich spekulieren, dass bereits sortierte Eingang Verzweigungsprädiktor des Prozessors zu glänzen, aber fast alle Zweige richtig erraten, so Pipeline-Blockierungen zu verhindern.

Schnell Art im Durchschnitt erfordert ~ 1,38 N log N Vergleiche. Es ist nicht stark in Bezug auf die Vergleiche von bereits sortierten Array zugute kommt (aber es funktioniert in Bezug auf Swaps und wahrscheinlich in Bezug auf die Verzweigungsvorhersagen innerhalb CPU).

Mein Benchmarks auf ziemlich modernen Prozessor zeigt folgende Möglichkeiten:

Als Vergleichsfunktion eine Callback-Funktion ist (wie in qsort () libc Implementierung) quicksort ist langsamer als mergesort um 15% auf zufällige Input und 30% für die bereits sortierten Array für 64-Bit-Integer.

Auf der anderen Seite, wenn der Vergleich nicht ein Rückruf ist, meine Erfahrung ist, dass quicksort trifft mergesort um bis zu 25%.

Allerdings, wenn Ihr (groß) Array sehr wenige eindeutige Werte hat, Mergesort beginnt über quicksort auf jeden Fall gewinnen.

Also vielleicht das Endergebnis ist: wenn der Vergleich teuer ist (zB Callback-Funktion, Strings zu vergleichen, vergleichen viele Teile einer Struktur meist auf eine zweite bis dritte her bekommen „wenn“ Unterschied machen) - die Chancen, dass Sie wird mit Mergesort besser sein. Für einfachere Aufgaben quicksort schneller sein.

Das heißt alle vorher gesagt gilt: - Quicksort kann N ^ 2 sein, aber Sedgewick behauptet, dass eine gute randomisierte Implementierung mehr Chancen auf einen Computer durchführt Art hat von einem Blitz getroffen werden, als N ^ 2 zu gehen - Mergesort erfordert zusätzlichen Raum

Wenn ich experimentiert mit beiden Sortieralgorithmen, indem die Anzahl der rekursiven Aufrufe zu zählen, quicksort durchweg weniger als rekursive Aufrufe mergesort. Es ist, weil quicksort schwenkt hat, und dreht sich nicht in den nächsten rekursiven Aufrufe enthalten. Auf diese Weise kann quicksort rekursive Basisfall erreichen mehr schneller als mergesort.

Alle Dinge gleich sind, würde ich die meisten Leute erwarten zu verwenden, was am einfachsten verfügbar ist, und das dazu neigt, qsort zu werden (3). Anders als das quicksort ist bekannt, auf Arrays sehr schnell zu sein, genau wie mergesort ist die gemeinsame Wahl für Listen.

Was ich frage mich, warum es so selten ist, um zu sehen Radix oder Bucketsort. Sie sind O (n), zumindest auf verkettete Listen, und es genügt, einige Verfahren zur Herstellung des Schlüssel zu einer Ordnungszahl umzuwandeln. (Strings und Schwimmer gut funktionieren.)

Ich denke, der Grund, mit dem zu tun hat, wie Informatik gelehrt wird. Ich hatte sogar mein Dozent in Algorithmenanalyse zu zeigen, dass es tatsächlich möglich war schneller als O zu sortieren (n log (n)). (Er hatte den Beweis, dass man nicht Vergleich Art schneller als O (n log (n)), was wahr ist.)

In anderen Nachrichten können Schwimmer als ganze Zahlen sortiert werden, aber Sie haben die negativen Zahlen umdrehen danach.

Edit: Eigentlich ist hier eine noch bösartige Weise schwebt-as-Zahlen zu sortieren: http: //www.stereopsis. com / radix.html . Beachten Sie, dass die Bit-Flipping Trick unabhängig davon, was Algorithmus Sortierung verwendet werden können, die Sie tatsächlich nutzen ...

Das ist schwer schlimmsten MergeSort say.The n (log2n) -n + 1, das genau ist, wenn n 2 ^ k gleich (ich habe dies bereits bewiesen) .Und für jeden n, es ist zwischen (n lg n -. n + 1) und (n lg n + n + O (lg n)) Aber für QuickSort, seine besten ist nlog2n (auch n gleich 2 ^ k) .Wenn Sie Mergesort durch QuickSort teilen, ist es eins gleich, wenn n infinite.So es ist, als ob der schlimmste Fall von MergeSort ist besser als der beste Fall von QuickSort, warum verwenden wir quicksort? Aber denken sie daran, MergeSort ist nicht vorhanden, erfordert es 2n memeroy space.And MergeSort müssen auch viele Array Kopien tun , die wir bei der Analyse von algorithm.In gehören ein Wort nicht, ist MergeSort wirklich faseter als quicksort in theroy, aber in Wirklichkeit müssen Sie memeory Raum berücksichtigen, die Kosten für die Array zu kopieren, ist Fusion langsamer als schnelle sort.I einmal machte ein Experiment, wo ich 1000000 Ziffern in Java nach Zufall Klasse gegeben wurde, und es dauerte 2610ms durch mergesort, 1370ms von quicksort.

Kleine Ergänzungen schnell vs merge sortiert.

Auch kann es von der Art der Sortierung Artikel ab. Wenn der Zugriff auf Artikel, Swap- und Vergleiche nicht einfache Operationen sind, wie ganze Zahlen in der Ebene Speicher zu vergleichen, fusioniert dann kann Art vorzuziehen Algorithmus sein.

Zum Beispiel sortieren wir Einzelteile Netzwerkprotokoll auf dem Remote-Server.

Auch in benutzerdefinierten Container wie „verketteten Liste“, die nicht von Vorteil schnell sortieren.
1. Merge Art auf verknüpfte Liste, brauchen keine zusätzlichen Speicher. 2. Zugriff auf Elemente in Quicksort ist nicht sequentiell (im Speicher)

Schnellsortierung ist ein In-Place-Sortier-Algorithmus, so ist es besser geeignet für Arrays. Merge Sort auf der anderen Seite erfordert zusätzliche Speicherung von O (N), und ist besser geeignet für verkettete Listen.

Im Gegensatz zu Arrays in gemocht Listen wir Einzelteile in der Mitte mit O (1) Raum und O (1) Zeit, damit der Druckvorgang in Mergesort einfügen kann ohne zusätzlichen Raum realisiert werden. Jedoch, Aufteilung und de-Zuweisung zusätzlichen Platz für Arrays haben einen negativen Einfluss auf die Laufzeit von Mergesort. Mergesort auch favorisiert verknüpfte Liste als Daten sequentiell zugegriffen wird, ohne viel zufällige Speicherzugriff.

Kurze Art auf der anderen Seite erfordert eine Menge von zufälligem Speicherzugriff und mit einem Array können wir direkt auf den Speicher zugreifen, ohne Verfahrweg durch verkettete Listen nach Bedarf. Auch schnelle Art, wenn für Arrays verwendet, um eine gute Referenzlokalität hat als Arrays zusammenhängend in Speichern gespeichert werden.

Obwohl beide Sortieralgorithmen durchschnittliche Komplexität O (NlogN) ist, in der Regel Menschen für gewöhnliche Aufgaben verwendet eine Anordnung für die Lagerung, und aus diesem Grund eine schnelle Art sollte der Algorithmus der Wahl sein.

EDIT: Ich habe gerade herausgefunden, dass Mergesort schlechtesten / besten / avg Fall ist immer nlogn, aber schnelle Art kann von n2 (ungünstigster Fall, wenn die Elemente bereits sortiert sind) variieren zu nlogn (avg / besten Fall, wenn Pivot immer teilt die Array in zwei Hälften).

Betrachten wir Zeit und Raum Komplexität beides. Für Merge sort: Zeitkomplexität: O (n log n), Speicherkomplexität: O (n log n)

Für Schnell sortieren: Zeitkomplexität: O (n ^ 2), Speicherkomplexität: O (n)

Nun, sie beide in einem scenerio gewinnen. Aber eine zufällige Pivot verwenden, können Sie fast immer reduzieren Zeitkomplexität von Quicksort zu O (n log n).

So Schnell Art anstelle von Merge Art in vielen Anwendungen bevorzugt.

In c / c ++ Land, wenn nicht stl Behälter verwendet, neige ich dazu, quicksort zu verwenden, da es gebaut wird in der Laufzeit, während mergesort nicht.

So glaube ich, dass in vielen Fällen, es ist einfach der Weg des geringsten Widerstandes.

Darüber hinaus kann die Leistung viel höher mit schnellen Art, für Fälle, in denen die gesamte Datenmenge paßt nicht in den Arbeitssatz.

Einer der Gründe ist philosophisch. Quicksort ist Top-> Down-Philosophie. Mit n Elemente zu sortieren, gibt es n! Möglichkeiten. Mit 2 Partitionen von m & n-m, die sich gegenseitig ausschließen, gehen die Anzahl der Möglichkeiten unten in mehrere Größenordnungen. m! * (N-m)! ist um mehrere Größenordnungen kleiner als n! allein. vorstellen, 5! vs 3! * 2 !. 5! hat 10-mal mehr Möglichkeiten als 2 Partitionen von 2 & 3 jeweils. und extrapolieren auf 1 Million faktorielles vs 900K! * 100K! vs. Also anstatt sich darum zu kümmern, jede Bestellung innerhalb eines Bereichs oder einer Partition zur Gründung etablieren nur um auf einer breiteren Ebene in Partitionen und die Möglichkeiten innerhalb einer Partition reduzieren. Jede Bestellung etabliert früher innerhalb eines Bereichs wird später gestört werden, wenn die Trennwände sich nicht gegenseitig ausschließen.

Alle unten nach oben, um Ansatz wie Mergesort oder Heap-Art ist wie ein Arbeiter oder Angestellter Ansatz, wo man beginnt, auf mikroskopischer Ebene zu vergleichen früh. Aber diese Ordnung gebunden ist, in, sobald ein Element verloren geht zwischen ihnen später gefunden wird. Diese Ansätze sind sehr stabil und extrem vorhersehbar, aber nicht eine bestimmte Menge an zusätzlicher Arbeit.

Quicksort ist wie Managerial Ansatz, bei dem man zunächst nicht zu einem beliebigen Reihenfolge betreffen, nur über ein breites Kriterium ohne Rücksicht auf Bestellung zu erfüllen. Dann werden die Partitionen verengt, bis Sie eine sortierte Menge erhalten. Die eigentliche Herausforderung in Quicksort ist eine Partition oder ein Kriterium im Dunkeln bei der Suche, wenn Sie nichts über die Elemente kennen zu sortieren. Deshalb sind wir entweder müssen einige Mühe aufwenden, einen Medianwert zu finden oder 1 nach dem Zufallsprinzip oder einem beliebigen „Managerial“ Ansatz wählen. Um einen perfekten Median zu finden wieder erhebliche Menge an Aufwand und führt zu einem dummen Bottom-up-Ansatz. So Quicksort sagt eine nur eine zufällige Pivot holen und hofft, dass es irgendwo in der Mitte sein oder etwas arbeitet Median von 3, 5 zu finden oder etwas mehr, um eine bessere mediane zu finden, aber nicht planen, perfekt zu sein und nicht verschwenden jederzeit in ursprünglich Bestellung. Das scheint gut zu tun, wenn man Glück hat oder manchmal verschlechtert zu n ^ 2, wenn Sie nicht einen Median bekommen, aber nur eine Chance. Jede Art und Weise Daten sind zufällig. richtig.  Also hat ich mehr mit der Spitze zustimmen -> unten logischer Ansatz von quicksort & es stellt sich heraus, dass die Chance, es dauert etwa Pivot-Auswahl & Vergleiche, dass es früher spart scheint besser mehr Zeit zu arbeiten, als jeder sorgfältiger und gründlicher stabiler Boden -> up-Ansatz wie Zusammenführen, sortieren. Aber

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top