Vergleich der Sortieralgorithmen

Sortieralgorithmen sind ein wichtiger Bestandteil der Datenverwaltung. AtCprogramming.com bieten wir Tutorials zum Verständnis der wichtigsten undgemeinsame Sortiertechniken. Jeder Algorithmus hat besondere Stärken undschwächen und in vielen Fällen ist es am besten, einfach die eingebaute Sortierfunktion qsort zu verwenden. Für Zeiten, in denen dies keine Option ist oder Sie nur brauchenein schneller und schmutziger Sortieralgorithmus, es gibt eine Vielzahl von Möglichkeiten.

Die meisten Sortieralgorithmen arbeiten durch Vergleichen der zu sortierenden Daten. In einigen Fällen kann es wünschenswert sein, einen großen Datenblock (z. B. eine Struktur, die einen Namen und eine Adresse enthält) nur anhand eines Teils dieser Daten zu sortieren.Die Daten, die tatsächlich zur Bestimmung der sortierten Reihenfolge verwendet werden, werden als Schlüssel bezeichnet.
Sortieralgorithmen werden normalerweise nach ihrer Effizienz beurteilt. In diesem Fall bezieht sich Effizienz auf die algorithmische Effizienz, da die Größe der Eingabe wächst und im Allgemeinen auf der Anzahl der zu sortierenden Elemente basiert. Die meisten verwendeten Algorithmen haben eine algorithmische Effizienz von entweder O (n ^ 2) odero (n * log (n)). Einige Spezialfallalgorithmen (ein Beispiel wird in Programmierperlen erwähnt) können bestimmte Datensätze schneller sortieren als O(n* log(n)) . Diese Algorithmen basieren nicht auf dem Vergleich der zu sortierenden Elemente und beruhen auf Tricks. Es hat sich gezeigt, dass kein Schlüsselvergleichsalgorithmus eine bessere Leistung erbringen kann als O (n * log (n)).
Viele Algorithmen, die die gleiche Effizienz haben, haben nicht die gleiche Geschwindigkeit auf dem gleichen Eingang. Zunächst müssen Algorithmen anhand ihrer Effizienz im Durchschnittsfall, im besten Fall und im schlimmsten Fall beurteilt werden. Einige Algorithmen, wie z. B. Quick Sort, funktionieren für einige Eingaben außergewöhnlich gut, für andere jedoch schrecklich. Otheralgorithmen, wie merge sort, sind von der Reihenfolge der Eingabedaten nicht betroffen.Sogar eine modifizierte Version von Bubble sort kann für die günstigsten Eingaben in O (n) enden.Ein zweiter Faktor ist der „konstante Term“. Da die Big-O-Notation viele Details eines Prozesses abstrahiert, ist sie sehr nützlich, um das bigpicture zu betrachten. Aber eine Sache, die herausfällt, ist die Konstante vor theexpression: Zum Beispiel ist O(c * n) nur O(n). In der realen Welt, theconstant, c, wird über verschiedene Algorithmen variieren. Ein gut implementierter quicksort sollte einen viel kleineren konstanten Multiplikator als Heap-Sortierung haben.
Ein zweites Kriterium für die Beurteilung von Algorithmen ist ihr Platzbedarf – benötigen sie zusätzlichen Platz oder kann das Array an Ort und Stelle sortiert werden (ohne zusätzlichen Speicher über einige Variablen hinaus)? Einige Algorithmen benötigen niemals zusätzlichen Speicherplatz, während andere am einfachsten zu verstehen sind, wenn sie mit zusätzlichem Speicherplatz implementiert werden (die Heap-Sortierung kann beispielsweise an Ort und Stelle erfolgen, aber konzeptionell ist es viel einfacher, sich einen separaten Heap vorzustellen). Der Platzbedarf kann sogar von der verwendeten Datenstruktur abhängen (z. B. Sortierung nach Arrays zusammenführen oder Sortierung nach verknüpften Listen zusammenführen).
Ein drittes Kriterium ist die Stabilität – bewahrt die Sortierung die Reihenfolge der Schlüssel mit gleichen Werten? Die meisten einfachen Sortierungen tun genau dies, aber einige Sortierungen, wie z. B. Heap-Sortierung, nicht.
Die folgende Tabelle vergleicht Sortieralgorithmen auf den verschiedenen criteriaoutlined oben; die Algorithmen mit höheren konstanten Termen erscheinen zuerst, obwohl dies eindeutig ein implementierungsabhängiges Konzept ist und nur als grobe Richtlinie bei der Auswahl zwischen Sorten derselben Big-O-Effizienz herangezogen werden sollte.

	Time
Sort	Average	Best	Worst	Space	Stability	Remarks
Bubble sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Always use a modified bubble sort
Modified Bubble sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	Stops after reaching a sorted array
Selection Sort	O(n^2)	O(n^2)	O(n^2)	Konstante	Stabil	Selbst eine perfekt sortierte Eingabe erfordert das Scannen des gesamten Arrays
Einfügesortierung	O(n^2)	O(n)	O(n^2)	Konstante	Stabil	Im besten Fall (bereits sortiert)benötigt jede Einfügung eine konstante Zeit
Heap-Sortierung	O(n*log(n))	O(n*log(n))	O(n*log(n))	Konstant	Instabil	Durch die Verwendung eines Eingabearrays als Speicher für den Heap kann ein konstanter Speicherplatz erreicht werden
Sortierung zusammenführen	O(n*log(n))	O(n*log(n))	O(n*log(n))	Abhängig	Stabil	Bei Arrays erfordert die Zusammenführungssortierung O(n) Platz; Bei verknüpften Listen erfordert die Zusammenführungssortierung konstanten Platz
Quicksort	O(n*log(n))	O(n*log(n))	O(n^2)	Constant	Stable	Das zufällige Auswählen eines Pivot-Werts (oder das Mischen des Arrays vor dem Sortieren) kann dazu beitragen, Worst-Case-Szenarien wie ein perfekt sortiertes Array zu vermeiden.