Warum ist Quicksort besser als Mergesort?

354

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?

Malik Daud Ahmad Khokhar
quelle
91
Dies ist keine sehr gute Interviewfrage. Daten aus der realen Welt werden nicht gemischt: Sie enthalten häufig eine Menge Reihenfolge, die eine intelligente Sortierung verwenden kann, und obwohl keiner der Algorithmen dies automatisch ausführt, ist es einfacher, eine Zusammenführungssortierung zu hacken, um dies zu tun, als eine Quicksortierung. GNU libc's qsort, Python's list.sortund das Array.prototype.sortin Firefox's JavaScript sind allesamt aufgemotzte Zusammenführungssorten. (GNU STL sortverwendet stattdessen Introsort, aber das könnte daran liegen, dass in C ++ das Austauschen möglicherweise
Jason Orendorff
3
@ Jason Orendorff: Warum ist es so "easier to hack a mergesort to do it than a quicksort"? Gibt es ein konkretes Beispiel, das Sie zitieren können?
Lazer
16
@eSKay Eine Zusammenführungssortierung beginnt mit der Gruppierung der Anfangsdaten in sortierten Subarrays. Wenn das Array anfänglich einige bereits sortierte Bereiche enthält, können Sie viel Zeit sparen, indem Sie erkennen, dass diese vorhanden sind, bevor Sie beginnen. Und das können Sie in O (n) Zeit tun. Spezifische Beispiele finden Sie im Quellcode der drei von mir erwähnten Projekte! Das beste Beispiel könnte Pythons Timsort sein, das hier ausführlich beschrieben wird: svn.python.org/view/python/trunk/Objects/… und implementiert in svn.python.org/view/python/trunk/Objects/… .
Jason Orendorff
4
@JasonOrendorff: Ich bin mir nicht sicher, ob ich Ihr Argument kaufe, dass Mergesort einfacher geändert werden kann, um bereits sortierte Abschnitte zu nutzen. Der Partitionierungsschritt von Quicksort kann trivial geändert werden, um anschließend zu überprüfen, ob beide resultierenden Partitionen sortiert sind, und die Rekursion anzuhalten, wenn dies der Fall ist. Dies verdoppelt möglicherweise die Anzahl der Vergleiche, ändert jedoch nichts an der O (n) -Zeitkomplexität dieses Schritts.
j_random_hacker
3
@j_random_hacker: Richtig, das habe ich angedeutet. Beachten Sie jedoch Folgendes: {10, 2, 3, 4, 5, 6, 7, 8, 1, 9} Obwohl die Partition bereits fast vollständig sortiert ist, wird sie weder nach noch nach der Partition gefunden. Und die Partition wird es vermasseln, bevor nachfolgende Aufrufe danach suchen würden. In der Zwischenzeit prüfen Zusammenführungssortierungen in den Teilungsschritten nach sortierten Sequenzen, bevor irgendwelche verschoben werden, und intelligente suchen nach solchen Läufen speziell während des Teilungsschritts (siehe: Tim Sort)
Mooing Duck

Antworten:

275

Quicksort hat eine O ( n 2 ) 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 2 ) 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 .

Konrad Rudolph
quelle
4
Der Wikipedia-Artikel besagt, dass es zu Heapsort wechselt, nicht zu Mergesort ... nur zu Ihrer Information.
7.
3
@Sev:… wie auch das Originalpapier. Vielen Dank, dass Sie auf den Fehler hingewiesen haben. - Nicht, dass es wirklich wichtig wäre, da ihre asymptotische Laufzeit gleich ist.
Konrad Rudolph
110
Warum ist dies die richtige Antwort? Alles, was es erklärt, ist, wie schnell Sortierprobleme behoben werden können. Es sagt immer noch nicht, warum die schnelle Sortierung mehr als andere verwendet wird. Ist die Antwort "Schnelle Sortierung wird mehr als andere verwendet, weil Sie nach einer Tiefe zu Heapsort wechseln können"? .. warum nicht zuerst Heapsort verwenden? .. nur versuchen zu verstehen ...
CodeObserver
16
@ p1 Gute Frage. Die eigentliche Antwort lautet, dass Quicksort für durchschnittliche Daten im Durchschnitt schneller ist als die Zusammenführungssortierung (und die Heap-Sortierung), und obwohl der schlimmste Fall von Quicksort langsamer ist als der Zusammenführungssort, kann dieser schlimmste Fall sehr leicht gemildert werden (daher meine Antwort).
Konrad Rudolph
4
Quicksort ist auch in Bezug auf das Gedächtnis besser.
Shashwat
287

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.

user11318
quelle
1
Sehr schön, habe nicht über die Annahmen nachgedacht, die für den Zugriff auf die Datenstruktur getroffen wurden. Gute Einsicht :)
Chutsu
2
Können Sie erklären, was Sie unter "auf Festplatte suchen" verstehen? Bedeutet dies, dass nach einem einzelnen Wert gesucht wird, wenn die Daten auf der Festplatte gespeichert werden?
James Wierzba
8
@JamesWierzba Ich nehme es aus dem Kontext, dass er "nach einem Ort auf der Festplatte suchen" bedeutet. "Suchen" auf einem rotierenden Plattengerät bedeutet, den Lesekopf aufzunehmen und an eine neue absolute Adresse zu verschieben, was ein notorisch langsamer Vorgang ist. Wenn Sie auf Daten in der Reihenfolge zugreifen, in der sie gespeichert wurden, muss die Festplattenhardware nicht suchen, sondern pflügt nur mit hoher Geschwindigkeit und liest die Elemente nacheinander.
nclark
1
Können einige das etwas näher erläutern? So sehe ich das: Quicksort: Wenn wir mit zufälligem Pivot arbeiten, enthält der Aufrufstapel Fragmente des Arrays, die auf zufällige Weise partitioniert sind. Dies erfordert einen wahlfreien Zugriff. Bei jedem Aufruf im Stapel bewegen sich jedoch sowohl der linke als auch der rechte Zeiger nacheinander. Ich gehe davon aus, dass diese im Cache bleiben würden. Die Swaps sind wieder Operationen an Informationen, die sich im Cache befinden (und schließlich auf die Festplatte geschrieben werden). (Fortsetzung in meinem nächsten Kommentar)
Sam
1
Nur ein Beitrag zur Vermeidung des kostspieligen Lese- / Schreibaufwands für Festplatten : Wenn Sie sehr große Daten sortieren, für die Festplattenzugriff erforderlich ist, ist es vorteilhaft, die Sortierrichtung für jeden Durchgang zu ändern. Das heißt, auf der obersten Ebene der Schleife, wenn Sie gehen aus 0Richtung nund das nächste Mal geht aus nRichtung 0. Dies bringt den Vorteil, dass die bereits im Speicher (Cache) verfügbaren Datenblöcke zurückgezogen (sortiert) und zweimal für nur einen Festplattenzugriff angegriffen werden. Ich denke, die meisten DBMS verwenden diese Optimierungstechnik.
SSD
89

Tatsächlich ist QuickSort O (n 2 ). Die durchschnittliche Laufzeit des Falls beträgt O (nlog (n)), der schlechteste Fall jedoch O (n 2 ). 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.
Dunkler Shikari
quelle
4
Tatsächlich gibt es Implementierungen von QuickSort, die O (n * log (n)) und im schlimmsten Fall nicht O (n ^ 2) sind.
JFS
12
Dies hängt auch von der Computerarchitektur ab. Quicksort profitiert vom Cache, MergeSort nicht.
Cristian Ciupitu
4
@JF Sebastian: Dies sind höchstwahrscheinlich Introsort-Implementierungen, nicht Quicksort (Introsort startet als Quicksort und wechselt zu Heapsort, wenn es nicht mehr n * log (n) sein soll).
CesarB
44
Sie können einen Mergesort implementieren.
Marcin
6
Die Zusammenführungssortierung kann auf eine Weise implementiert werden, die nur O (1) zusätzlichen Speicher erfordert, aber die meisten dieser Implementierungen leiden stark unter der Leistung.
Klarer
29

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

Asche
quelle
3
Beantwortet keine Frage, was besser ist. Der Name des Algorithmus spielt keine Rolle bei der Bestimmung, welcher besser ist.
Nick Gallimore
18

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.

Javier
quelle
9

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 .

Antti Rasinen
quelle
7

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

Gnobal
quelle
7

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

Römisches Glas
quelle
Mergesort kann direkt implementiert werden, sodass kein zusätzlicher Speicherplatz benötigt wird. Zum Beispiel mit einer doppelt verknüpften Liste: stackoverflow.com/questions/2938495/…
lanoxx
6

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.

Niyaz
quelle
5

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.

Mat Mannion
quelle
Der schlimmste Fall von Quicksort ist O (n), Mergesort O (n log n) - also gibt es dort einen großen Unterschied.
Paul23
1
Worst-Case-Quicksort ist O (n ^ 2) - kann meinen vorherigen Kommentar nicht bearbeiten und habe einen Tippfehler gemacht
paul23
@ paul23 Kommentare können gelöscht werden. Die Antwort ging auch bereits auf Ihren Punkt ein: "In den meisten realen Daten ist es möglich, Entwurfsentscheidungen zu treffen, die die Wahrscheinlichkeit minimieren, dass eine quadratische Zeit erforderlich ist"
Jim Balter,
5

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.

Lance mit Bedacht
quelle
1
"die existierenden großen Antworten" - welche sind das? Ich kann sie nicht finden.
Jim Balter
Benachrichtigen Variationen der Schnellsortierung die Vergleichsfunktion über Partitionen so, dass Situationen ausgenutzt werden können, in denen ein wesentlicher Teil des Schlüssels für alle Elemente in einer Partition gleich ist?
Supercat
4

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

Sanjeev Kumar Dangi
quelle
"Dies kann durch zufälliges Mischen gemildert werden, bevor mit dem Sortieren begonnen wird." - ähm, nein, das wäre teuer. Verwenden Sie stattdessen zufällige Drehpunkte.
Jim Balter
4

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.

xpda
quelle
2
Ihr zweiter Satz lautet "... Mergesort ist möglicherweise viel langsamer als ... Mergesort". Der erste Hinweis sollte vermutlich auf Quicksort sein.
Jonathan Leffler
Die Zusammenführungssortierung ist nur stabil, wenn der Zusammenführungsalgorithmus stabil ist. Dies ist nicht garantiert.
Klarer
@Clearer Es ist garantiert, wenn <=es eher für Vergleiche als verwendet wird <, und es gibt keinen Grund, dies nicht zu tun .
Jim Balter
@ JimBalter Ich könnte mir leicht einen instabilen Zusammenführungsalgorithmus einfallen lassen (Quicksort würde zum Beispiel diese Rolle übernehmen). Der Grund, warum die schnelle Sortierung in vielen Fällen schneller ist als die Zusammenführungssortierung, liegt nicht im geringeren Overhead, sondern darin, wie Quicksort auf Daten zugreift, was viel cachefreundlicher ist als ein Standard-Mergesort.
Klarer
@Clearer quicksort ist keine Zusammenführungssortierung ... Ihre Aussage vom 21. Dezember 14, auf die ich geantwortet habe, betraf ausschließlich die Zusammenführungssortierung und ob sie stabil ist. quicksort und was schneller ist, ist für Ihren Kommentar oder meine Antwort überhaupt nicht relevant. Ende der Diskussion für mich ... immer wieder.
Jim Balter
3

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

Appbootup
quelle
3

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.

RvPr
quelle
Dass die Pivots auf der nächsten Ebene nicht zu den Sorten gehören, ist nicht der Grund, warum QS leistungsfähiger ist. Weitere Informationen finden Sie in den anderen Antworten.
Jim Balter
@ JimBalter Auf welche "anderen Antworten" beziehen Sie sich? Die Top-Antwort besagt lediglich, dass QS "wenig zusätzlichen Speicherplatz benötigt und eine gute Cache-Lokalität aufweist", gibt jedoch keine Erklärung dafür, warum dies so ist, und liefert auch keine Zitate. Die zweite Antwort besagt einfach, dass Merge-Sort für größere Datenmengen besser ist
RvPr
Sie verschieben die Torpfosten, von der Frage, warum QS leistungsfähiger ist, bis hin zur Erklärung grundlegender Fakten zu seiner Funktionsweise. Antworten auf andere Fragen tun dies: stackoverflow.com/questions/9444714/… ... Ich hoffe, das reicht Ihnen; Ich werde nicht weiter antworten.
Jim Balter
3

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.

Shantam Mittal
quelle
Nein, der schlimmste Fall von QuickSort tritt nicht auf, wenn das Array bereits sortiert ist, es sei denn, Sie verwenden das erste oder letzte Element als Drehpunkt, aber das tut niemand.
Jim Balter
2

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.

Simon Johnson
quelle
2
Wie hat Quicksort eine bessere durchschnittliche Fallkomplexität? Sie sind beide O (nlgn). Ich würde argumentieren, dass ein Angreifer keine Eingabe für einen Sortieralgorithmus liefert ... aber im Interesse, Sicherheit nicht durch Dunkelheit anzunehmen, nehmen wir an, dass er dies könnte. Während die Laufzeit von n ^ 2 schlechter als die von nlgn ist, ist es nicht ausreichend schlechter, dass ein Webserver aufgrund eines einzelnen Angriffs abstürzt. Tatsächlich ist das DOS-Argument so gut wie null, da jeder Webserver für einen DDOS-Angriff anfällig ist und es für einen Angreifer wahrscheinlicher ist, ein verteiltes Netzwerk von Hosts zu verwenden, wobei alle TCP-SYNs überflutet werden.
CaTalyst.X
"Quicksort hat eine bessere durchschnittliche Fallkomplexität" - nein, das tut es nicht.
Jim Balter
2

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.

Peter
quelle
2

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.

Wade Anderson
quelle
O (2n) == O (n). Die richtige Aussage ist, dass Mergesort O (n) zusätzlichen Speicher benötigt (genauer gesagt, es benötigt n / 2 Hilfsspeicher). Dies gilt nicht für verknüpfte Listen.
Jim Balter
@ JimBalter Sir, würde es Ihnen etwas ausmachen, Ihre brillanten und lohnenden Ideen über ihre Leistungen als Antwort auf die Frage mit uns zu teilen? Danke im Voraus.
Snr
2

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

virco
quelle
Schlägt qsort Mergesort auch für sortierte Eingaben, wenn der Vergleich billig ist?
Eonil
2

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.

Aldian Fazrihady
quelle
Pivots haben nichts damit zu tun, warum QS weniger rekursive Aufrufe hat. Dies liegt daran, dass die Hälfte der QS-Rekursion eine Schwanzrekursion ist, die beseitigt werden kann.
Jim Balter
2

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.

Himanshu Kansal
quelle
1

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.

DJ Capelis
quelle
1

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

Anders Eurenius
quelle
1
Ich habe meinen Anteil an Radix-Sorten gesehen. Die Verwendung ist jedoch ziemlich schwierig, da die Laufzeit bei korrekter Analyse nicht O (n) beträgt, da sie von mehr als der Anzahl der Eingabeelemente abhängt. Im Allgemeinen ist es sehr schwierig, solche starken Vorhersagen zu treffen, dass die Radix-Sortierung hinsichtlich der Eingabe effizient sein muss.
Konrad Rudolph
Es ist O (n), wobei n die gesamte Eingabegröße ist, dh einschließlich der Größe der Elemente. Es ist wahr, dass Sie es implementieren können, so dass Sie mit vielen Nullen auffüllen müssen, aber es ist Unsinn, eine schlechte Implementierung zum Vergleich zu verwenden. (Das heißt, die Implementierung kann schwierig sein, ymmv.)
Anders Eurenius
Beachten Sie, dass es sich bei der Verwendung von GNU libc qsortum eine Zusammenführungssortierung handelt.
Jason Orendorff
Um genau zu sein, handelt es sich um eine Zusammenführungssortierung, es sei denn, der erforderliche temporäre Speicher kann nicht zugewiesen werden. cvs.savannah.gnu.org/viewvc/libc/stdlib/…
Jason Orendorff
1

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

minorlogic
quelle
0

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

Saad
quelle
0

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.

Pankaj
quelle
-1

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.

EvilTeach
quelle
3
Wenn es sich um die qsort () - Bibliotheksfunktion handelt, über die Sie sprechen, kann sie tatsächlich als Quicksort implementiert werden oder nicht.
Thomas Padron-McCarthy
3
Konrad, tut mir leid, dass ich ein bisschen anal bin, aber wo findest du diese Garantie? Ich kann es nicht im ISO C-Standard oder im C ++ - Standard finden.
Thomas Padron-McCarthy
2
GNU libc's qsortist eine Zusammenführungssorte, es sei denn, die Anzahl der Elemente ist wirklich gigantisch oder der temporäre Speicher kann nicht zugewiesen werden. cvs.savannah.gnu.org/viewvc/libc/stdlib/…
Jason Orendorff
-3

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

Wintermelone
quelle
Quicksort profitiert von der Zufälligkeit der Pivot-Auswahl. Der zufällige Drehpunkt würde natürlich in Richtung einer 50: 50-Partition tendieren und ist wahrscheinlich nicht konsistent in Richtung eines der Extreme. Der konstante Faktor von nlogn ist ziemlich niedrig, bis die durchschnittliche Partitionierung 60-40 oder sogar bis 70-30 beträgt.
Winter Melone
Das ist völliger Unsinn. Quicksort wird wegen seiner Leistung verwendet, nicht wegen "Philosophie" ... und die Behauptungen über "Ordnung muss verloren gehen" sind einfach falsch.
Jim Balter