Wie jeder weiß, kann das Sortieren auf Austauschen, Einfügen, Auswählen, Zusammenführen und Verteilen basieren.
Wenn jedoch verschiedene Methoden im Algorithmus kombiniert werden, gehört er zur Klasse der Hybridsorten.
Dieser Artikel wurde mit der Unterstützung von EDISON verfasst.
Wir kümmern uns um die Fertigstellung und Wartung von Websites auf 1C-Bitrix sowie um die Entwicklung von mobilen Anwendungen für Android und iOS .
Wir lieben die Theorie der Algorithmen! ;-)
Erinnern wir uns schnell daran, welche Klassen Sortieralgorithmen haben und welche Merkmale sie haben.
Sortierungen austauschen
Die Elemente des Arrays werden paarweise miteinander verglichen und es erfolgt ein Austausch gegen ungeordnete Paare.
Der effektivste Vertreter dieser Klasse ist die legendäre
schnelle Sorte .
Einfügesortierung
Elemente aus dem unsortierten Teil des Arrays werden an ihren Stellen im sortierten Bereich eingefügt.
In dieser Klasse
wird am häufigsten
nach einfachen Einfügungen sortiert . Obwohl dieser Algorithmus eine durchschnittliche Komplexität von O (
n 2 ) aufweist, funktioniert diese Sortierung bei fast geordneten Arrays sehr schnell - auf diesen erreicht die Komplexität O (
n ). Darüber hinaus ist diese Sortierung eine der besten Optionen für die Verarbeitung kleiner Arrays.
Zu dieser Klasse gehört auch das
Sortieren nach dem binären Suchbaum .
Nach Auswahl sortieren
Im ungeordneten Bereich wird das Minimum / Maximum-Element ausgewählt, das an das Ende / den Anfang des unsortierten Teils des Arrays übertragen wird.
Das Sortieren mit einer einfachen Auswahl funktioniert sehr langsam (im Durchschnitt O (
n 2 )), aber in dieser Klasse gibt es eine schwierige
Sortierung nach einem Haufen (auch als
pyramidenförmige Sortierung bezeichnet ), die eine zeitliche Komplexität von O (
n log
n ) aufweist - und die sehr wertvoll ist. Es gibt keine entarteten Fälle dieser Sortierung, unabhängig von den eingehenden Daten. Übrigens hat diese Sortierung auch nicht die besten Fälle für eingehende Daten.
Sortierungen zusammenführen
Die sortierten Bereiche werden in das Array aufgenommen und zusammengeführt, dh die kleineren sortierten Subarrays werden zu einem größeren sortierten Subarray zusammengefasst.
Wenn zwei Subarrays sortiert sind, ist das Kombinieren eine einfach zu implementierende und schnell durchzuführende Operation. Die Kehrseite der Medaille ist, dass das Zusammenführen fast immer die Kosten für zusätzlichen O (
n ) -Speicher erfordert - obwohl eine äußerst kleine Anzahl besonders ausgefeilter Sortieroptionen für das Zusammenführen bekannt ist, bei denen die Speicherkosten O (1) betragen.
Nach Verteilung sortieren
Die Elemente des Arrays werden verteilt und in Klassen umverteilt, bis das Array einen sortierten Zustand annimmt.
Elemente werden entweder abhängig von ihrem Wert (den sogenannten
Zählsortierungen ) oder abhängig vom Wert einzelner Ziffern (dies sind bereits
bitweise Sortierungen ) in Gruppen gestreut.
Zu dieser Klasse gehört auch die Eimersortierung.
Ein Merkmal der Sortierung nach Verteilung ist, dass sie entweder keine paarweisen Vergleiche von Elementen untereinander verwenden oder solche Vergleiche in geringem Umfang vorliegen. Daher ist die Sortierung nach Verteilung oft schneller als die Geschwindigkeit, beispielsweise die schnelle Sortierung. Andererseits erfordert das Sortieren nach Verteilung häufig viel zusätzlichen Speicher, da Gruppen von ständig neu verteilten Elementen irgendwo gespeichert werden müssen.
Auseinandersetzungen darüber, welche Sortierung
die beste ist, sind sehr häufig, aber Tatsache ist, dass es keinen idealen Algorithmus für alle Gelegenheiten gibt und nicht geben kann. Zum Beispiel ist das schnelle Sortieren in den meisten Situationen sehr schnell (aber nicht am schnellsten), es stößt jedoch auch auf entartete Fälle, in denen ein Absturz auftritt. Das Sortieren nach einfachen Einfügungen ist langsam, aber bei fast geordneten Arrays werden andere Algorithmen leicht umgangen. Die Heap-Sortierung funktioniert bei eingehenden Daten recht schnell, ist jedoch unter bestimmten Bedingungen nicht so schnell wie andere Sortierungen, und es gibt keine Möglichkeit, die Pyramide zu beschleunigen. Das Sortieren durch Zusammenführen ist langsamer als das schnelle Sortieren. Wenn das Array jedoch sortierte Unterfelder enthält, ist das Zusammenführen schneller als das Sortieren durch schnelles Sortieren. Wenn das Array viele sich wiederholende Elemente enthält oder wir die Zeilen sortieren, ist die Sortierung nach Verteilung am wahrscheinlichsten. Jede Methode ist in ihrer günstigsten Situation besonders gut.
Dennoch erfinden Programmierer weiterhin die schnellsten Sortierungen der Welt und synthetisieren die effektivsten Methoden aus verschiedenen Klassen. Mal sehen, wie erfolgreich es für sie ist.
Da im Artikel viele nicht-triviale Algorithmen erwähnt werden, beschreibe ich nur kurz die Grundlagen ihrer Arbeit, ohne den Artikel mit Animationen und detaillierten Erklärungen zu überladen. In Zukunft wird es separate Artikel geben, in denen es Cartoons für jeden Algorithmus und detaillierte, subtile Nuancen geben wird.
Einfügen + Zusammenführen
Eine rein empirische Schlussfolgerung ist, dass Fusion und / oder Insertion in Hybriden am häufigsten verwendet werden. In den meisten Sortierungen wird die eine oder die andere Methode gefunden oder beides zusammen. Und dafür gibt es eine logische Erklärung.
Sortiererfinder bemühen sich häufig, parallele Algorithmen zu erstellen, die gleichzeitig verschiedene Teile eines Arrays anordnen. Der beste Weg, um mit mehreren sortierten Subarrays umzugehen, besteht darin, sie zusammenzuführen - dies ist der schnellste Weg.
Moderne Algorithmen verwenden häufig die Rekursion. Während eines rekursiven Abstiegs wird das Array normalerweise in zwei Teile geteilt, auf der untersten Ebene wird das Array geordnet. Bei der Rückkehr zu höheren Rekursionsebenen stellt sich die Frage, ob auf niedrigeren Ebenen sortierte Subarrays kombiniert werden sollen.
Was die Einfügungen betrifft, so werden in hybriden Algorithmen in bestimmten Stadien oft ungefähr geordnete Unteranordnungen erhalten, die am besten mit Hilfe von Einfügungen zur endgültigen Anordnung geführt werden.
Diese Gruppe enthält Hybridsorten, bei denen eine Zusammenführung und Einfügung erfolgt, und diese Methoden werden sehr unterschiedlich verwendet.
Sortieren nach Zusammenführungseinfügung
Ford-Johnson-Algorithmus :: Ford-Johnson-Algorithmus
Zusammenführen + Einfügen
Ein sehr alter Weg, schon 1959. Es wird ausführlich in der unsterblichen Arbeit von Donald Knuth, "Die Kunst des Programmierens", Band 3, "Sortieren und Suchen", Kapitel 5, "Sortieren", Abschnitt 5.3, "Optimale Sortierung", Unterabschnitt "Sortieren mit einer minimalen Anzahl von Vergleichen" und Abschnitt "Sortieren nach Einfügungen und Zusammenführen" beschrieben. .
Sortieren hat jetzt keinen praktischen Wert, ist aber für diejenigen interessant, die die Theorie der Algorithmen lieben. Das Problem, einen Weg zu finden, um
n Elemente mit der geringsten Anzahl von Vergleichen zu sortieren, wird in Betracht gezogen. Eine nicht triviale heuristische Modifikation wird für die Einfügungssortierung (eine solche Einfügung finden Sie sonst nirgendwo) unter Verwendung von
Jacobstal-Zahlen vorgeschlagen, um die Anzahl der Vergleiche zu minimieren. Bisher ist auch bekannt, dass dies nicht die beste Option ist und Sie noch geschickter ausweichen und noch weniger Vergleiche erhalten können. Im Allgemeinen ist die akademische Standardsortierung nicht von praktischem Nutzen, aber für Kenner des Genres ist es ein Vergnügen, solche Tricks mit einer algebraischen Tendenz zu disassemblieren.
Tim Sort :: Timsort
Einfügen + Zusammenführen
Gepostet von Tim Peters vor 15 Jahren und jetztDiese Sortierung auf Habré wird sehr oft erinnert.
These: In einem Array werden fast geordnete kleine Subarrays gesucht, für die die Einfügesortierung verwendet wird. Diese Subarrays werden dann mit Merge zusammengeführt.
Die Zusammenführung in TimSort ist der interessanteste Teil: Die klassische Zusammenführung nach oben wird für verschiedene Situationen weiter optimiert. Beispielsweise ist es bekannt, dass das Zusammenführen effizienter ist, wenn die verbundenen Unteranordnungen ungefähr dieselbe Größe haben. Wenn die Größen in TimSort sehr unterschiedlich sind, erfolgt nach zusätzlichen Aktionen eine Anpassung (wir können sagen, dass einige der Elemente vom größeren Subarray zu einem kleineren "fließen", wonach der Zusammenschluss im Standardmodus fortgesetzt wird). Es gibt auch verschiedene heimtückische Situationen - zum Beispiel, wenn in einem Subarray alle Elemente kleiner sind als in einem anderen. In diesem Fall ist der Vergleich von Elementen aus beiden Unterfeldern inaktiv. Das modifizierte Fusionsverfahren wird eine solche unerwünschte Entwicklung von Ereignissen rechtzeitig „bemerken“ und, wenn es von einer pessimistischen Option unter Verwendung der binären Suche „überzeugt“ ist, zu einer optimaleren Verarbeitungsoption wechseln.
Im Durchschnitt arbeitet diese Sortierung etwas langsamer als QuickSort. Wenn das eingehende Array jedoch eine ausreichende Anzahl von geordneten Teilsequenzen von Elementen enthält, erhöht sich die Geschwindigkeit erheblich und TimSort übertrifft den Rest.
Block Merge Sort :: Block Merge Sort
Wiki-Sortierung :: Wiki-Sortierung
Heilige Gralsorte :: Grailsort
Fügt + Merge + Buckets ein
Blockieren Sie die Animation zum Sortieren von Zusammenführungen aus Wikipedia.Dies ist ein sehr frischer (2008) und gleichzeitig sehr vielversprechender Algorithmus. Tatsache ist, dass das relativ bedeutende Problem des Zusammenführens die Kosten für zusätzlichen Speicher sind. In der Regel ist dort, wo das Zusammenführen stattfindet, auch die Komplexität von O (
n ) Speicher vorhanden.
WikiSort ist jedoch so konzipiert, dass das Zusammenführen ohne die Verwendung von zusätzlichem Speicher erfolgt - unter Zusammenführungsarten ist dies in dieser Hinsicht eine sehr seltene Instanz. Außerdem ist der Algorithmus stabil. Nun, wenn die konventionelle Sortierung der Zusammenführung die beste algorithmische Geschwindigkeit O (
n log
n ) hat, dann ist dieser Indikator in der Wiki-Sortierung O (
n ). Bis vor kurzem glaubte man, dass das Zusammenführen von Sortierungen mit solchen Merkmalen prinzipiell unmöglich sei, aber chinesische Programmierer überraschten alle.
Der Algorithmus ist sehr kompliziert in ein paar Sätzen zu erklären. Aber eines Tages werde ich einen separaten Habrast über ihn schreiben.
Anfangs hieß der Algorithmus namenlos Block Merge Sort, doch mit der leichten Hand von Tim Peters, der die Sortierung im Detail studierte (um festzustellen, ob einige seiner Ideen auf TimSort übertragen werden sollten), blieb der Name WikiSort dabei.
Der frühzeitig
verstorbene Habruiser
Mrrl arbeitete mehrere Jahre selbständig an der Zusammenführungssortierung, die gleichzeitig mit allen eingehenden Daten schnell, sparsam im Speicher und stabil sein würde.
Seine kreativen Suchen waren erfolgreich und er nannte den entwickelten Algorithmus später eine Sortierung des Heiligen Grals (da er alle hohen Anforderungen an eine „perfekte Sortierung“ erfüllt). Die meisten Ideen dieses Algorithmus ähneln denen, die in WikiSort implementiert sind, obwohl diese Arten nicht identisch sind und unabhängig voneinander entwickelt werden.
Hash-Tabellensortierung :: Hash-Tabellensortierung
Verteilung + Einfügen + Zusammenführen
Das Array wird rekursiv in zwei Hälften geteilt, bis die Anzahl der Elemente in den resultierenden Subarrays einen bestimmten Schwellenwert erreicht. Bei der niedrigsten Rekursionsebene erfolgt eine ungefähre Verteilung (unter Verwendung einer Hash-Tabelle), und das Subarray wird nach Einfügungen sortiert. Dann erfolgt eine rekursive Rückkehr zu höheren Ebenen, die sortierten Hälften werden durch Zusammenführen kombiniert.
Ich
habe vor einem
Monat ein bisschen mehr über diesen Algorithmus gesprochen.
Schnelle Sortierung als primäre
Nach dem Zusammenführen und Einfügen wird der dritte Platz in der Hybrid-Hit-Parade von allen bevorzugten schnellen Sorten festgehalten.
Dies ist ein sehr effizienter Algorithmus, aber es gibt auch entartete Fälle dafür. Einige Erfinder versuchen, QuickSort für fehlerhafte eingehende Daten völlig unempfindlich zu machen, und schlagen vor, es durch überzeugende Ideen anderer Sorten zu ergänzen.
Introspektive Sortierung :: Introsort, Introspektive Sortierung, std :: sort
Schnelle + Haufen + Einfügungen
Die Heap-Sortierung ist etwas langsamer als die schnelle Sortierung, weist jedoch im Gegensatz zu QuickSort keine entarteten Fälle auf - die durchschnittliche, beste und schlechteste algorithmische Zeitkomplexität beträgt O (
n log
n ).
David Musser schlug daher vor, beim schnellen Sortieren auf Nummer sicher zu gehen - wenn zu viel verschachtelt ist, wird dies als Angriff auf das System angesehen, das ein "schlechtes" Array verloren hat. Das Umschalten auf das Sortieren nach einem Heap erfolgt, was nicht Megabyte ist, sondern auch nicht langsam, um
mit eingehenden Daten umzugehen.
C ++ hat einen Algorithmus namens std :: sort, der eine Implementierung der introspektiven Sortierung ist. Ein kleiner Zusatz - Wenn auf der nächsten Rekursionsstufe die
Anzahl der Elemente des Subarrays ≤ 16 ist, wird die Einfügesortierung auf das Subarray angewendet.
Multikey sort :: Multikey sort
Bitweises schnelles Sortieren :: Radix-schnelles Sortieren
Schnell + Ränge
Schnelle Sortierung, nur die Werte der Elemente des Arrays werden miteinander verglichen, aber ihre einzelnen Ziffern (zuerst ordnen wir die höheren Ziffern auf diese Weise an, wir bewegen uns von den jüngeren zu ihnen).
Oder so - dies ist eine bitweise Sortierung nach hoher Ordnung, die Sortierung innerhalb des nächsten Bits wird nach dem schnellen Sortieralgorithmus ausgeführt.
Scatter Sort :: Spreadsort
Schnelle + Zusammenführung + Eimer + Entladungen
Gestalt aus QuickSort, Merge Sort, Bucket Sort und Bitwise Sort.
In aller Kürze nicht erklären. Wir werden diesen Algorithmus in einem der folgenden Artikel detailliert analysieren.
Andere Hybriden
Baumzählende Sorte
Zählen + Baum
Der
vom Benutzer
AlexanderUsatov vorgeschlagene Algorithmus. Zählsortierung, die Anzahl der gezählten Schlüssel wird in einem ausgeglichenen Baum gespeichert.
J-Sortierung :: J-Sortierung
Haufen + Einsätze
Über diese Sortierung habe ich
schon vor 5 Jahren geschrieben . Alles ist ganz einfach: Zuerst müssen Sie im Array einmal einen nicht zunehmenden Heap erstellen und dann genau das Gegenteil tun - einmal einen nicht abnehmenden Heap erstellen. Infolge der ersten Operation befindet sich das Minimum an erster Stelle des Arrays, und kleine Elemente als Ganzes rücken erheblich an den Anfang. Im zweiten Fall befindet sich das Maximum an letzter Stelle und große Elemente wandern gegen Ende des Arrays. Im Allgemeinen erhalten wir ein fast sortiertes Array, mit dem wir was machen? Das ist richtig - sortiere die Beilagen aus.
Referenzen
Merge-Insertion ,
Block-Merge ,
Tim ,
Introspective ,
Spread ,
Multikey
Gral
Gral ,
Hash-Tabelle ,
Graf / Baum ,
JSerienartikel:
Von allen hier vorgestellten Sortierungen ist derzeit in der AlgoLab-Excel-Anwendung nur für Jsort-Animation implementiert.