it-swarm-eu.dev

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 O (n2) Worst-Case-Laufzeit und O (nlogn) durchschnittliche Falllaufzeit. In vielen Szenarien ist es jedoch überlegen, die Sortierung zusammenzuführen, da viele Faktoren die Laufzeit eines Algorithmus beeinflussen. Wenn Sie alle zusammenfassen, gewinnt QuickSort.

Insbesondere bezieht sich die oft zitierte Laufzeit von Sortieralgorithmen auf die Anzahl der Vergleiche oder die Anzahl der Swap-Vorgänge, 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. Aber auch andere Dinge - wie die Referenzlokalität (d. H. Lesen wir viele Elemente, die sich wahrscheinlich im Cache befinden?) - spielen bei der aktuellen Hardware 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 Sortieren durch Zusammenführen.

Außerdem ist es sehr einfach, die Worst-Case-Laufzeit von O (n2) fast ausschließlich durch Verwendung einer geeigneten Auswahl des Pivots - beispielsweise durch zufälliges Auswählen (dies ist eine hervorragende Strategie).

In der Praxis gibt es viele moderne Implementierungen von Quicksort (insbesondere die std::sort) sind eigentlich Introsort , deren theoretischer Worst-Case O ist (nlogn), genau wie beim Zusammenführen. Dies wird erreicht, indem die Rekursionstiefe begrenzt und bei Überschreitung von log auf einen anderen Algorithmus ( heapsort ) umgeschaltet wirdn.

258
Konrad Rudolph

Wie viele Leute bemerkt haben, ist die durchschnittliche Fallleistung für Quicksort schneller als für Mergesort. Aber Dies gilt nur, wenn Sie eine konstante Zeit für den Zugriff auf ein beliebiges Speicherelement bei Bedarf annehmen.

In RAM ist diese Annahme im Allgemeinen nicht allzu schlimm (aufgrund von Caches nicht immer, aber nicht allzu schlimm). Wenn Ihre Datenstruktur jedoch groß genug ist, um auf der Festplatte zu leben, dann quicksort wird durch die Tatsache getötet , dass eine durchschnittliche Festplatte 200 zufällige Suchvorgänge pro Sekunde ausführt, aber dieselbe Festplatte hat keine Probleme beim Lesen oder Schreiben von Megabyte pro Sekunde genau das macht mergesort.

Wenn also Daten auf der Festplatte sortiert werden müssen, möchten Sie wirklich eine Variation von Mergesort verwenden. (Im Allgemeinen werden Unterlisten schnell sortiert und ab einem bestimmten Größenschwellenwert zusammengeführt.)

Wenn Sie mit Datasets dieser Größe etwas zu tun haben , sollten Sie darüber nachdenken, wie Sie Datenträgersuchvorgänge vermeiden können. Aus diesem Grund wird standardmäßig empfohlen, Indizes zu löschen, bevor große Datenmengen in Datenbanken geladen werden, und den Index später erneut zu erstellen. Wenn Sie den Index während des Ladevorgangs beibehalten, müssen Sie ständig nach Datenträgern suchen. Wenn Sie dagegen die Indizes löschen, kann die Datenbank den Index neu erstellen, indem sie zuerst die zu bearbeitenden Informationen sortiert (natürlich mit einer Zusammenführung!) Und dann in eine BTREE-Datenstruktur für den Index lädt. (BTREEs werden natürlich in Ordnung gehalten, sodass Sie mit wenigen Suchanfragen einen aus einem sortierten Datensatz auf die Festplatte laden können.)

Es gab eine Reihe von Fällen, in denen ich Datenverarbeitungsaufträge nicht mehr nach Tagen oder Wochen, sondern nach Stunden ausführen musste, um Datenträgersuchen zu vermeiden.

275
user11318

Eigentlich ist QuickSort O (n2). Seine durchschnittlicher Fall Laufzeit ist O (nlog (n)), aber sein schlechtester Fall ist O (n)2), der auftritt, wenn Sie es in einer Liste ausführen, die nur wenige eindeutige Elemente enthält. Für die Randomisierung wird O (n) benötigt. Dies ändert natürlich nichts an seinem schlimmsten Fall, sondern verhindert lediglich, dass ein böswilliger Benutzer Ihre Sortierung lange Zeit in Anspruch nimmt.

QuickSort ist populärer, weil es:

  1. Ist vorhanden (MergeSort benötigt zusätzlichen Speicher, der linear zur Anzahl der zu sortierenden Elemente ist).
  2. Hat eine kleine versteckte Konstante.
88
Dark Shikari

"und dennoch verwenden die meisten Leute Quicksort anstelle von Mergesort. Warum ist das so?"

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

Ja, Quicksort mit dreifacher Partitionierung ist wahrscheinlich einer der besten Allzweck-Sortieralgorithmen, aber die Tatsache, dass "Schnelle" Sortierung viel leistungsfähiger klingt als "Zusammenführen".

29
Ash

Wie andere angemerkt haben, ist der schlechteste 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 allermeisten Fälle vergleichbar.

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

15
Javier

Ich möchte hinzufügen, dass von den drei bisher erwähnten Algorithmen (Mergesort, Quicksort und Heap-Sort) 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 Leute nur eine gute Durchschnittsleistung und Quicksort ist ... schnell =)

Alle Sortieralgorithmen haben ihre Höhen und Tiefen. Siehe Wikipedia-Artikel für Sortieralgorithmen für eine gute Übersicht.

8
Antti Rasinen

Von der Wikipedia-Eintrag auf 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 Sortierung und kann problemlos für verknüpfte Listen und sehr große Listen angepasst werden, die auf Datenträgern mit langsamem Zugriff wie Festplattenspeicher oder Netzwerkspeicher gespeichert sind. Obwohl QuickSort so geschrieben werden kann, dass es mit verknüpften Listen funktioniert, wird es häufig unter schlechten Pivot-Optionen ohne wahlfreien Zugriff leiden. Der Hauptnachteil von Mergesort besteht darin, dass es beim Betrieb auf Arrays im besten Fall Θ (n) zusätzlichen Speicherplatz benötigt, während die Variante von Quicksort mit In-Place-Partitionierung und Tail-Rekursion nur Θ (logn) Speicherplatz benötigt. (Beachten Sie, dass Mergesort bei der Arbeit mit verknüpften Listen nur eine geringe, konstante Menge an Zusatzspeicher benötigt.)

7
gnobal

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, schlechte Worst-Case-Leistung nicht toleriert werden kann und zusätzlicher Speicherplatz verfügbar ist. 1

Sie sagten, sie seien 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

7
Roman Glass

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

Heapsort wird garantiert in O (n * ln (n)) ausgeführt und benötigt nur begrenzten zusätzlichen Speicher. Es gibt jedoch viele Zitate von Tests in der Praxis, die zeigen, dass Heapsort im Durchschnitt erheblich langsamer ist als Quicksort.

6
Niyaz

Die Erklärung von Wikipedia lautet:

In der Praxis ist Quicksort in der Regel 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 eines quadratischen Zeitaufwands minimieren .

Quicksort

Mergesort

Ich denke, es gibt auch Probleme mit der Menge an Speicher, die für Mergesort benötigt wird (was Ω (n) ist), die QuickSort-Implementierungen nicht haben. Im schlimmsten Fall haben sie die gleiche algorithmische Zeit, aber für die Zusammenführung ist mehr Speicher erforderlich.

5
Mat Mannion

Ich möchte zu den vorhandenen großartigen Antworten einige mathematische Überlegungen hinzufügen, wie QuickSort abweicht und wie wahrscheinlich dies ist. Ich hoffe, dass dies den Leuten hilft, ein wenig besser zu verstehen, warum der O (n ^ 2) -Fall nicht real ist Bedenken in den anspruchsvolleren Implementierungen von QuickSort.

Abgesehen von Problemen mit wahlfreiem Zugriff können zwei Hauptfaktoren die Leistung von QuickSort beeinflussen. Beide Faktoren 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 in einer Vanilla 2-Partition QuickSort in n ^ 2-Zeit sortiert, da alle Werte mit Ausnahme der Pivot-Position jedes Mal auf einer Seite platziert werden. Moderne Implementierungen begegnen diesem Problem mit Methoden wie der Verwendung einer Sortierung mit drei Partitionen. Diese Methoden werden für einen Datensatz mit demselben Wert in O(n) Zeit ausgeführt. Wenn Sie also eine solche Implementierung verwenden, bedeutet dies, dass eine Eingabe mit einer geringen Anzahl von Schlüsseln die Leistungszeit tatsächlich verbessert und nicht länger gültig ist eine Sorge.

2) Extrem schlechte Pivot-Auswahl kann die Leistung im schlechtesten Fall beeinträchtigen. 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 Swap-Zeiten log-2 (n) Rekursionen für O (n * logn) Zeit.

Inwieweit beeinflusst die nicht ideale Pivot-Auswahl die Ausführungszeit?

Angenommen, der Pivot wird konsistent so ausgewählt, 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. Das Leistungsverhältnis beim Basiswechsel ist immer eine Konstante, die durch log (2)/log (newBase) dargestellt wird. In diesem Fall ist diese Konstante 2.4. Diese Qualität der Pivot-Auswahl dauert also 2,4-mal länger als das Ideal.

Wie schnell wird das noch schlimmer?

Nicht sehr schnell, bis die Pivot-Wahl (durchgehend) 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 einseitig 100% nähern, nähert sich der Log-Teil der Ausführung n und die gesamte Ausführung nähert sich asymptotisch O (n ^ 2).

In einer naiven Implementierung von QuickSort wird in Fällen wie einem sortierten Array (für den 1. Element-Pivot) oder einem umgekehrt sortierten Array (für den letzten Element-Pivot) eine Ausführungszeit von O (n ^ 2) im ungünstigsten Fall zuverlässig erzeugt. Darüber hinaus können Implementierungen mit einer vorhersagbaren Pivot-Auswahl DoS-Angriffen 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 Zufallsgenerierung der Daten vor dem Sortieren, Auswahl des Medians aus 3 zufällig ausgewählten Indizes usw. Mit dieser Zufallsgenerierung im Mix haben wir zwei Fälle:

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

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

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

Unsere hypothetische Implementierung wählt einen Pivot aus einem Median von 3 zufällig ausgewählten Indizes. Wir werden Pivots im Bereich von 25% -75% als "gut" und Pivots im Bereich von 0% -25% oder 75% -100% als "schlecht" betrachten. Wenn Sie die Wahrscheinlichkeitsverteilung mit dem Median von 3 Zufallsindizes betrachten, hat jede Rekursion eine 11/16-Chance, mit einem guten Pivot zu enden. Lassen Sie uns zwei konservative (und falsche) Annahmen treffen, um die Mathematik zu vereinfachen:

  1. Gute Pivots haben immer genau einen Split von 25%/75% und arbeiten im Idealfall mit 2,4 *. Wir bekommen niemals eine ideale Aufteilung oder eine bessere Aufteilung als 25/75.

  2. Schlechte Pivots 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ügesorte. Daher benötigen wir 22 Pivot-Partitionen mit 25%/75%, um die 5.000-Werteingabe so weit herunterzubrechen. (10 * 1.333333 ^ 22> 5000) Oder wir benötigen 4990 Worst-Case-Pivots. Denken Sie daran, dass, wenn wir 22 gute Pivots an einem beliebigen Punkt akkumulieren, die Sortierung abgeschlossen wird, sodass der schlimmste Fall oder etwas in der Nähe davon extrem Pech erfordert. Wenn wir 88 Rekursionen benötigen, um die 22 guten Pivots, die zum Sortieren auf n = 10 erforderlich sind, tatsächlich zu erreichen, wäre dies der 4 * 2,4 * -Idealfall oder etwa die 10-fache Ausführungszeit des Idealfalls. Wie wahrscheinlich ist es, dass wir nach 88 Rekursionen nicht die erforderlichen 22 guten Pivots erreichen?

Binomial Wahrscheinlichkeitsverteilungen kann das beantworten, und die Antwort ist ungefähr 10 ^ -18. (n ist 88, k ist 21, p ist 0,6875) Es ist ungefähr tausendmal wahrscheinlicher, dass Ihr Benutzer in einer Sekunde, die zum Klicken auf [SORTIEREN] benötigt wird, vom Blitz getroffen wird, als dass 5.000 Elemente sortiert werden alle schlechter 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 * ideal zu laufen:

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

Denken Sie daran, dass dies mit 2 konservativen Annahmen ist, die schlechter als die Realität sind. Die tatsächliche Leistung ist also noch besser und das Gleichgewicht der verbleibenden Wahrscheinlichkeit ist eher ideal als nicht.

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

4
Lance Wisely

Quicksort ist NICHT besser als Mergesort. Bei O (n ^ 2) (der schlimmste Fall, der selten vorkommt) ist die Quicksort-Funktion möglicherweise viel langsamer als die Funktion O(nlogn) der Zusammenführungssortierung Es ist besser, langsame Computer zu verwenden, aber Computer sind heutzutage so schnell, dass der zusätzliche Aufwand für eine Zusammenführung vernachlässigbar ist, und das Risiko einer sehr langsamen Zusammenführung überwiegt in den meisten Fällen den unbedeutenden Aufwand für eine Zusammenführung bei weitem.

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

4
xpda

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 verringert werden, bevor mit dem Sortieren begonnen wird.
  • QuickSort beansprucht 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 Elemente 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 eine stabile Ausgabe benötigen, verwenden Sie Mergesort. Stabilität ist in vielen praktischen Anwendungen erforderlich.
  • Speicher ist heutzutage billig. Wenn also zusätzlicher von Mergesort verwendeter Speicher für Ihre Anwendung nicht kritisch ist, kann die Verwendung von Mergesort nicht schaden.

Hinweis: In Java verwendet die Funktion Arrays.sort () Quicksort für primitive Datentypen und Mergesort für Objektdatentypen. Da Objekte Speicherplatz belegen, ist das Hinzufügen eines kleinen Overheads für Mergesort aus Sicht der Leistung möglicherweise kein Problem.

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

4

Im Gegensatz zu Merge Sort verwendet Quick Sort kein zusätzliches Leerzeichen. Während Merge Sort einen Hilfsraum O (n) verwendet. Merge Sort hat jedoch die schlechteste Zeitkomplexität von O(nlogn), wohingegen die schlechteste Fallkomplexität von Quick Sort O (n ^ 2) ist, was passiert, wenn das Array bereits sortiert ist.

3
Shantam Mittal

Bei Änderungen, die mit DualPivotQuickSort für primitive Werte vorgenommen wurden, würde die Antwort leicht in Richtung Quicksort w.r.t tendieren. Es wird in Java 7 verwendet, um in Java.util.Arrays zu sortieren.

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

3
appbootup

Bei der Zusammenführungssortierung lautet der allgemeine Algorithmus:

  1. Sortieren Sie das linke Unterarray
  2. Sortieren Sie das richtige Sub-Array
  3. Füge die 2 sortierten Subarrays zusammen

Auf der obersten Ebene beinhaltet das Zusammenführen der 2 sortierten Subarrays den Umgang mit N Elementen.

Eine Ebene darunter umfasst 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 verschmelzen Sie 4 * N/4 == N Elemente und so weiter. Jede Tiefe im rekursiven Stapel umfasst das Zusammenführen der gleichen Anzahl von Elementen für alle Aufrufe dieser Tiefe.

Betrachten Sie stattdessen den Schnell-Sortier-Algorithmus:

  1. Wählen Sie einen Drehpunkt
  2. Platzieren Sie den Drehpunkt an der richtigen Stelle im Array, wobei sich alle kleineren Elemente links und die größeren rechts befinden
  3. Sortieren Sie das linke Subarray
  4. Sortieren Sie das rechte Subarray

Auf der obersten Ebene haben Sie es mit einem Array der Größe N zu tun. 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 Sub-Array einen Drehpunkt aus, der bis zu 2 zusätzliche Drehpunkte ergibt.

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 haben Sie es immer mit einer Zusammenführung von N Elementen auf jeder Ebene des rekursiven Stapels zu tun. Mit der schnellen Sortierung verringert sich jedoch die Anzahl der Elemente, mit denen Sie zu tun haben, je weiter Sie im Stapel arbeiten. Wenn Sie sich beispielsweise die Tiefe in der Mitte des rekursiven Stapels ansehen, ist die Anzahl der Elemente, mit denen Sie zu tun haben, N - 2 ^ ((logN)/2)) == N - sqrt (N).

Haftungsausschluss: Beim Sortieren durch Zusammenführen ist die rekursive Tiefe genau logN, da Sie das Array jedes Mal in zwei exakt gleiche Blöcke aufteilen. Bei der schnellen Sortierung ist die Tiefe des rekursiven Stapels möglicherweise etwas größer als logN, da der Drehpunkt wahrscheinlich nicht genau in der Mitte des Arrays liegt. Ich habe nicht nachgerechnet, wie groß die Rolle dieses Faktors und des oben beschriebenen Faktors für die Komplexität des Algorithmus tatsächlich ist.

3
RvPr

Quicksort hat eine bessere durchschnittliche Fallkomplexität, ist jedoch in einigen Anwendungen 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 auf einfache Weise eine Menge erstellen, die die Zeitkomplexität im ungünstigsten Fall von o (n ^ 2) annimmt.

Mergesorts durchschnittliche Fallkomplexität und die schlimmste Fallkomplexität sind gleich und weisen daher 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 ausgeführt wird.

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

2
Simon Johnson

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 strenge Implementierung zu programmieren, und die Operationen, die es ausführt, schneller ablaufen können. Es ist so, weil diese Quicksortierung im Allgemeinen schneller ist, als die Leute sie verwenden, anstatt sie zusammenzuführen.

Jedoch! Ich persönlich verwende häufig Mergesort oder eine QuickSort-Variante, die sich zu Mergesort verschlechtert, wenn QuickSort schlecht funktioniert. Merken. Quicksort ist nur O (n log n) im Durchschnitt . 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 ist und Ihre Eingabedaten aus einer böswilligen Quelle stammen können, Sie sollten keine einfache Quicksortierung verwenden.

2
DJ Capelis

Schnelle Sortierung ist der schlechteste Fall O (n ^ 2), der durchschnittliche Fall führt jedoch 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 Zusammenführungssortierung, wenn es um konstante Faktoren geht.

Das Sortieren beim Zusammenführen erfordert auch O(2n) Speicher, während das schnelle Sortieren an Ort und Stelle erfolgen kann (nur O (n) erforderlich). Dies ist ein weiterer Grund, warum das schnelle Sortieren im Allgemeinen dem Sortieren beim Zusammenführen vorgezogen wird.

Extra info:

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 Drehpunkt 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 Pivot-Auswahl einen guten Pivot auszuwählen. Für Sammlungen von großer Größe beträgt die Wahrscheinlichkeit, immer einen schlechten Pivot zu wählen, 0,5 * n. Basierend auf dieser Wahrscheinlichkeit ist eine schnelle Sortierung für den durchschnittlichen (und typischen) Fall effizient.

2
Wade Anderson

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

Sortierbedarf zusammenführen durchschnittlich ~ N log N Vergleiche. Für bereits (fast) sortierte sortierte Arrays ergibt dies 1/2 N log N, da wir beim Zusammenführen (fast) immer 1/2 N mal den "linken" Teil auswählen und dann einfach 1/2 N Elemente nach rechts kopieren. Außerdem kann ich spekulieren, dass bereits sortierte Eingaben den Branch Predictor des Prozessors zum Leuchten bringen, aber fast alle Branches korrekt erraten, wodurch ein Stillstand der Pipeline verhindert wird.

Schnelles Sortieren erfordert im Durchschnitt ~ 1,38 N log N Vergleiche. Es profitiert nicht sehr von bereits sortierten Arrays in Bezug auf Vergleiche (jedoch in Bezug auf Auslagerungen und wahrscheinlich in Bezug auf Verzweigungsvorhersagen innerhalb der CPU).

Meine Benchmarks für einen ziemlich modernen Prozessor zeigen Folgendes:

Wenn es sich bei der Vergleichsfunktion um eine Rückruffunktion handelt (wie in der Implementierung von qsort () libc), ist quicksort bei zufälligen Eingaben um 15% langsamer als mergesort und bei bereits sortierten Arrays für 64-Bit-Ganzzahlen um 30%.

Auf der anderen Seite, wenn der Vergleich 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 enthält, gewinnt die Sortierung beim Zusammenführen in jedem Fall über die Sortierung nach QuickSort.

Vielleicht lautet das Fazit also: Wenn der Vergleich teuer ist (z. B. Rückruffunktion, Vergleichen von Zeichenfolgen, Vergleichen vieler Teile einer Struktur, die meistens ein zweites Drittel erreichen, um einen Unterschied zu erzielen), sind die Chancen gut, dass Sie besser sind mit merge sort. Bei einfacheren Aufgaben ist der Schnellsortiervorgang schneller.

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

2
virco

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 in den nächsten rekursiven Aufrufen nicht enthalten sind. Auf diese Weise kann QuickSort rekursive Basisfälle schneller erreichen als Mergesort.

2

Kleine Ergänzungen für schnelle und gemischte Sortierungen.

Es kann auch von der Art der Sortierung der Artikel abhängen. Wenn der Zugriff auf Elemente, Auslagerungen und Vergleiche nicht einfach ist, wie z. B. das Vergleichen von Ganzzahlen im Ebenenspeicher, kann die Zusammenführungssortierung ein vorzuziehender Algorithmus sein.

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

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

1
minorlogic

Das ist schwer zu sagen. Das Schlimmste an 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 (auch n ist 2 ^ k) das Beste. Wenn Sie Mergesort durch quickSort teilen, ist es eins, wenn n unendlich ist Es ist, als ob der schlimmste Fall von MergeSort besser ist als der beste Fall von QuickSort. Warum verwenden wir QuickSort? Denken Sie jedoch daran, dass MergeSort nicht vorhanden ist und 2 n Speicherplatz benötigt. Und MergeSort muss auch viele Array-Kopien erstellen, was wir tun Nicht in die Analyse des Algorithmus einbeziehen. In einem Word ist MergeSort wirklich schneller als QuickSort, aber in Wirklichkeit müssen Sie den Speicherplatz berücksichtigen, die Kosten für das Kopieren von Arrays, die Zusammenführung ist langsamer als die schnelle Sortierung Experiment, bei dem ich 1000000 Stellen in Java von Random class erhalten habe, und es dauerte 2610 ms bei Mergesort, 1370 ms bei Quicksort.

1
Peter

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 QuickSort auf Arrays bekanntermaßen sehr schnell, genau wie Mergesort die häufigste Wahl für Listen ist.

Was ich mich wundere, ist, warum es so selten ist, Radix oder Eimersorte zu sehen. Sie sind O (n), zumindest in verknüpften Listen, und alles, was es braucht, ist eine Methode, um den Schlüssel in eine Ordnungszahl umzuwandeln. (Saiten und Flöße funktionieren einwandfrei.)

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

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

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

1
Anders Eurenius

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 Schnelles Sortieren: Zeitkomplexität: O (n ^ 2), Raumkomplexität: O (n)

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

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

0
pankaj

Quick Sort ist ein direkter Sortieralgorithmus, der sich besser für Arrays eignet. Die Sortierung beim Zusammenführen erfordert andererseits zusätzlichen Speicherplatz für 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 die Zusammenführungsoperation in Zusammenführung sort kann ohne zusätzlichen Speicherplatz implementiert werden.Das Zuweisen und Entfernen von zusätzlichem Speicherplatz für Arrays wirkt sich jedoch nachteilig auf die Laufzeit der Zusammenführungssortierung aus.

Ein schnelles Sortieren erfordert andererseits viel wahlfreien Speicherzugriff, und mit einem Array können wir direkt auf den Speicher zugreifen, ohne das von verknüpften Listen geforderte Durchlaufen zu müssen. Auch die schnelle Sortierung für Arrays hat eine gute Referenzlokalität, da Arrays fortlaufend im Speicher gespeichert werden.

Obwohl beide Sortieralgorithmen eine durchschnittliche Komplexität von O (NlogN) aufweisen, 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 die schlechteste/beste/durchschnittliche Sortierung immer nlogn ist, aber die schnelle Sortierung kann von n2 (schlechtester Fall, wenn Elemente bereits sortiert sind) bis nlogn (durchschnittliche/beste Fall, wenn Pivot das Array immer in zwei Teile teilt) variieren Hälften).

0
Saad