Sortieralgorithmus - Sorting algorithm

In der Informatik ist ein Sortieralgorithmus ein Algorithmus , der Elemente einer Liste in eine Reihenfolge bringt . Die am häufigsten verwendeten Reihenfolgen sind die numerische Reihenfolge und die lexikographische Reihenfolge , und zwar entweder aufsteigend oder absteigend. Eine effiziente Sortierung ist wichtig, um die Effizienz anderer Algorithmen (wie Such- und Zusammenführungsalgorithmen ) zu optimieren, die erfordern, dass die Eingabedaten in sortierten Listen vorliegen. Das Sortieren ist auch oft nützlich, um Daten zu kanonisieren und eine für Menschen lesbare Ausgabe zu erstellen.

Formal muss die Ausgabe eines Sortieralgorithmus zwei Bedingungen erfüllen:

1. Die Ausgabe erfolgt in monotoner Reihenfolge (jedes Element ist nicht kleiner/größer als das vorherige Element, entsprechend der erforderlichen Reihenfolge).
2. Die Ausgabe ist eine Permutation (eine Neuordnung unter Beibehaltung aller ursprünglichen Elemente) der Eingabe.

Für eine optimale Effizienz sollten die Eingabedaten in einer Datenstruktur gespeichert werden, die einen wahlfreien Zugriff erlaubt, anstatt in einer, die nur einen sequentiellen Zugriff zulässt .

Geschichte und Konzepte

Seit den Anfängen der Informatik hat das Sortierproblem viel Forschung angezogen, vielleicht aufgrund der Komplexität seiner effizienten Lösung trotz seiner einfachen, vertrauten Aussage. Zu den Autoren früher Sortieralgorithmen um 1951 gehört Betty Holberton , die an ENIAC und UNIVAC mitgearbeitet hat . Bubble-Sort wurde bereits 1956 analysiert. Asymptotisch optimale Algorithmen sind seit Mitte des 20. Jahrhunderts bekannt – neue Algorithmen werden immer noch erfunden, wobei der weit verbreitete Timsort aus dem Jahr 2002 stammt und die Bibliothekssortierung 2006 erstmals veröffentlicht wurde.

Vergleichssortierungsalgorithmen haben eine grundlegende Anforderung von Ω( n log n ) Vergleichen (einige Eingabesequenzen erfordern ein Vielfaches von n log n Vergleichen, wobei n die Anzahl der Elemente in dem zu sortierenden Array ist). Algorithmen, die nicht auf Vergleichen basieren, wie das Zählen sort , können eine bessere Leistung aufweisen.

Sortieralgorithmen sind weit verbreitet in einführende Informatik Klassen, wo die Fülle von Algorithmen für das Problem auf eine Vielzahl von Kern - Algorithmus Konzepte, wie eine sanfte Einführung bietet O - Notation , teile und herrsche Algorithmen , Datenstrukturen wie Haufen und Binärbäumen , randomisierte Algorithmen , Best-, Worst- und Average-Case- Analyse, Zeit-Raum-Kompromisse sowie Ober- und Untergrenzen .

Das optimale Sortieren kleiner Arrays (wenigstens an Vergleichen und Swaps) oder schnell (dh unter Berücksichtigung maschinenspezifischer Details) ist noch ein offenes Forschungsproblem, wobei Lösungen nur für sehr kleine Arrays (<20 Elemente) bekannt sind. Eine ähnlich optimale (nach verschiedenen Definitionen) Sortierung auf einer parallelen Maschine ist ein offenes Forschungsthema.

Einstufung

Sortieralgorithmen können klassifiziert werden nach:

• Rechenkomplexität
  • Best-, Worst- und Average-Case- Verhalten in Bezug auf die Größe der Liste. Für typische Seriensortieralgorithmen, ist gutes Verhalten O ( n  log  n ), mit parallelen Art in O (log ²  n ) und schlechtes Verhalten ist O ( n ² ). Ideales Verhalten für eine serielle Sortierung ist O( n ), dies ist jedoch im durchschnittlichen Fall nicht möglich. Optimale parallele Sortierung ist O(log  n ).
  • Tauscht gegen "in-place"-Algorithmen.
• Speichernutzung (und Nutzung anderer Computerressourcen). Insbesondere sind einige Sortieralgorithmen „ in-place “. Streng genommen benötigt eine In-Place-Sortierung nur O(1)-Speicher über die zu sortierenden Elemente hinaus; manchmal wird O(log  n ) zusätzlicher Speicher als "in-place" betrachtet.
• Rekursion: Einige Algorithmen sind entweder rekursiv oder nicht-rekursiv, während andere beides sein können (zB Merge-Sort).
• Stabilität: Stabile Sortieralgorithmen behalten die relative Reihenfolge von Datensätzen mit gleichen Schlüsseln (dh Werten) bei.
• Unabhängig davon, ob es sich um eine Vergleichssortierung handelt oder nicht . Eine Vergleichssortierung untersucht die Daten nur, indem zwei Elemente mit einem Vergleichsoperator verglichen werden.
• Allgemeine Methode: Einfügen, Austauschen, Auswählen, Zusammenführen usw. Zu den Austauschsortierungen gehören Bubble-Sort und Quicksort. Auswahlsortierungen umfassen Zyklussortierung und Heapsortierung.
• Ob der Algorithmus seriell oder parallel ist. Der Rest dieser Diskussion konzentriert sich fast ausschließlich auf serielle Algorithmen und geht von einem seriellen Betrieb aus.
• Anpassungsfähigkeit: Ob sich die Vorsortierung der Eingabe auf die Laufzeit auswirkt oder nicht. Algorithmen, die dies berücksichtigen, sind bekanntermaßen adaptiv .
• Online: Ein Algorithmus wie Insertion Sort, der online ist, kann einen konstanten Eingabestrom sortieren.

Stabilität

Ein Beispiel für eine stabile Sortierung auf Spielkarten. Wenn die Karten mit einer stabilen Sortierung nach Rang sortiert werden, müssen die beiden 5er in der sortierten Ausgabe in derselben Reihenfolge bleiben, in der sie ursprünglich waren. Wenn sie mit einer nicht stabilen Sortierung sortiert werden, können die 5er im Gegenteil enden Reihenfolge in der sortierten Ausgabe.

Stabile Sortieralgorithmen sortieren gleiche Elemente in der gleichen Reihenfolge, in der sie in der Eingabe erscheinen. Im Kartensortierbeispiel rechts werden die Karten beispielsweise nach ihrem Rang sortiert und ihre Farbe wird ignoriert. Dies ermöglicht die Möglichkeit, mehrere verschiedene, korrekt sortierte Versionen der Originalliste zu erstellen. Stabile Sortieralgorithmen wählen nach folgender Regel einen dieser Sortieralgorithmen aus: Wenn zwei Elemente gleich sind (wie die beiden 5er-Karten), dann wird ihre relative Reihenfolge beibehalten, dh wenn ein Element in der Eingabe vor dem anderen steht, wird es kommen vor dem anderen in der Ausgabe.

Stabilität ist wichtig, um die Ordnung über mehrere Sortierungen desselben Datensatzes hinweg beizubehalten . Angenommen, Schülerdatensätze, die aus dem Namens- und Klassenabschnitt bestehen, werden dynamisch zuerst nach Name und dann nach Klassenabschnitt sortiert. Wenn in beiden Fällen ein stabiler Sortieralgorithmus verwendet wird, ändert die Sortierung nach Klassenabschnitt die Namensreihenfolge nicht; Bei einer instabilen Sortierung kann es sein, dass die Sortierung nach Abschnitten die Namensreihenfolge vertauscht, was zu einer nicht alphabetischen Liste der Schüler führt.

Formaler ausgedrückt können die sortierten Daten als Datensatz oder Tupel von Werten dargestellt werden, und der Teil der Daten, der zum Sortieren verwendet wird, wird als Schlüssel bezeichnet . Im Kartenbeispiel werden Karten als Rekord (Rang, Farbe) dargestellt, und der Schlüssel ist der Rang. Ein Sortieralgorithmus ist stabil, wenn immer dann, wenn zwei Datensätze R und S mit demselben Schlüssel vorhanden sind und R vor S in der ursprünglichen Liste erscheint, R immer vor S in der sortierten Liste erscheint.

Wenn gleiche Elemente nicht unterscheidbar sind, z. B. bei ganzen Zahlen, oder allgemeiner bei Daten, bei denen das gesamte Element der Schlüssel ist, ist die Stabilität kein Problem. Stabilität ist auch kein Problem, wenn alle Tasten unterschiedlich sind.

Instabile Sortieralgorithmen können speziell implementiert werden, um stabil zu sein. Eine Möglichkeit besteht darin, den Schlüsselvergleich künstlich zu erweitern, so dass Vergleiche zwischen zwei Objekten mit ansonsten gleichen Schlüsseln anhand der Reihenfolge der Einträge in der ursprünglichen Eingabeliste als Tie-Break entschieden werden. Das Merken dieser Reihenfolge kann jedoch zusätzliche Zeit und Platz erfordern.

Eine Anwendung für stabile Sortieralgorithmen ist das Sortieren einer Liste unter Verwendung eines Primär- und Sekundärschlüssels. Angenommen, wir möchten eine Kartenhand so sortieren, dass die Farben in der Reihenfolge Kreuz (♣), Karo ( ♦ ), Herz ( ♥ ), Pik (♠) liegen und innerhalb jeder Farbe die Karten nach . sortiert sind Rang. Dazu können Sie die Karten zuerst nach Rang sortieren (mit einer beliebigen Sortierung) und dann eine stabile Sortierung nach Farbe durchführen:

Innerhalb jeder Farbe behält die stabile Sortierung die bereits vorgenommene Rangordnung bei. Diese Idee kann auf beliebig viele Schlüssel erweitert werden und wird von radix sort genutzt . Der gleiche Effekt kann mit einer instabilen Sortierung erzielt werden, indem ein lexikographischer Schlüsselvergleich verwendet wird, der zB zuerst nach Farbe vergleicht und dann nach Rang vergleicht, wenn die Farben gleich sind.

Vergleich von Algorithmen

In diesen Tabellen ist n die Anzahl der zu sortierenden Datensätze. Die Spalten "Best", "Average" und "Worst" geben jeweils die Zeitkomplexität an, unter der Annahme, dass die Länge jedes Schlüssels konstant ist und somit alle Vergleiche, Swaps und andere Operationen in konstanter Zeit ablaufen können. "Speicher" bezeichnet die Menge an zusätzlichem Speicherplatz, der zusätzlich zu dem von der Liste selbst verwendeten Speicherplatz unter der gleichen Annahme benötigt wird. Die aufgeführten Laufzeiten und Speicheranforderungen liegen in der großen O-Notation , daher spielt die Basis der Logarithmen keine Rolle. Die Notation log ² n bedeutet (log n ) ² .

Vergleichssortierungen

Unten ist eine Tabelle mit Vergleichsarten . Eine Vergleichssortierung kann im Durchschnitt keine bessere Leistung als O ( n log n ) erbringen.

Vergleichssortierungen

Name	Am besten	Durchschnitt	Am schlimmsten	Speicher	Stabil	Methode	Weitere Hinweise
Schnelle Sorte	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle \log n}$	Nein	Partitionierung	Quicksort wird normalerweise direkt mit O (log n ) Stapelplatz durchgeführt.
Zusammenführen, sortieren	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	Jawohl	Zusammenführen	Hochgradig parallelisierbar (bis zu O (log n ) unter Verwendung des Drei-Ungarischen-Algorithmus).
Direkte Zusammenführungssortierung	—	—	${\displaystyle n\log^{2}n}$	1	Jawohl	Zusammenführen	Kann als stabile Sortierung basierend auf einer stabilen In-Place-Zusammenführung implementiert werden.
Einführung	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle \log n}$	Nein	Partitionierung & Auswahl	Wird in mehreren STL- Implementierungen verwendet.
Heapsort	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	Nein	Auswahl
Sortieren durch Einfügen	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Jawohl	Einfügen	O ( n + d ) , im schlimmsten Fall über Folgen mit d Inversionen .
Blocksortierung	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	Jawohl	Einfügen und Zusammenführen	Kombinieren Sie einen blockbasierten In-Place-Merge-Algorithmus mit einer Bottom-Up-Merge-Sortierung . ${\displaystyle O(n)}$
Timsort	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	Jawohl	Einfügen und Zusammenführen	Führt n-1 Vergleiche durch, wenn die Daten bereits sortiert oder umgekehrt sortiert sind.
Auswahl sortieren	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Nein	Auswahl	Stabil mit zusätzlichem Platz, wenn verknüpfte Listen verwendet werden oder als Variante von Insertion Sort erstellt werden, anstatt die beiden Elemente zu vertauschen. ${\displaystyle O(n)}$
Cubesort	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	Jawohl	Einfügen	Führt n-1 Vergleiche durch, wenn die Daten bereits sortiert oder umgekehrt sortiert sind.
Shellsort	${\displaystyle n\log n}$	${\displaystyle n^{4/3}}$	${\displaystyle n^{3/2}}$	1	Nein	Einfügen	Kleine Codegröße.
Blasensortierung	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Jawohl	Austausch	Winzige Codegröße.
Exchange sortieren	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Jawohl	Austausch	Winzige Codegröße.
Baumsortierung	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$(ausgewogen)	n	Jawohl	Einfügen	Bei Verwendung eines selbstausgleichenden binären Suchbaums .
Zyklus sortieren	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Nein	Auswahl	In-Place mit theoretisch optimaler Anzahl von Schreibvorgängen.
Bibliothek sortieren	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	n	Nein	Einfügen	Ähnlich einer mit Lücken versehenen Einfügungssortierung. Es erfordert eine zufällige Permutation der Eingabe, um Zeitgrenzen mit hoher Wahrscheinlichkeit zu gewährleisten, was sie nicht stabil macht.
Geduld sortieren	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	Nein	Einfügen & Auswahl	Findet alle längsten ansteigenden Teilfolgen in O ( n log n ) .
Smoothsort	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	Nein	Auswahl	Eine adaptive Variante von Heapsort, die auf der Leonardo-Sequenz basiert und nicht auf einem traditionellen binären Heap .
Strangsortierung	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	n	Jawohl	Auswahl
Turniersortierung	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	Nein	Auswahl	Variation von Heapsort.
Cocktailshaker sortieren	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Jawohl	Austausch	Eine Variante von Bubblesort, die mit kleinen Werten am Ende der Liste gut zurechtkommt
Kammsortierung	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Nein	Austausch	Im Durchschnitt schneller als Blasensortierung.
Gnome sortieren	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Jawohl	Austausch	Winzige Codegröße.
Ungerade–gerade Sortierung	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Jawohl	Austausch	Lässt sich problemlos auf parallelen Prozessoren ausführen.

Nicht-Vergleichssorten

In der folgenden Tabelle werden ganzzahlige Sortieralgorithmen und andere Sortieralgorithmen beschrieben, die keine Vergleichssortierungen sind . Als solche sind sie nicht darauf beschränkt Ω ( n log n ) . Die folgenden Komplexitäten gehen von n zu sortierenden Elementen mit Schlüsseln der Größe k , Zifferngröße d und r des zu sortierenden Zahlenbereichs aus. Viele von ihnen basieren auf der Annahme, dass die Schlüsselgröße groß genug ist, dass alle Einträge eindeutige Schlüsselwerte haben, und daher n 2 ^k , wobei ≪ "viel kleiner als" bedeutet. In der Einheit kostengünstigen random-access Maschinenmodell, Algorithmen mit Laufzeit , wie Radix Sort, nehmen noch Zeit proportional zu Θ ( n log n ) , weil n beschränkt ist nicht mehr als sein , und eine größere Anzahl von Elementen zu sortieren würde ein größeres k erfordern, um sie im Speicher zu speichern. ${\displaystyle \scriptstyle n\cdot {\frac {k}{d}}}$${\displaystyle 2^{\frac {k}{d}}}$

Nicht-Vergleichssorten

Name	Am besten	Durchschnitt	Am schlimmsten	Speicher	Stabil	n ≪ 2 k	Anmerkungen
Schubladensortierung	—	${\displaystyle n+2^{k}}$	${\displaystyle n+2^{k}}$	${\displaystyle 2^{k}}$	Jawohl	Jawohl	Nicht-Ganzzahlen können nicht sortiert werden.
Bucket-Sort (einheitliche Schlüssel)	—	${\displaystyle n+k}$	${\displaystyle n^{2}\cdot k}$	${\displaystyle n\cdot k}$	Jawohl	Nein	Nimmt eine gleichmäßige Verteilung der Elemente aus der Domäne im Array an. Nicht-Ganzzahlen können auch nicht sortiert werden
Bucket-Sort (Integer-Schlüssel)	—	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	Jawohl	Jawohl	Wenn r ist , dann ist die durchschnittliche Zeitkomplexität . ${\displaystyle O(n)}$${\displaystyle O(n)}$
Zählen sortieren	—	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	Jawohl	Jawohl	Wenn r ist , dann ist die durchschnittliche Zeitkomplexität . ${\displaystyle O(n)}$${\displaystyle O(n)}$
LSD Radix Sortierung	${\displaystyle n}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	Jawohl	Nein	${\displaystyle {\frac {k}{d}}}$Rekursionsebenen, 2 d für count-Array. Im Gegensatz zu den meisten Verteilungssortierungen können hier Gleitkommazahlen , negative Zahlen und mehr sortiert werden.
MSD Radix Sortierung	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	Jawohl	Nein	Die stabile Version verwendet ein externes Array der Größe n , um alle Bins aufzunehmen. Wie die LSD-Variante kann sie nicht-ganzzahlige sortieren.
MSD Radix Sort (vor Ort)	—	${\displaystyle n\cdot {\frac {k}{1}}}$	${\displaystyle n\cdot {\frac {k}{1}}}$	${\displaystyle 2^{1}}$	Nein	Nein	d=1 für In-Place, Rekursionsebenen, kein Count-Array. ${\displaystyle k/1}$
Spreadsort	n	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot \left({{\frac {k}{s}}+d}\right)}$	${\displaystyle {\frac {k}{d}}\cdot 2^{d}}$	Nein	Nein	Asymptotische basieren auf der Annahme, dass n ≪ 2 k ist , aber der Algorithmus erfordert dies nicht.
Burstsort	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	Nein	Nein	Hat einen besseren konstanten Faktor als Radixsort zum Sortieren von Strings. Allerdings hängt sie etwas von den Besonderheiten der häufig anzutreffenden Zeichenfolgen ab.
Flashsort	n	${\displaystyle n+r}$	${\displaystyle n^{2}}$	n	Nein	Nein	Erfordert eine gleichmäßige Verteilung von Elementen aus der Domäne im Array, um in linearer Zeit ausgeführt zu werden. Wenn die Verteilung extrem schief ist, kann sie quadratisch werden, wenn die zugrunde liegende Sortierung quadratisch ist (normalerweise eine Einfügungssortierung). In-Place-Version ist nicht stabil.
Postbote sortieren	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	—	Nein	Eine Variante von Bucket Sort, die sehr ähnlich wie MSD Radix Sort funktioniert. Speziell für Post-Service-Bedürfnisse.

Samplesort kann verwendet werden, um jede der Nicht-Vergleichssortierungen zu parallelisieren, indem Daten effizient auf mehrere Buckets verteilt und dann die Sortierung an mehrere Prozessoren weitergegeben wird, ohne dass eine Zusammenführung erforderlich ist, da die Buckets bereits untereinander sortiert sind.

Andere

Einige Algorithmen sind langsam im Vergleich zu den oben diskutierten, wie beispielsweise der Bogosort mit unbegrenzter Laufzeit und der Stooge-Sort, der O ( n ^2,7 ) Laufzeit hat. Diese Arten werden normalerweise zu Bildungszwecken beschrieben, um zu zeigen, wie die Laufzeit von Algorithmen geschätzt wird. In der folgenden Tabelle werden einige Sortieralgorithmen beschrieben, die aufgrund extrem schlechter Leistung oder spezieller Hardwareanforderungen für die reale Verwendung in herkömmlichen Softwarekontexten nicht praktikabel sind.

Name	Am besten	Durchschnitt	Am schlimmsten	Speicher	Stabil	Vergleich	Weitere Hinweise
Perlensortierung	n	S	S	${\displaystyle n^{2}}$	N / A	Nein	Funktioniert nur mit positiven ganzen Zahlen. Erfordert spezielle Hardware, um in garantierter Zeit ausgeführt zu werden. Es gibt eine Möglichkeit für eine Softwareimplementierung, aber die Laufzeit ist , wobei S die Summe aller zu sortierenden ganzen Zahlen ist, bei kleinen ganzen Zahlen kann sie als linear angesehen werden. ${\displaystyle O(n)}$${\displaystyle O(S)}$
Einfache Pfannkuchensortierung	—	n	n	${\displaystyle \log n}$	Nein	Jawohl	Count ist die Anzahl der Flips.
Spaghetti (Umfrage) sortieren	n	n	n	${\displaystyle n^{2}}$	Jawohl	Umfrage	Dies ist ein analoger Algorithmus mit linearer Zeit zum Sortieren einer Folge von Elementen, der O ( n ) Stapelplatz erfordert , und die Sortierung ist stabil. Dies erfordert n parallele Prozessoren. Siehe Spaghettisort#Analyse .
Sortiernetzwerk	Variiert	Variiert	Variiert	Variiert	Variiert (stabile Sortiernetzwerke erfordern mehr Vergleiche)	Jawohl	Die Reihenfolge der Vergleiche wird im Voraus basierend auf einer festen Netzwerkgröße festgelegt.
Bitonic Sortierer	${\displaystyle \log^{2}n}$ parallel	${\displaystyle \log^{2}n}$ parallel	${\displaystyle n\log^{2}n}$ nicht parallel	1	Nein	Jawohl	Eine effektive Variante von Sortiernetzwerken.
Bogosort	n	${\displaystyle (n\mal n!)}$	unbegrenzt (sicher), (erwartet)${\displaystyle (n\mal n!)}$	1	Nein	Jawohl	Zufälliges Mischen. Wird nur zu Beispielzwecken verwendet, da selbst die erwartete Laufzeit im besten Fall schrecklich ist.
Stooge sortieren	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	n	Nein	Jawohl	Langsamer als die meisten der Sortieralgorithmen (auch naiv sind) mit einer Zeitkomplexität von O ( n 3 log / log 1,5 ) = O ( n 2,7095 ... ) stabil gemacht werden kann, und ist auch ein Sortiernetz .
Slowsort	${\displaystyle n^{\log n}}$	${\displaystyle n^{\log n}}$	${\displaystyle n^{\log n}}$	n	Nein	Jawohl	Ein Multiplizier- und Kapitulationsalgorithmus, der dem Divide-and-Conquer-Algorithmus entspricht .

Theoretische Informatiker haben andere Sortieralgorithmen detailliert beschrieben, die eine bessere Zeitkomplexität als O ( n log n ) bieten , unter der Annahme zusätzlicher Einschränkungen, einschließlich:

• Thorups Algorithmus , ein randomisierter Algorithmus zum Sortieren von Schlüsseln aus einem Bereich endlicher Größe, der O ( n log log n ) Zeit und O ( n ) Raum benötigt.
• Ein randomisierter ganzzahliger Sortieralgorithmus , der die erwartete Zeit und den O ( n )-Raum benötigt.${\displaystyle O\left(n{\sqrt {\log\log n}}\right)}$

Beliebte Sortieralgorithmen

Während es eine große Anzahl von Sortieralgorithmen gibt, überwiegen in praktischen Implementierungen einige wenige Algorithmen. Insertion Sort wird häufig für kleine Datensätze verwendet, während für große Datensätze eine asymptotisch effiziente Sortierung verwendet wird, hauptsächlich Heapsort, Merge Sort oder Quicksort. Effiziente Implementierungen verwenden im Allgemeinen einen Hybridalgorithmus , der einen asymptotisch effizienten Algorithmus für die Gesamtsortierung mit einer Einfügungssortierung für kleine Listen am Ende einer Rekursion kombiniert. Hochgradig abgestimmte Implementierungen verwenden komplexere Varianten wie Timsort (Merge-Sort, Insertion-Sort und zusätzliche Logik), das in Android, Java und Python verwendet wird, und Introsort (Quicksort und Heapsort), das (in Variantenformen) in einigen C++-Sorten verwendet wird Implementierungen und in .NET.

Für eingeschränktere Daten, wie Zahlen in einem festen Intervall, werden häufig Verteilungssortierungen wie Zählsortierung oder Radixsortierung verwendet. Bubble-Sort und -Varianten werden in der Praxis selten verwendet, finden sich jedoch häufig in der Lehre und in theoretischen Diskussionen.

Beim physischen Sortieren von Objekten (wie Alphabetisierung von Aufsätzen, Tests oder Büchern) verwenden Menschen intuitiv im Allgemeinen Einfügesortierungen für kleine Sätze. Bei größeren Sets wird häufig zuerst ein Eimer verwendet, z. Oftmals ist der Platz relativ günstig, beispielsweise durch das Verteilen von Objekten auf dem Boden oder über eine große Fläche, aber die Operationen sind teuer, insbesondere das Bewegen eines Objekts über eine große Entfernung – der Referenzort ist wichtig. Zusammenführungssortierungen sind auch für physische Objekte praktisch, insbesondere da zwei Hände verwendet werden können, eine für jede zusammenzuführende Liste, während andere Algorithmen wie Heapsort oder Quicksort für den menschlichen Gebrauch schlecht geeignet sind. Auch andere Algorithmen, wie zB library sort , eine Variante der Insertionssortierung, die Leerzeichen lässt, sind für den physischen Gebrauch praktisch.

Einfache Sortierung

Zwei der einfachsten Sortierungen sind die Einfügungssortierung und die Auswahlsortierung, die beide aufgrund des geringen Overheads bei kleinen Daten effizient, bei großen Daten jedoch nicht effizient sind. Die Einfügungssortierung ist in der Praxis aufgrund weniger Vergleiche und einer guten Leistung bei fast sortierten Daten im Allgemeinen schneller als die Auswahlsortierung und wird daher in der Praxis bevorzugt, aber die Auswahlsortierung verwendet weniger Schreibvorgänge und wird daher verwendet, wenn die Schreibleistung ein limitierender Faktor ist.

Sortieren durch Einfügen

Insertion Sort ist ein einfacher Sortieralgorithmus, der für kleine Listen und meist sortierte Listen relativ effizient ist und oft als Teil komplexerer Algorithmen verwendet wird. Es funktioniert, indem Elemente nacheinander aus der Liste genommen und an der richtigen Position in eine neue sortierte Liste eingefügt werden, ähnlich wie wir Geld in unsere Brieftasche stecken. In Arrays können sich die neue Liste und die verbleibenden Elemente den Platz des Arrays teilen, aber das Einfügen ist teuer, da alle folgenden Elemente um eins verschoben werden müssen. Shellsort (siehe unten) ist eine Variante der Insertionssortierung, die für größere Listen effizienter ist.

Auswahl sortieren

Die Auswahlsortierung ist eine direkte Vergleichssortierung . Sie hat eine Komplexität von O ( n ² ), was sie bei großen Listen ineffizient macht und im Allgemeinen schlechter abschneidet als die ähnliche Einfügungssortierung . Die Auswahlsortierung ist für ihre Einfachheit bekannt und hat in bestimmten Situationen auch Leistungsvorteile gegenüber komplizierteren Algorithmen.

Der Algorithmus findet den Minimalwert, vertauscht ihn mit dem Wert an der ersten Position und wiederholt diese Schritte für den Rest der Liste. Es führt nicht mehr als n Auslagerungen durch und ist daher nützlich, wenn Auslagerungen sehr teuer sind.

Effiziente Sortierung

Praktische allgemeine Sortieralgorithmen basieren fast immer auf einem Algorithmus mit durchschnittlicher Zeitkomplexität (und allgemein Worst-Case-Komplexität) O( n log n ), von denen die gebräuchlichsten Heapsort, Mergesort und Quicksort sind. Jedes hat Vorteile und Nachteile, wobei der wichtigste ist , daß eine einfache Implementierung von Merge Sort verwendet O ( n ) , zusätzlichen Raum und einfache Implementierung hat quicksort O ( n ² ) worst-case Komplexität. Diese Probleme können auf Kosten eines komplexeren Algorithmus gelöst oder verbessert werden.

Während diese Algorithmen bei Zufallsdaten asymptotisch effizient sind, werden für die praktische Effizienz bei realen Daten verschiedene Modifikationen verwendet. Erstens wird der Overhead dieser Algorithmen bei kleineren Daten erheblich, so dass oft ein Hybridalgorithmus verwendet wird, der üblicherweise auf Einfügungssortierung umschaltet, sobald die Daten klein genug sind. Zweitens funktionieren die Algorithmen bei bereits sortierten Daten oder fast sortierten Daten oft schlecht – diese sind bei realen Daten üblich und können durch geeignete Algorithmen in O( n ) -Zeit sortiert werden. Schließlich können sie auch instabil sein , und Stabilität ist oft eine wünschenswerte Eigenschaft. Daher werden oft ausgefeiltere Algorithmen verwendet, wie Timsort (basierend auf Mergesort) oder Introsort (basierend auf Quicksort, Rückfall auf Heapsort).

Zusammenführen, sortieren

Merge Sort nutzt die einfache Möglichkeit, bereits sortierte Listen zu einer neuen sortierten Liste zusammenzuführen. Es beginnt damit, alle zwei Elemente zu vergleichen (dh 1 mit 2, dann 3 mit 4...) und sie zu vertauschen, wenn das erste nach dem zweiten kommen sollte. Es führt dann jede der resultierenden Zweier-Listen in Vierer-Listen zusammen, führt dann diese Vierer-Listen zusammen und so weiter; bis zuletzt zwei Listen zur endgültigen sortierten Liste zusammengeführt werden. Von den hier beschriebenen Algorithmen ist dies der erste, der sich gut auf sehr große Listen skalieren lässt, da seine Laufzeit im ungünstigsten Fall O( n log n ) beträgt . Es lässt sich auch leicht auf Listen anwenden, nicht nur auf Arrays, da es nur sequentiellen Zugriff erfordert, keinen wahlfreien Zugriff. Es hat jedoch eine zusätzliche O( n )-Raumkomplexität und beinhaltet eine große Anzahl von Kopien in einfachen Implementierungen.

Merge-Sort hat für praktische Implementierungen in letzter Zeit aufgrund seiner Verwendung im ausgeklügelten Algorithmus Timsort , der für die Standardsortierroutine in den Programmiersprachen Python und Java (ab JDK7 ) verwendet wird, einen relativ hohen Popularitätsschub erfahren . Merge-Sort selbst ist unter anderem die Standardroutine in Perl und wird in Java mindestens seit 2000 in JDK1.3 verwendet .

Heapsort

Heapsort ist eine viel effizientere Version der Auswahlsortierung . Es funktioniert auch, indem es das größte (oder kleinste) Element der Liste bestimmt, dieses am Ende (oder Anfang) der Liste platziert und dann mit dem Rest der Liste fortfährt, führt diese Aufgabe jedoch effizient durch die Verwendung einer Datenstruktur namens a . aus heap , eine spezielle Art von Binärbaum . Sobald die Datenliste in einen Heap umgewandelt wurde, ist der Wurzelknoten garantiert das größte (oder kleinste) Element. Wenn es entfernt und am Ende der Liste platziert wird, wird der Heap neu angeordnet, sodass das größte verbleibende Element an den Stamm verschoben wird. Unter Verwendung des Heaps benötigt das Finden des nächstgrößeren Elements O(log n ) Zeit anstelle von O( n ) für einen linearen Scan wie bei der einfachen Auswahlsortierung. Dadurch kann Heapsort in O( n log n ) Zeit ausgeführt werden, und dies ist auch die Komplexität des ungünstigsten Falls.

Schnelle Sorte

Quicksort ist ein Divide-and-Conquer-Algorithmus, der auf einer Partitionierungsoperation beruht : Um ein Array zu partitionieren, wird ein Element namens Pivot ausgewählt. Alle Elemente, die kleiner als der Pivot sind, werden davor und alle größeren Elemente danach verschoben. Dies kann effizient in linearer Zeit und vor Ort erfolgen . Die kleineren und größeren Teillisten werden dann rekursiv sortiert. Dies ergibt eine durchschnittliche Zeitkomplexität von O( n log n ) mit geringem Overhead, und daher ist dies ein beliebter Algorithmus. Effiziente Implementierungen von Quicksort (mit direkter Partitionierung) sind typischerweise instabile Sortierungen und etwas komplex, gehören jedoch zu den schnellsten Sortieralgorithmen in der Praxis. Zusammen mit seinem bescheidenen O(log n )-Speicherverbrauch ist Quicksort einer der beliebtesten Sortieralgorithmen und in vielen Standard-Programmierbibliotheken verfügbar.

Der wichtige Vorbehalt bei Quicksort ist, dass seine Leistung im schlimmsten Fall O( n ² ) ist; Während dies selten vorkommt, tritt dies in naiven Implementierungen (die Wahl des ersten oder letzten Elements als Pivot-Element) bei sortierten Daten auf, was ein häufiger Fall ist. Das komplexeste Problem bei Quicksort ist daher die Auswahl eines guten Pivot-Elements, da eine dauerhaft schlechte Auswahl von Pivots zu einer drastisch langsameren O( n ² )-Leistung führen kann, aber eine gute Wahl der Pivots ergibt eine O( n log n )-Leistung, die asymptotisch optimal ist . Wenn beispielsweise bei jedem Schritt der Median als Pivot gewählt wird, dann arbeitet der Algorithmus in O( n  log  n ). Das Auffinden des Medians, beispielsweise durch den Median-von-Median- Auswahlalgorithmus, ist jedoch eine O( n )-Operation bei unsortierten Listen und erfordert daher einen erheblichen Aufwand beim Sortieren. In der Praxis führt die Wahl eines zufälligen Pivots mit ziemlicher Sicherheit zu einer Leistung von O( n  log  n ).

Shellsort

Ein Shellsort unterscheidet sich von Bubblesort dadurch, dass es Elemente an zahlreiche Tauschpositionen verschiebt .

Shellsort wurde 1959 von Donald Shell erfunden . Es verbessert die Sortierung beim Einfügen, indem es Elemente aus der Reihenfolge an mehr als einer Position gleichzeitig verschiebt. Das Konzept hinter Shellsort besteht darin, dass die Einfügungssortierung in der Zeit ausgeführt wird, wobei k der größte Abstand zwischen zwei fehlplatzierten Elementen ist. Dies bedeutet, dass sie im Allgemeinen in O ( n ² ) arbeiten, aber für Daten, die meistens sortiert sind und nur wenige Elemente fehl am Platz sind, sind sie schneller. Wenn Sie also zuerst weit entfernte Elemente sortieren und die Lücke zwischen den zu sortierenden Elementen schrittweise verkleinern, wird die endgültige Sortierung viel schneller berechnet. Eine Implementierung kann als Anordnen der Datensequenz in einem zweidimensionalen Array und anschließendes Sortieren der Spalten des Arrays mittels Einfügungssortierung beschrieben werden. ${\displaystyle O(kn)}$

Die Worst-Case-Zeitkomplexität von Shellsort ist ein offenes Problem und hängt von der verwendeten Lückenfolge ab, wobei die bekannten Komplexitäten von O ( n ² ) bis O ( n ^4/3 ) und Θ ( n log ² n ) reichen . Dies, kombiniert mit der Tatsache, dass Shellsort an Ort und Stelle ist , nur eine relativ geringe Menge an Code benötigt und keine Verwendung des Aufrufstapels erfordert , macht es in Situationen nützlich, in denen der Speicher knapp ist, wie z. B. in eingebetteten Systemen und Betriebssystemkerne .

Blasensortierung und Varianten

Bubblesort und Varianten wie Shellsort und Cocktailsort sind einfache, höchst ineffiziente Sortieralgorithmen. Sie werden wegen der einfachen Analyse häufig in einführenden Texten verwendet, in der Praxis jedoch selten verwendet.

Blasensortierung

Ein Bubble-Sort, ein Sortieralgorithmus, der kontinuierlich eine Liste durchläuft und Elemente vertauscht , bis sie in der richtigen Reihenfolge erscheinen.

Bubble-Sort ist ein einfacher Sortieralgorithmus. Der Algorithmus beginnt am Anfang des Datensatzes. Es vergleicht die ersten beiden Elemente, und wenn das erste größer als das zweite ist, vertauscht es sie. Dies wird für jedes Paar benachbarter Elemente bis zum Ende des Datensatzes fortgesetzt. Es beginnt dann wieder mit den ersten beiden Elementen und wiederholt sich, bis beim letzten Durchgang keine Vertauschungen aufgetreten sind. Die durchschnittliche Zeit und die Worst-Case-Leistung dieses Algorithmus ist O( n ² ), daher wird er selten verwendet, um große, ungeordnete Datensätze zu sortieren. Bubble-Sort kann verwendet werden, um eine kleine Anzahl von Elementen zu sortieren (wobei seine asymptotische Ineffizienz kein hoher Nachteil ist). Bubble-Sort kann auch effizient für eine Liste beliebiger Länge verwendet werden, die nahezu sortiert ist (dh die Elemente sind nicht wesentlich fehl am Platz). Wenn beispielsweise eine beliebige Anzahl von Elementen nur um eine Position verschoben ist (z. B. 0123546789 und 1032547698), wird der Austausch von Bubble-Sort sie beim ersten Durchgang in die richtige Reihenfolge bringen, beim zweiten Durchgang werden alle Elemente der Reihe nach gefunden, sodass die Sortierung dauert nur 2 n Zeit.

Kammsortierung

Comb Sort ist ein relativ einfacher Sortieralgorithmus, der auf Bubble Sort basiert und ursprünglich 1980 von Włodzimierz Dobosiewicz entwickelt wurde. Später wurde er von Stephen Lacey und Richard Box mit einem im April 1991 veröffentlichten Artikel im Byte Magazine wiederentdeckt und populär gemacht . Die Grundidee besteht darin, Schildkröten zu eliminieren , oder kleine Werte am Ende der Liste, da diese bei einer Blasensortierung die Sortierung enorm verlangsamen. ( Kaninchen , große Werte am Anfang der Liste, stellen kein Problem bei der Blasensortierung dar) Dies wird erreicht, indem zunächst Elemente getauscht werden, die einen bestimmten Abstand voneinander im Array haben, anstatt nur Elemente auszutauschen, wenn sie benachbart sind aneinander und verkleinern dann den gewählten Abstand, bis er wie eine normale Blasensortierung funktioniert. Wenn man sich Shellsort als eine verallgemeinerte Version von Insertion-Sort vorstellen kann, die Elemente mit einem bestimmten Abstand voneinander vertauscht, kann man sich Comb-Sort als dieselbe Verallgemeinerung vorstellen, die auf Bubble-Sort angewendet wird.

Exchange sortieren

Exchange-Sort wird manchmal mit Bubble-Sort verwechselt, obwohl die Algorithmen tatsächlich unterschiedlich sind. Exchange-Sort funktioniert, indem das erste Element mit allen darüber liegenden Elementen verglichen und bei Bedarf ausgetauscht wird, wodurch sichergestellt wird, dass das erste Element für die endgültige Sortierreihenfolge korrekt ist; dann fährt es fort, dasselbe für das zweite Element zu tun, und so weiter. Es fehlt der Vorteil von Bubble-Sort, in einem Durchlauf zu erkennen, ob die Liste bereits sortiert ist, aber es kann schneller sein als Bubble-Sort um einen konstanten Faktor (ein Durchlauf weniger über die zu sortierenden Daten; halb so viele Gesamtvergleiche) in Worst-Case-Situationen. Wie jede einfache O( n ² )-Sortierung kann sie über sehr kleine Datensätze relativ schnell sein, obwohl die Einfügungssortierung im Allgemeinen schneller ist.

Verteilungssortierung

Verteilungssortierung bezieht sich auf jeden Sortieralgorithmus, bei dem Daten von ihrer Eingabe auf mehrere Zwischenstrukturen verteilt werden, die dann gesammelt und auf der Ausgabe platziert werden. Sowohl Bucket-Sort als auch Flashsort sind verteilungsbasierte Sortieralgorithmen. Verteilungssortierungsalgorithmen können auf einem einzelnen Prozessor verwendet werden, oder sie können ein verteilter Algorithmus sein , bei dem einzelne Teilmengen separat auf verschiedenen Prozessoren sortiert und dann kombiniert werden. Dies ermöglicht die externe Sortierung von Daten, die zu groß sind, um in den Speicher eines einzelnen Computers zu passen.

Zählen sortieren

Die Zählsortierung ist anwendbar, wenn bekannt ist, dass jede Eingabe zu einer bestimmten Menge S von Möglichkeiten gehört. Der Algorithmus läuft in O(| S | + n ) Zeit und O(| S |) Speicher, wobei n die Länge der Eingabe ist. Es funktioniert, indem es ein ganzzahliges Array der Größe | . erstellt S | und Verwenden des i- ten Bins, um das Auftreten des i- ten Mitglieds von S in der Eingabe zu zählen. Jeder Eingang wird dann gezählt, indem der Wert seines entsprechenden Bins erhöht wird. Danach wird das Zählarray durchgeschleift, um alle Eingänge der Reihe nach anzuordnen. Dieser Sortieralgorithmus kann oft nicht verwendet werden, da S relativ klein sein muss, damit der Algorithmus effizient ist, aber er ist extrem schnell und zeigt ein starkes asymptotisches Verhalten mit zunehmendem n . Es kann auch modifiziert werden, um ein stabiles Verhalten bereitzustellen.

Eimersortierung

Bucket-Sort ist ein Sortieralgorithmus zum Teilen und Erobern, der die Zählsortierung verallgemeinert , indem er ein Array in eine endliche Anzahl von Buckets aufteilt. Jeder Eimer wird dann einzeln sortiert, entweder unter Verwendung eines anderen Sortieralgorithmus oder durch rekursives Anwenden des Eimersortierungsalgorithmus.

Eine Bucket-Sortierung funktioniert am besten, wenn die Elemente des Datasets gleichmäßig auf alle Buckets verteilt sind.

Radix sortieren

Radix sort ist ein Algorithmus, der Zahlen sortiert, indem er einzelne Ziffern verarbeitet. n Zahlen mit jeweils k Ziffern werden in O( n · k ) -Zeit sortiert . Radix sort kann Ziffern jeder Zahl entweder beginnend mit der niedrigstwertigen Stelle (LSD) oder beginnend mit der höchstwertigen Stelle (MSD) verarbeiten. Der LSD-Algorithmus sortiert die Liste zuerst nach der am wenigsten signifikanten Ziffer, während die relative Reihenfolge unter Verwendung einer stabilen Sortierung beibehalten wird. Dann sortiert es sie nach der nächsten Ziffer und so weiter, von der niedrigstwertigen zur höchstwertigen, was zu einer sortierten Liste führt. Während die LSD-Radixsortierung die Verwendung einer stabilen Sortierung erfordert, tut dies der MSD-Radixsortierungsalgorithmus nicht (es sei denn, eine stabile Sortierung ist erwünscht). Die direkte MSD-Radixsortierung ist nicht stabil. Es ist üblich, dass der Zähl- Sortieralgorithmus intern von der Radix-Sortierung verwendet wird. Ein hybrider Sortieransatz, wie die Verwendung von Insertion-Sort für kleine Behälter, verbessert die Leistung der Radix-Sortierung erheblich.

Speichernutzungsmuster und Indexsortierung

Wenn die Größe des zu sortierenden Arrays sich dem verfügbaren Primärspeicher nähert oder diesen überschreitet, so dass (viel langsamerer) Platten- oder Swap-Speicherplatz verwendet werden muss, wird das Speichernutzungsmuster eines Sortieralgorithmus wichtig, und ein Algorithmus, der angemessen gewesen sein könnte effizient, wenn das Array leicht in den RAM passt, kann unpraktisch werden. In diesem Szenario wird die Gesamtzahl der Vergleiche (relativ) weniger wichtig, und die Häufigkeit, mit der Speicherabschnitte auf und von der Platte kopiert oder ausgelagert werden müssen, kann die Leistungsmerkmale eines Algorithmus bestimmen. Daher kann die Anzahl der Durchläufe und die Lokalisierung von Vergleichen wichtiger sein als die reine Anzahl der Vergleiche, da Vergleiche benachbarter Elemente miteinander mit Systembusgeschwindigkeit (oder beim Caching sogar mit CPU- Geschwindigkeit) erfolgen, was im Vergleich zur Festplattengeschwindigkeit, ist praktisch augenblicklich.

Zum Beispiel bietet der beliebte rekursive Quicksort- Algorithmus eine recht vernünftige Leistung mit ausreichend RAM, aber aufgrund der rekursiven Art, wie er Teile des Arrays kopiert, wird es viel weniger praktisch, wenn das Array nicht in den RAM passt, da dies zu einer Reihe von Fehlern führen kann langsame Kopier- oder Verschiebevorgänge auf und von der Festplatte. In diesem Szenario kann ein anderer Algorithmus vorzuziehen sein, selbst wenn er mehr Gesamtvergleiche erfordert.

Eine Möglichkeit, dieses Problem zu umgehen, das gut funktioniert, wenn komplexe Datensätze (z. B. in einer relationalen Datenbank ) nach einem relativ kleinen Schlüsselfeld sortiert werden, besteht darin, einen Index im Array zu erstellen und dann den Index zu sortieren, anstatt den gesamten Array. (Eine sortierte Version des gesamten Arrays kann dann mit einem Durchlauf erzeugt werden, indem aus dem Index gelesen wird, aber oft ist auch das unnötig, da der sortierte Index ausreichend ist.) Da der Index viel kleiner ist als das gesamte Array, kann es passen problemlos in den Speicher, wo nicht das gesamte Array wäre, wodurch das Problem des Festplattenaustauschs effektiv beseitigt wird. Dieses Verfahren wird manchmal als "Tag-Sortierung" bezeichnet.

Eine andere Technik zur Überwindung des Speichergrößenproblems ist die Verwendung einer externen Sortierung , beispielsweise besteht eine der Möglichkeiten darin, zwei Algorithmen so zu kombinieren, dass die Stärke jedes einzelnen ausgenutzt wird, um die Gesamtleistung zu verbessern. Zum Beispiel könnte das Array in Chunks mit einer Größe unterteilt werden, die in den RAM passt, der Inhalt jedes Chunks mit einem effizienten Algorithmus (wie quicksort ) sortiert und die Ergebnisse mit einem k- way-Merge ähnlich dem in . zusammengeführt werden zusammenführen sortieren . Dies ist schneller, als entweder eine Zusammenführungssortierung oder eine Schnellsortierung über die gesamte Liste durchzuführen.

Techniken können auch kombiniert werden. Zum Sortieren sehr großer Datenmengen, die den Systemspeicher erheblich überschreiten, muss möglicherweise sogar der Index unter Verwendung eines Algorithmus oder einer Kombination von Algorithmen sortiert werden, die dafür ausgelegt sind, vernünftig mit dem virtuellen Speicher zu arbeiten , dh um den Umfang des erforderlichen Austauschens zu reduzieren.

Verwandte Algorithmen

Verwandte Probleme umfassen teilweises Sortieren (Sortieren nur der k kleinsten Elemente einer Liste oder alternativ Berechnen der k kleinsten Elemente, aber ungeordnet) und Auswahl (Berechnen des k -kleinsten Elements). Diese können durch eine Gesamtsortierung ineffizient gelöst werden, es gibt jedoch effizientere Algorithmen, die oft durch Verallgemeinerung eines Sortieralgorithmus abgeleitet werden. Das bemerkenswerteste Beispiel ist Quickselect , das mit Quicksort verwandt ist . Umgekehrt können einige Sortieralgorithmen durch wiederholte Anwendung eines Auswahlalgorithmus abgeleitet werden; Quicksort und Quickselect können als der gleiche Pivot-Zug angesehen werden, der sich nur darin unterscheidet, ob man auf beiden Seiten (Quicksort, Divide and Conquer ) oder auf einer Seite (Quickselect, Reduce und Conquer ) rekursiert .

Eine Art Gegenstück zu einem Sortieralgorithmus ist ein Mischalgorithmus . Diese unterscheiden sich grundlegend, da sie eine Quelle von Zufallszahlen benötigen. Das Mischen kann auch durch einen Sortieralgorithmus realisiert werden, nämlich durch eine zufällige Sortierung: Zuweisen einer Zufallszahl zu jedem Element der Liste und anschließendes Sortieren anhand der Zufallszahlen. Dies wird in der Praxis jedoch im Allgemeinen nicht durchgeführt, und es gibt einen bekannten einfachen und effizienten Algorithmus zum Mischen: den Fisher-Yates-Shuffle .

Siehe auch

• Kollation  – Zusammenfügen von schriftlichen Informationen zu einer Standardbestellung
• Schwartzsche Transformation
• Suchalgorithmus  – Jeder Algorithmus, der das Suchproblem löst
• Quantum sort  – Sortieralgorithmen für Quantencomputer

Verweise

Weiterlesen

• Knuth, Donald E. (1998), Sortieren und Suchen , The Art of Computer Programming, 3 (2. Aufl.), Boston: Addison-Wesley, ISBN 0-201-89685-0
• Sedgewick, Robert (1980), "Efficient Sorting by Computer: An Introduction", Computational Probability , New York: Academic Press, S.  101–130 , ISBN 0-12-394680-8

Externe Links

• Sorting Algorithm Animations at the Wayback Machine (archiviert am 3. März 2015).
• Sequentielle und parallele Sortieralgorithmen – Erläuterungen und Analysen vieler Sortieralgorithmen.
• Wörterbuch der Algorithmen, Datenstrukturen und Probleme – Wörterbuch der Algorithmen, Techniken, allgemeinen Funktionen und Probleme.
• Etwas skeptische Sicht auf Sortieralgorithmen – Bespricht mehrere klassische Algorithmen und fördert Alternativen zum Quicksort- Algorithmus.
• 15 Sortieralgorithmen in 6 Minuten (Youtube) – Visualisierung und „Anhörung“ von 15 Sortieralgorithmen in 6 Minuten.
• A036604-Sequenz in der OEIS-Datenbank mit dem Titel "Sorting numbers: minimal number of Comparisons need to sort n elements" – Durchgeführt vom Ford-Johnson-Algorithmus .
• Sortieralgorithmen für berühmte Gemälde (Youtube) - Visualisierung von Sortieralgorithmen für viele berühmte Gemälde.
• Ein Vergleich von Sortieralgorithmen - Führt eine Reihe von Tests von 9 der wichtigsten Sortieralgorithmen mit Python timeit und Google Colab durch.