Wir verwenden Sortierungs-Algorithmen, um Elemente in einer Liste in eine
Reihenfolge zu sortieren. Neben anderen Anwendungen kann die
Sortierung angewendet werden, um einen Datensatz für einen anderen
Algorithmus vorzubereiten, zum Beispiel für die Binäre Suche.
Comparision Sort
Non-Comparision Sort
Counting Sort ( O(n + k) , SPACE: O(k))
Die Zählsortierung ist ein Algorithmus, mit dem wir in bestimmten
Fällen ein Array in linearer Zeit sortieren können. Um die Zählsortierung zu verwenden, darf unser Array nur Dezimalzahlen enthalten. Es wird davon ausgegangen, dass wir die Min- und Max-Werte kennen.
Counting Sort funktioniert, indem die Anzahl der Objekte gezählt werden. Jeder der
unterschiedlichen Schlüsselwerte wird anhand dieser Zählungen
arithmetisch verwendet, um die Positionen jedes Schlüsselwerts in der Ausgabesequenz zu bestimmen.
Die Laufzeit des Algorithmus ist linear in der
Anzahl der Elemente und der Differenz zwischen den maximalen und
minimalen Schlüsselwerten. Deshalb ist der Algorithmus nur für den direkten Einsatz in
Situationen geeignet, in denen die Variation der Schlüssel nicht
wesentlich größer ist als die Anzahl der Elemente. Er wird jedoch oft
als Unterprogramm in einem anderen Sortieralgorithmus (Radixsort),
verwendet, der größere Schlüssel effizienter handhaben kann. Die
Zählsortierung funktioniert am besten, wenn der Zahlenbereich für jedes Arrayelement sehr klein ist.
Bucket Sort (O(n + k))
Bucket Sort kann für viele der gleichen Aufgaben wie Counting Sort verwendet werden, mit einer ähnlichen Zeitanalyse. Im Vergleich zur Counting Sort erfordert die Bucket-Sortierung jedoch verknüpfte
Listen, dynamische Arrays oder eine große Menge an vorab zugewiesenem
Speicher, um die Sätze von Elementen in jedem Bucket zu speichern. Counting Sort speichert stattdessen eine einzelne Zahl (die
Anzahl der Elemente) pro Bucket.
Radix Sort (Best: O(n) , Worst: O(n^2)
In der Informatik ist Radixsort ein nicht vergleichender
Dezimalzahl-Sortieralgorithmus, der Daten mit ganzzahligen Schlüsseln
sortiert. Dies geschieht indem Schlüssel nach den einzelnen Ziffern gruppiert werden,
die dieselbe signifikante Position und denselben Wert haben. Eine
Positionsnotation ist erforderlich, aber da ganze Zahlen Zeichenfolgen
(z. B. Namen oder Datumsangaben) und speziell formatierte
Gleitkommazahlen darstellen können, ist die Radixsortierung nicht auf
ganze Zahlen beschränkt.