Vermutung aufgrund mangelnden Kontexts - Sie fragen nach einer In-Memory-Sortierung, bei der keine Zwischenergebnisse auf die Festplatte übertragen werden müssen?
Jonathan Leffler
1
Nach diesen Animationen funktioniert die Sortierung beim Einfügen am besten bei meist sortierten Daten.
Dopple
Antworten:
259
Basierend auf der hochwissenschaftlichen Methode, animierte Gifs anzusehen, würde ich sagen, dass Insertion- und Bubble-Sorten gute Kandidaten sind.
Das ist übrigens eine hervorragende Verbindung, ein
großes Lob
5
Blasensorte ist schrecklich. Es ist immer O (n ^ 2). Nehmen Sie das zumindest aus Ihrer Antwort heraus, damit es richtig ist, bitte.
jjnguy
79
jjnguy, das ist einfach falsch. Ich denke, Sie müssen Ihre Algorithmusklasse wiederholen. Bei nahezu sortierten Daten (adaptiver Fall) ist dies O (N). Es dauert jedoch 2 Durchgänge durch die Daten und das Einfügen dauert nur 1 für nahezu sortierte Daten, was das Einfügen zum Gewinner macht. Bubble ist immer noch gut
mmcdole
3
Die Leistung verschlechtert sich erheblich, wenn Ihre Daten jedoch nicht annähernd sortiert werden. Ich persönlich würde es immer noch nicht benutzen.
Blorgbeard ist
5
Dieser Link war unterbrochen, als ich es versuchte. Versuchen Sie dies stattdessen: sorting-algorithms.com
Michael La Voie
107
Nur wenige Artikel => INSERTION SORT
Artikel sind meistens schon sortiert => INSERTION SORT
Besorgt über Worst-Case-Szenarien => HEAP SORT
Interessiert an einem guten Durchschnittsergebnis => QUICKSORT
Gegenstände werden aus einem dichten Universum gezogen => EIMERSORT
Wunsch, so wenig Code wie möglich zu schreiben => INSERTION SORT
Das ist genau die Art von Antwort, nach der ich gesucht habe. Ich lese Bücher, aber ich finde anscheinend keine klare Erklärung für die Auswahl von Alogorithmen in bestimmten Fällen. Könnten Sie dies bitte näher erläutern oder einen Link übergeben, damit ich mich darauf einlassen kann es ein bisschen mehr? Vielen Dank
Simran Kaur
9
Sie sollten hinzufügen "Daten sind bereits nach einem anderen Kriterium sortiert => MERGE SORT"
Jim Hunziker
30
Timsort
Timsort ist "ein adaptiver, stabiler, natürlicher Mergesort" mit " übernatürlicher Leistung auf vielen Arten von teilweise geordneten Arrays" (weniger als lg (N!) Vergleiche erforderlich und nur N-1)". Python ist eingebautsort()hat diesen Algorithmus seit einiger Zeit verwendet, anscheinend mit guten Ergebnissen. Es wurde speziell entwickelt, um teilweise sortierte Teilsequenzen in der Eingabe zu erkennen und zu nutzen, die häufig in realen Datensätzen auftreten. In der realen Welt ist es häufig so, dass Vergleiche viel teurer sind als das Austauschen von Elementen in einer Liste, da man normalerweise nur Zeiger austauscht, was Timsort sehr oft zu einer hervorragenden Wahl macht. Wenn Sie jedoch wissen, dass Ihre Vergleiche immer sehr billig sind (z. B. Schreiben eines Spielzeugprogramms zum Sortieren von 32-Bit-Ganzzahlen), gibt es andere Algorithmen, die wahrscheinlich eine bessere Leistung erzielen. Der einfachste Weg, Timsort zu nutzen, ist natürlich die Verwendung von Python. Da Python jedoch Open Source ist, können Sie den Code möglicherweise auch ausleihen. Alternativ enthält die obige Beschreibung mehr als genug Details, um Ihre eigene Implementierung zu schreiben.
@JF Sebastian: Timsort ist viel schneller als lg(n!)Vergleiche auf einem fast sortierten Array, bis hinunter zu O(n)! | @behrooz: Kein Vergleich Art kann einen durchschnittlichen Fall besser hat als O(n log n)und lg(n!)ist O(n log n). Der schlimmste Fall von Timsort ist also asymptotisch nicht schlimmer als der einer anderen Vergleichsart. Darüber hinaus ist der beste Fall besser oder gleich jeder anderen Vergleichssorte.
Artelius
3
Timsort ist im schlimmsten Fall immer noch O (nlogn), aber seine guten Fälle sind recht erfreulich. Hier ist ein Vergleich mit einigen Grafiken: stromberg.dnsalias.org/~strombrg/sort-comparison Beachten Sie, dass Timsort in Cython nicht annähernd so schnell war wie Pythons eingebautes Timsort in C.
user1277476
19
Einfügesortierung mit folgendem Verhalten:
Überprüfen Sie für jedes Element kin Slots 1..nzunächst, ob el[k] >= el[k-1]. Wenn ja, fahren Sie mit dem nächsten Element fort. (Überspringen Sie offensichtlich das erste Element.)
Wenn nicht, verwenden Sie die Binärsuche in Elementen 1..k-1, um die Einfügeposition zu bestimmen, und fahren Sie dann mit den Elementen darüber. (Sie können dies nur tun , wenn , k>Two Teiniger Schwellenwert ist, mit kleinen kdies übertrieben ist.)
Diese Methode führt die geringste Anzahl von Vergleichen durch.
Ich denke, die Blasensortierung könnte dies übertreffen, wenn die Anzahl der unsortierten Elemente sehr gering ist (z. B. eins oder zwei), aber im Allgemeinen scheint mir dies die wahrscheinlich beste Lösung zu sein.
Sol
Aufgrund von Schritt 1 gibt es für alle Elemente, die bereits sortiert sind, genau einen Vergleich und keine Datenverschiebungen, was offensichtlich das Beste ist, was Sie tun können. Schritt 2 ist derjenige, den Sie verbessern könnten, aber die Blase bewegt die gleiche Anzahl von Elementen und hat möglicherweise mehr Vergleiche, abhängig von Ihrem Gerät.
Jason Cohen
Nach weiteren Überlegungen denke ich, dass die Blasensorte stärker ist als ich dachte. Es ist eigentlich eine ziemlich knifflige Frage. Wenn Sie beispielsweise den Fall annehmen, dass die Liste vollständig sortiert ist, mit der Ausnahme, dass das letzte Element zuerst angezeigt wird, übertrifft die Blasensortierung Ihre Beschreibung erheblich.
Sol
Ich habe versucht, dies zu implementieren, aber die binäre Suche ist keine große Verbesserung, da Sie immer noch den gesamten Block verschieben müssen, um das Element einzufügen. Anstelle von 2xrange erhalten Sie also range + logb (range).
Es basiert auf Quicksort, vermeidet jedoch das Worst-Case-Verhalten von Quicksort für nahezu sortierte Listen.
Der Trick besteht darin, dass dieser Sortieralgorithmus die Fälle erkennt, in denen Quicksort in den Worst-Case-Modus wechselt und auf Heap- oder Merge-Sortierung umschaltet. Nahezu sortierte Partitionen werden von einer nicht-naiiven Partitionsmethode erkannt, und kleine Partitionen werden mithilfe der Einfügesortierung behandelt.
Sie erhalten den besten aller wichtigen Sortieralgorithmen für die Kosten für mehr Code und Komplexität. Und Sie können sicher sein, dass Sie niemals auf Worst-Case-Verhalten stoßen, egal wie Ihre Daten aussehen.
Wenn Sie ein C ++ - Programmierer sind, überprüfen Sie Ihren std :: sort-Algorithmus. Möglicherweise wird die introspektive Sortierung bereits intern verwendet.
Splaysort ist ein unbekanntes Sortierverfahren basierend auf Splay-Baum , eine Art von adaptivem Binärbaum. Splaysort eignet sich nicht nur für teilweise sortierte Daten, sondern auch für teilweise umgekehrt sortierte Daten oder für Daten, für die bereits eine Reihenfolge besteht. Es ist O (nlogn) im allgemeinen Fall und O (n) im Fall, wenn die Daten auf irgendeine Weise sortiert sind (vorwärts, rückwärts, Orgelpfeife usw.).
Der große Vorteil gegenüber der Einfügesortierung besteht darin, dass das O (n ^ 2) -Verhalten nicht wiederhergestellt wird, wenn die Daten überhaupt nicht sortiert sind. Sie müssen also nicht unbedingt sicher sein, dass die Daten teilweise sortiert sind, bevor Sie sie verwenden .
Sein Nachteil ist der zusätzliche Platzbedarf für die benötigte Spreizbaumstruktur sowie die Zeit, die zum Erstellen und Zerstören des Spreizbaums erforderlich ist. Abhängig von der Größe der Daten und der erwarteten Vorsortierung kann sich der Overhead für die Geschwindigkeitssteigerung jedoch lohnen.
Dijkstras Smoothsort eignet sich hervorragend für bereits sortierte Daten. Es ist eine Heapsort-Variante, die im O (n lg n) Worst-Case und O (n) Best-Case ausgeführt wird. Ich habe eine Analyse des Algorithmus geschrieben, falls Sie neugierig sind, wie er funktioniert.
Natural Mergesort ist eine weitere wirklich gute Variante - es handelt sich um eine Bottom-Up-Mergesort-Variante, bei der die Eingabe als Verkettung mehrerer verschiedener sortierter Bereiche behandelt und dann mithilfe des Zusammenführungsalgorithmus zusammengefügt wird. Sie wiederholen diesen Vorgang, bis der gesamte Eingabebereich sortiert ist. Dies läuft in O (n) Zeit, wenn die Daten bereits sortiert sind und O (n lg n) im schlimmsten Fall. Es ist sehr elegant, obwohl es in der Praxis nicht so gut ist wie einige andere adaptive Sorten wie Timsort oder Smoothsort.
Was sind die Laufzeitkonstanten von Smoothsort im Vergleich zu anderen Sortieralgorithmen? (dh Laufzeit (Smoothsort) / Laufzeit (Insertionsort) für die gleichen Daten)
Arne Babenhauserheide
4
Wenn Elemente bereits sortiert sind oder nur wenige Elemente vorhanden sind, ist dies ein perfekter Anwendungsfall für die Einfügesortierung!
Die Einfügungssortierung benötigt die Zeit O (n + die Anzahl der Inversionen).
Eine Inversion ist ein Paar, (i, j)so dass i < j && a[i] > a[j]. Das heißt, ein Paar, das nicht in Ordnung ist.
Ein Maß für "fast sortiert" ist die Anzahl der Inversionen - man könnte "fast sortierte Daten" als Daten mit wenigen Inversionen bezeichnen. Wenn man weiß, wie viele Inversionen linear sind (zum Beispiel haben Sie gerade O (1) -Elemente an eine sortierte Liste angehängt), dauert die Einfügesortierung O (n).
Wie alle anderen sagten, achten Sie auf naives Quicksort - das kann eine O (N ^ 2) -Leistung für sortierte oder nahezu sortierte Daten haben. Mit einem geeigneten Algorithmus für die Auswahl des Pivots (entweder zufällig oder im Median von drei - siehe Auswählen eines Pivots für Quicksort ) funktioniert Quicksort dennoch einwandfrei.
Im Allgemeinen besteht die Schwierigkeit bei der Auswahl von Algorithmen wie der Einfügesortierung darin, zu entscheiden, wann die Daten nicht in der richtigen Reihenfolge sind, sodass Quicksort wirklich schneller wäre.
Ich werde nicht so tun, als ob ich hier alle Antworten hätte, da ich denke, dass es erforderlich sein kann, die Algorithmen zu codieren und sie anhand repräsentativer Datenproben zu profilieren, um zu den tatsächlichen Antworten zu gelangen. Aber ich habe den ganzen Abend über diese Frage nachgedacht, und hier ist, was mir bisher eingefallen ist, und einige Vermutungen darüber, was wo am besten funktioniert.
Sei N die Anzahl der Artikel insgesamt, M die Anzahl der nicht in Ordnung befindlichen Artikel.
Die Blasensortierung muss so etwas wie 2 * M + 1 durch alle N Gegenstände führen. Wenn M sehr klein ist (0, 1, 2?), Wird dies meiner Meinung nach sehr schwer zu schlagen sein.
Wenn M klein ist (sagen wir weniger als log N), hat die Einfügesortierung eine große durchschnittliche Leistung. Wenn ich jedoch keinen Trick sehe, den ich nicht sehe, wird die Leistung im schlimmsten Fall sehr schlecht sein. (Richtig? Wenn der letzte Artikel in der Reihenfolge an erster Stelle steht, müssen Sie, soweit ich sehen kann, jeden einzelnen Artikel einfügen, was die Leistung beeinträchtigt.) Ich vermute, dass es dafür einen zuverlässigeren Sortieralgorithmus gibt Fall, aber ich weiß nicht, was es ist.
Wenn M größer ist (sagen wir gleich oder groß als log N), ist die introspektive Sortierung mit ziemlicher Sicherheit am besten.
Ausnahme: Wenn Sie im Voraus wissen, welche Elemente unsortiert sind, sollten Sie diese Elemente am besten herausziehen, nach introspektiver Sortierung sortieren und die beiden sortierten Listen zu einer sortierten Liste zusammenführen. Wenn Sie schnell herausfinden könnten, welche Artikel nicht in Ordnung sind, wäre dies auch eine gute allgemeine Lösung - aber ich konnte keinen einfachen Weg finden, dies zu tun.
Weitere Gedanken (über Nacht): Wenn M + 1 <N / M ist, können Sie die Liste nach einem Lauf von N / M in einer Reihe durchsuchen, die sortiert sind, und diesen Lauf dann in beide Richtungen erweitern, um das Out-of zu finden -Auftragspositionen. Das dauert höchstens 2N Vergleiche. Sie können dann die unsortierten Elemente sortieren und die beiden Listen sortiert zusammenführen. Die Gesamtvergleiche sollten weniger als 4N + M log2 (M) betragen, was meiner Meinung nach jede nicht spezialisierte Sortierroutine übertreffen wird. (Noch weiter gedacht: Das ist schwieriger als ich dachte, aber ich denke immer noch, dass es vernünftigerweise möglich ist.)
Eine andere Interpretation der Frage ist, dass es möglicherweise viele nicht in Ordnung befindliche Elemente gibt, diese sich jedoch sehr nahe an der Stelle befinden, an der sie in der Liste enthalten sein sollten. (Stellen Sie sich vor, Sie beginnen mit einer sortierten Liste und tauschen jedes andere Element gegen das nachfolgende aus.) In diesem Fall funktioniert die Blasensortierung meiner Meinung nach sehr gut. Ich denke, die Anzahl der Durchgänge ist proportional zu der am weitesten entfernten Position eines Elements ist. Die Sortierung nach Einfügungen funktioniert schlecht, da jeder Artikel außerhalb der Reihenfolge eine Einfügung auslöst. Ich vermute, dass eine introspektive Art oder ähnliches auch gut funktionieren wird.
Wenn Sie eine spezielle Implementierung zum Sortieren von Algorithmen, Datenstrukturen oder anderen Elementen benötigen, die mit den oben genannten verknüpft sind, kann ich Ihnen das hervorragende Projekt "Datenstrukturen und Algorithmen" auf CodePlex empfehlen ?
Es wird alles haben, was Sie brauchen, ohne das Rad neu zu erfinden.
Dieser schönen Sammlung von Sortieralgorithmen für diesen Zweck in den Antworten scheint Gnome Sort zu fehlen , was ebenfalls geeignet wäre und wahrscheinlich den geringsten Implementierungsaufwand erfordert.
Die Einfügesortierung ist der beste Fall O (n) bei sortierter Eingabe. Und es ist sehr nah an meist sortierten Eingaben (besser als schnelle Sortierung).
Konsistenz ist hier nicht von Belang. Heapsort gibt selbst bei sortierten Daten O (n lg n) und ist nicht wirklich anpassungsfähig. Durchführbare Optionen können sein: Einfügesortierung, Timsort und Bubblesort.
Max
0
Die Blasensortierung (oder, noch sicherer, die bidirektionale Blasensortierung) ist wahrscheinlich ideal für meist sortierte Listen, obwohl ich wette, dass eine optimierte Kammsortierung (mit einer viel geringeren anfänglichen Lückengröße) etwas schneller wäre, wenn die Liste nicht vorhanden wäre. t ganz so perfekt sortiert. Die Kammsortierung wird zur Blasensortierung.
Dieser "soweit es mich betrifft" -Test der Algorithmus-Effizienz hat meinen Tag aufgehellt :) Wenn Sie jedoch "Schreiben und Einfügen" schreiben, meinen Sie damit "Einfügen sortieren" (was bereits in früheren Antworten erwähnt wurde) oder bieten Sie an eine neue Art von Algorithmus? Wenn ja, erweitern Sie bitte Ihre Antwort.
YoniLavi
0
Die Blasensortierung ist definitiv der Gewinner. Die nächste auf dem Radar wäre die Einfügungssortierung.
Ich würde vorschlagen, dass Sie sich vor dem Posten die verfügbaren Antworten ansehen, um Duplikate zu vermeiden.
Angainor
-1
Halten Sie sich von QuickSort fern - es ist sehr ineffizient für vorsortierte Daten. Die Einfügesortierung verarbeitet nahezu sortierte Daten gut, indem so wenige Werte wie möglich verschoben werden.
Antworten:
Basierend auf der hochwissenschaftlichen Methode, animierte Gifs anzusehen, würde ich sagen, dass Insertion- und Bubble-Sorten gute Kandidaten sind.
quelle
Nur wenige Artikel => INSERTION SORT
Artikel sind meistens schon sortiert => INSERTION SORT
Besorgt über Worst-Case-Szenarien => HEAP SORT
Interessiert an einem guten Durchschnittsergebnis => QUICKSORT
Gegenstände werden aus einem dichten Universum gezogen => EIMERSORT
Wunsch, so wenig Code wie möglich zu schreiben => INSERTION SORT
quelle
Timsort
Timsort ist "ein adaptiver, stabiler, natürlicher Mergesort" mit " übernatürlicher Leistung auf vielen Arten von teilweise geordneten Arrays" (weniger als lg (N!) Vergleiche erforderlich und nur N-1)". Python ist eingebaut
sort()hat diesen Algorithmus seit einiger Zeit verwendet, anscheinend mit guten Ergebnissen. Es wurde speziell entwickelt, um teilweise sortierte Teilsequenzen in der Eingabe zu erkennen und zu nutzen, die häufig in realen Datensätzen auftreten. In der realen Welt ist es häufig so, dass Vergleiche viel teurer sind als das Austauschen von Elementen in einer Liste, da man normalerweise nur Zeiger austauscht, was Timsort sehr oft zu einer hervorragenden Wahl macht. Wenn Sie jedoch wissen, dass Ihre Vergleiche immer sehr billig sind (z. B. Schreiben eines Spielzeugprogramms zum Sortieren von 32-Bit-Ganzzahlen), gibt es andere Algorithmen, die wahrscheinlich eine bessere Leistung erzielen. Der einfachste Weg, Timsort zu nutzen, ist natürlich die Verwendung von Python. Da Python jedoch Open Source ist, können Sie den Code möglicherweise auch ausleihen. Alternativ enthält die obige Beschreibung mehr als genug Details, um Ihre eigene Implementierung zu schreiben.quelle
lg(n!)Vergleiche auf einem fast sortierten Array, bis hinunter zuO(n)! | @behrooz: Kein Vergleich Art kann einen durchschnittlichen Fall besser hat alsO(n log n)undlg(n!)istO(n log n). Der schlimmste Fall von Timsort ist also asymptotisch nicht schlimmer als der einer anderen Vergleichsart. Darüber hinaus ist der beste Fall besser oder gleich jeder anderen Vergleichssorte.Einfügesortierung mit folgendem Verhalten:
kin Slots1..nzunächst, obel[k] >= el[k-1]. Wenn ja, fahren Sie mit dem nächsten Element fort. (Überspringen Sie offensichtlich das erste Element.)1..k-1, um die Einfügeposition zu bestimmen, und fahren Sie dann mit den Elementen darüber. (Sie können dies nur tun , wenn ,k>TwoTeiniger Schwellenwert ist, mit kleinenkdies übertrieben ist.)Diese Methode führt die geringste Anzahl von Vergleichen durch.
quelle
Versuchen Sie es mit einer introspektiven Sortierung. http://en.wikipedia.org/wiki/Introsort
Es basiert auf Quicksort, vermeidet jedoch das Worst-Case-Verhalten von Quicksort für nahezu sortierte Listen.
Der Trick besteht darin, dass dieser Sortieralgorithmus die Fälle erkennt, in denen Quicksort in den Worst-Case-Modus wechselt und auf Heap- oder Merge-Sortierung umschaltet. Nahezu sortierte Partitionen werden von einer nicht-naiiven Partitionsmethode erkannt, und kleine Partitionen werden mithilfe der Einfügesortierung behandelt.
Sie erhalten den besten aller wichtigen Sortieralgorithmen für die Kosten für mehr Code und Komplexität. Und Sie können sicher sein, dass Sie niemals auf Worst-Case-Verhalten stoßen, egal wie Ihre Daten aussehen.
Wenn Sie ein C ++ - Programmierer sind, überprüfen Sie Ihren std :: sort-Algorithmus. Möglicherweise wird die introspektive Sortierung bereits intern verwendet.
quelle
Splaysort ist ein unbekanntes Sortierverfahren basierend auf Splay-Baum , eine Art von adaptivem Binärbaum. Splaysort eignet sich nicht nur für teilweise sortierte Daten, sondern auch für teilweise umgekehrt sortierte Daten oder für Daten, für die bereits eine Reihenfolge besteht. Es ist O (nlogn) im allgemeinen Fall und O (n) im Fall, wenn die Daten auf irgendeine Weise sortiert sind (vorwärts, rückwärts, Orgelpfeife usw.).
Der große Vorteil gegenüber der Einfügesortierung besteht darin, dass das O (n ^ 2) -Verhalten nicht wiederhergestellt wird, wenn die Daten überhaupt nicht sortiert sind. Sie müssen also nicht unbedingt sicher sein, dass die Daten teilweise sortiert sind, bevor Sie sie verwenden .
Sein Nachteil ist der zusätzliche Platzbedarf für die benötigte Spreizbaumstruktur sowie die Zeit, die zum Erstellen und Zerstören des Spreizbaums erforderlich ist. Abhängig von der Größe der Daten und der erwarteten Vorsortierung kann sich der Overhead für die Geschwindigkeitssteigerung jedoch lohnen.
Ein Artikel über Splaysort wurde in Software - Practice & Experience veröffentlicht.
quelle
Insertion oder Shell Sort!
quelle
Dijkstras Smoothsort eignet sich hervorragend für bereits sortierte Daten. Es ist eine Heapsort-Variante, die im O (n lg n) Worst-Case und O (n) Best-Case ausgeführt wird. Ich habe eine Analyse des Algorithmus geschrieben, falls Sie neugierig sind, wie er funktioniert.
Natural Mergesort ist eine weitere wirklich gute Variante - es handelt sich um eine Bottom-Up-Mergesort-Variante, bei der die Eingabe als Verkettung mehrerer verschiedener sortierter Bereiche behandelt und dann mithilfe des Zusammenführungsalgorithmus zusammengefügt wird. Sie wiederholen diesen Vorgang, bis der gesamte Eingabebereich sortiert ist. Dies läuft in O (n) Zeit, wenn die Daten bereits sortiert sind und O (n lg n) im schlimmsten Fall. Es ist sehr elegant, obwohl es in der Praxis nicht so gut ist wie einige andere adaptive Sorten wie Timsort oder Smoothsort.
quelle
Wenn Elemente bereits sortiert sind oder nur wenige Elemente vorhanden sind, ist dies ein perfekter Anwendungsfall für die Einfügesortierung!
quelle
Die Einfügungssortierung benötigt die Zeit O (n + die Anzahl der Inversionen).
Eine Inversion ist ein Paar,
(i, j)so dassi < j && a[i] > a[j]. Das heißt, ein Paar, das nicht in Ordnung ist.Ein Maß für "fast sortiert" ist die Anzahl der Inversionen - man könnte "fast sortierte Daten" als Daten mit wenigen Inversionen bezeichnen. Wenn man weiß, wie viele Inversionen linear sind (zum Beispiel haben Sie gerade O (1) -Elemente an eine sortierte Liste angehängt), dauert die Einfügesortierung O (n).
quelle
Wie alle anderen sagten, achten Sie auf naives Quicksort - das kann eine O (N ^ 2) -Leistung für sortierte oder nahezu sortierte Daten haben. Mit einem geeigneten Algorithmus für die Auswahl des Pivots (entweder zufällig oder im Median von drei - siehe Auswählen eines Pivots für Quicksort ) funktioniert Quicksort dennoch einwandfrei.
Im Allgemeinen besteht die Schwierigkeit bei der Auswahl von Algorithmen wie der Einfügesortierung darin, zu entscheiden, wann die Daten nicht in der richtigen Reihenfolge sind, sodass Quicksort wirklich schneller wäre.
quelle
Ich werde nicht so tun, als ob ich hier alle Antworten hätte, da ich denke, dass es erforderlich sein kann, die Algorithmen zu codieren und sie anhand repräsentativer Datenproben zu profilieren, um zu den tatsächlichen Antworten zu gelangen. Aber ich habe den ganzen Abend über diese Frage nachgedacht, und hier ist, was mir bisher eingefallen ist, und einige Vermutungen darüber, was wo am besten funktioniert.
Sei N die Anzahl der Artikel insgesamt, M die Anzahl der nicht in Ordnung befindlichen Artikel.
Die Blasensortierung muss so etwas wie 2 * M + 1 durch alle N Gegenstände führen. Wenn M sehr klein ist (0, 1, 2?), Wird dies meiner Meinung nach sehr schwer zu schlagen sein.
Wenn M klein ist (sagen wir weniger als log N), hat die Einfügesortierung eine große durchschnittliche Leistung. Wenn ich jedoch keinen Trick sehe, den ich nicht sehe, wird die Leistung im schlimmsten Fall sehr schlecht sein. (Richtig? Wenn der letzte Artikel in der Reihenfolge an erster Stelle steht, müssen Sie, soweit ich sehen kann, jeden einzelnen Artikel einfügen, was die Leistung beeinträchtigt.) Ich vermute, dass es dafür einen zuverlässigeren Sortieralgorithmus gibt Fall, aber ich weiß nicht, was es ist.
Wenn M größer ist (sagen wir gleich oder groß als log N), ist die introspektive Sortierung mit ziemlicher Sicherheit am besten.
Ausnahme: Wenn Sie im Voraus wissen, welche Elemente unsortiert sind, sollten Sie diese Elemente am besten herausziehen, nach introspektiver Sortierung sortieren und die beiden sortierten Listen zu einer sortierten Liste zusammenführen. Wenn Sie schnell herausfinden könnten, welche Artikel nicht in Ordnung sind, wäre dies auch eine gute allgemeine Lösung - aber ich konnte keinen einfachen Weg finden, dies zu tun.
Weitere Gedanken (über Nacht): Wenn M + 1 <N / M ist, können Sie die Liste nach einem Lauf von N / M in einer Reihe durchsuchen, die sortiert sind, und diesen Lauf dann in beide Richtungen erweitern, um das Out-of zu finden -Auftragspositionen. Das dauert höchstens 2N Vergleiche. Sie können dann die unsortierten Elemente sortieren und die beiden Listen sortiert zusammenführen. Die Gesamtvergleiche sollten weniger als 4N + M log2 (M) betragen, was meiner Meinung nach jede nicht spezialisierte Sortierroutine übertreffen wird. (Noch weiter gedacht: Das ist schwieriger als ich dachte, aber ich denke immer noch, dass es vernünftigerweise möglich ist.)
Eine andere Interpretation der Frage ist, dass es möglicherweise viele nicht in Ordnung befindliche Elemente gibt, diese sich jedoch sehr nahe an der Stelle befinden, an der sie in der Liste enthalten sein sollten. (Stellen Sie sich vor, Sie beginnen mit einer sortierten Liste und tauschen jedes andere Element gegen das nachfolgende aus.) In diesem Fall funktioniert die Blasensortierung meiner Meinung nach sehr gut. Ich denke, die Anzahl der Durchgänge ist proportional zu der am weitesten entfernten Position eines Elements ist. Die Sortierung nach Einfügungen funktioniert schlecht, da jeder Artikel außerhalb der Reihenfolge eine Einfügung auslöst. Ich vermute, dass eine introspektive Art oder ähnliches auch gut funktionieren wird.
quelle
Wenn Sie eine spezielle Implementierung zum Sortieren von Algorithmen, Datenstrukturen oder anderen Elementen benötigen, die mit den oben genannten verknüpft sind, kann ich Ihnen das hervorragende Projekt "Datenstrukturen und Algorithmen" auf CodePlex empfehlen ?
Es wird alles haben, was Sie brauchen, ohne das Rad neu zu erfinden.
Nur mein kleines Salzkorn.
quelle
Dieser schönen Sammlung von Sortieralgorithmen für diesen Zweck in den Antworten scheint Gnome Sort zu fehlen , was ebenfalls geeignet wäre und wahrscheinlich den geringsten Implementierungsaufwand erfordert.
quelle
Die Einfügesortierung ist der beste Fall O (n) bei sortierter Eingabe. Und es ist sehr nah an meist sortierten Eingaben (besser als schnelle Sortierung).
quelle
Nachdenken Heap. Ich glaube, es ist die beständigste der O (n lg n) -Sorten.
quelle
Die Blasensortierung (oder, noch sicherer, die bidirektionale Blasensortierung) ist wahrscheinlich ideal für meist sortierte Listen, obwohl ich wette, dass eine optimierte Kammsortierung (mit einer viel geringeren anfänglichen Lückengröße) etwas schneller wäre, wenn die Liste nicht vorhanden wäre. t ganz so perfekt sortiert. Die Kammsortierung wird zur Blasensortierung.
quelle
Nun, es hängt vom Anwendungsfall ab. Wenn Sie wissen, welche Elemente geändert werden, ist das Entfernen und Einfügen für mich der beste Fall.
quelle
Die Blasensortierung ist definitiv der Gewinner. Die nächste auf dem Radar wäre die Einfügungssortierung.
quelle
Halten Sie sich von QuickSort fern - es ist sehr ineffizient für vorsortierte Daten. Die Einfügesortierung verarbeitet nahezu sortierte Daten gut, indem so wenige Werte wie möglich verschoben werden.
quelle