Wann wird jeder Sortieralgorithmus verwendet? [geschlossen]

170

Was sind die Anwendungsfälle, in denen ein bestimmter Sortieralgorithmus anderen vorgezogen wird - Sortierung gegen QuickSort gegen Heapsort gegen Intro-Sortierung zusammenführen usw.?

Gibt es eine empfohlene Anleitung für deren Verwendung, die auf der Größe, dem Typ der Datenstruktur, dem verfügbaren Speicher und Cache sowie der CPU-Leistung basiert?

algorithm sorting Sam
quelle
Eine Reihe von Animationen für verschiedene Arten von Daten und Algorithmen finden Sie unter <a href=" sorting-algorithms.com/"> sorting-algorithms.com </ a >
Chip Uni
2
Ein Leitfaden wie bigocheatsheet.com für dieses Zeug wäre greaaaat
K - Die Toxizität in SO wächst.
@ChipUni hier ist der feste Link: toptal.com/developers/sorting-algorithms
Eric
2
Warum ist diese Frage geschlossen?
Arvand

Antworten:

316

Erstens eine Definition, da sie ziemlich wichtig ist: Eine stabile Sortierung ist eine, die garantiert keine Elemente mit identischen Schlüsseln neu anordnet.

Empfehlungen:

Schnelle Sortierung: Wenn Sie keine stabile Sortierung benötigen und die durchschnittliche Fallleistung wichtiger ist als die Leistung im schlechtesten Fall. Eine schnelle Sortierung ist im Durchschnitt O (N log N), im schlimmsten Fall O (N ^ 2). Eine gute Implementierung verwendet O (log N) -Hilfsspeicher in Form von Stapelspeicher für die Rekursion.

Sortierung zusammenführen: Wenn Sie eine stabile Sortierung O (N log N) benötigen, ist dies Ihre einzige Option. Die einzigen Nachteile sind, dass es O (N) -Hilfsraum verwendet und eine etwas größere Konstante als eine schnelle Sortierung hat. Es gibt einige In-Place-Merge-Sorten, aber AFAIK sind alle entweder nicht stabil oder schlechter als O (N log N). Sogar die vorhandenen O (N log N) -Sorten haben eine so viel größere Konstante als die einfache alte Zusammenführungssorte, dass sie eher theoretische Kuriositäten als nützliche Algorithmen sind.

Heap-Sortierung: Wenn Sie keine stabile Sortierung benötigen und sich mehr um die Worst-Case-Leistung als um die durchschnittliche Case-Leistung kümmern. Es ist garantiert O (N log N) und verwendet O (1) -Hilfsraum, was bedeutet, dass Ihnen bei sehr großen Eingaben nicht unerwartet der Heap- oder Stapelspeicher ausgeht.

Introsort: Dies ist eine schnelle Sortierung, die nach einer bestimmten Rekursionstiefe zu einer Heap-Sortierung wechselt, um den O (N ^ 2) -Schlankfall der schnellen Sortierung zu umgehen. Es ist fast immer besser als eine einfache alte schnelle Sortierung, da Sie den durchschnittlichen Fall einer schnellen Sortierung mit garantierter O (N log N) -Leistung erhalten. Wahrscheinlich ist der einzige Grund, stattdessen eine Heap-Sortierung zu verwenden, in stark speicherbeschränkten Systemen, in denen der Stapelspeicherplatz O (log N) praktisch von Bedeutung ist.

Einfügesortierung : Wenn N garantiert klein ist, auch als Basisfall für eine schnelle Sortierung oder Zusammenführungssortierung. Während dies O (N ^ 2) ist, hat es eine sehr kleine Konstante und ist eine stabile Sorte.

Blasensortierung, Auswahlsortierung : Wenn Sie etwas schnelles und schmutziges tun und aus irgendeinem Grund nicht einfach den Sortieralgorithmus der Standardbibliothek verwenden können. Der einzige Vorteil, den diese gegenüber der Einfügesortierung haben, ist die etwas einfachere Implementierung.

Nicht vergleichbare Sortierungen: Unter relativ begrenzten Bedingungen ist es möglich, die O (N log N) -Sperre zu durchbrechen und in O (N) zu sortieren. Hier sind einige Fälle, in denen dies einen Versuch wert ist:

Sortierung zählen: Wenn Sie Ganzzahlen mit einem begrenzten Bereich sortieren.

Radix-Sortierung: Wenn log (N) signifikant größer als K ist, wobei K die Anzahl der Radix-Ziffern ist.

Bucket-Sortierung: Wenn Sie sicherstellen können, dass Ihre Eingabe ungefähr gleichmäßig verteilt ist.

Dsimcha
quelle
1
Wie ich mich erinnere, hat die Heap-Sortierung auch eine sehr vorhersehbare Laufzeit, da zwischen verschiedenen Eingaben derselben Größe nur geringe Abweichungen bestehen. Dies ist jedoch weniger interessant als die konstante räumliche Begrenzung. Ich finde auch, dass die Einfügungssortierung von den n ^ 2-Sortierungen am einfachsten zu implementieren ist, aber vielleicht bin das nur ich. Schließlich möchten Sie vielleicht auch die Shell-Sortierung erwähnen, die fast so einfach zu implementieren ist wie die Einfügesortierung, aber eine bessere Leistung aufweist, obwohl sie immer noch nicht n log n ist.
JaakkoK
29
Bogosort nicht vergessen ! ;-)
Alex Brasetvik
2
+1 Sehr interessant. Möchten Sie erklären, wie Sie "garantieren können ... ungefähr gleichmäßig verteilt". für Bucket Sort?
Sam Overton
2
Warum sollte Introsort wesentlich langsamer sein als schnelles Sortieren? Der einzige Aufwand besteht darin, die Rekursionstiefe zu zählen, die vernachlässigbar sein sollte. Es wechselt erst, nachdem die Rekursion viel tiefer ist, als es in einem guten Fall der schnellen Sortierung sein sollte.
Dsimcha
2
Sie erwähnen nicht, dass der beste Fall der Blasensortierung O (n) ist!
Tara
33

Quicksort ist normalerweise im Durchschnitt am schnellsten, hat aber einige ziemlich böse Worst-Case-Verhaltensweisen. Wenn Sie also garantieren müssen, dass Sie keine schlechten Daten erhalten O(N^2), sollten Sie dies vermeiden.

Merge-Sort verwendet zusätzlichen Speicher, eignet sich jedoch besonders für die externe Sortierung (dh große Dateien, die nicht in den Speicher passen).

Die Heap-Sortierung kann direkt sortiert werden und weist nicht das quadratische Verhalten im ungünstigsten Fall auf, ist jedoch in den meisten Fällen im Durchschnitt langsamer als die Quicksortierung.

Wenn nur Ganzzahlen in einem eingeschränkten Bereich beteiligt sind, können Sie eine Art Radix-Sortierung verwenden, um dies sehr schnell zu machen.

In 99% der Fälle sind Sie mit den Bibliothekssortierungen einverstanden, die normalerweise auf Quicksort basieren.

Eli Bendersky
quelle
6
+1: Für "In 99% der Fälle sind Sie mit den Bibliothekssortierungen einverstanden, die normalerweise auf Quicksort basieren".
Jim G.
Durch zufälliges Schwenken erhält Quicksort für alle praktischen Zwecke eine Laufzeit von O (nlogn), ohne dass Garantien für fehlerhafte Daten erforderlich sind. Ich glaube wirklich nicht, dass irgendjemand einen O (n ^ 2) Quicksort für irgendeinen Produktionscode implementiert.
MAK
2
MAK, außer zum Beispiel der C-Standardbibliothek qsort? ( google.com/codesearch/… ) - auf die sich die meisten "Produktionscode" -Sorten stützen
Eli Bendersky
Die Bibliothekssortierung basiert normalerweise nicht auf Quicksort, da sie nicht stabil ist. Fast alle höheren Sprachen (für C zu erwarten) bieten eine stabile Sortierung. In den meisten Fällen weiß ich, dass Sie eine stabile oder zumindest deterministische Sorte benötigen.
12431234123412341234123
3

Was die bereitgestellten Links zu Vergleichen / Animationen nicht berücksichtigen, ist, wenn die Datenmenge den verfügbaren Speicher überschreitet - zu diesem Zeitpunkt dominiert die Anzahl der Durchgänge über die Daten, dh die E / A-Kosten, die Laufzeit. Wenn Sie dies tun müssen, lesen Sie "Externe Sortierung", die normalerweise Varianten von Merge- und Heap-Sortierungen abdeckt.

http://corte.si/posts/code/visualisingsorting/index.html und http://corte.si/posts/code/timsort/index.html haben auch einige coole Bilder, die verschiedene Sortieralgorithmen vergleichen.

Alex Brasetvik
quelle
0

@dsimcha hat geschrieben: Zählsortierung: Wenn Sie Ganzzahlen mit einem begrenzten Bereich sortieren

Ich würde das ändern in:

Zählsortierung: Wenn Sie positive Ganzzahlen sortieren (0 - Integer.MAX_VALUE-2 aufgrund der Schublade).

Sie können die Max- und Min-Werte auch in linearer Zeit als Effizienzheuristik erhalten.
Außerdem benötigen Sie mindestens n zusätzlichen Platz für das Zwischenarray und es ist offensichtlich stabil.

/**
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

(obwohl es tatsächlich MAX_VALUE-2 erlaubt) siehe: Haben Java-Arrays eine maximale Größe?

Ich würde auch erklären, dass die Radix-Sortierkomplexität O (wn) für n Schlüssel ist, die ganze Zahlen der Wortgröße w sind. Manchmal wird w als Konstante dargestellt, wodurch die Radix-Sortierung besser ist (für ausreichend große n) als die besten vergleichsbasierten Sortieralgorithmen, die alle O (n log n) -Vergleiche durchführen, um n Schlüssel zu sortieren. Im Allgemeinen kann w jedoch nicht als Konstante betrachtet werden: Wenn alle n Schlüssel verschieden sind, muss w mindestens log n sein, damit eine Maschine mit wahlfreiem Zugriff sie im Speicher speichern kann, was bestenfalls eine zeitliche Komplexität O ergibt (n log n). (aus Wikipedia)

Droiden-Teehaus
quelle