Radix Sort
Du hast den Radix Sort aktuell noch nicht wirklich verstanden? Hier zeigen wir dir das Prinzip von dem Sortieralgorithmus und dessen Vorgehensweise. Danach findest du ein ausführliches Beispiel und alle wichtigen Informationen zur Laufzeitkomplexität. Am Ende findest du drei verschiedene Implementierungen: einen allgemeinen Radix Sort Java Code, sowie auch eine iterative Version und abschließend eine rekursive Radix Sort C++ Implementierung.
Inhaltsübersicht
Grundidee
Der Radixsort kann aus dem lateinischen radix = Wurzel; Basis abgeleitet werden. Er ist auch als Distributionsort oder Fachverteilen bekannt. Dabei handelt es sich um ein lineares Sortierverfahren basierend auf dem Counting Sort und Bucketsort . Es kann entweder stabile out-of-place oder instabile in-place Varianten realisiert werden. Des Weiteren kann zwischen Verfahren unterschiedenen werden. Zum einen das MSD-Verfahren (englisch most significant digit), bei dem die Stelle mit dem höchsten Wert beginnt oder das LSD-Verfahren (englisch least significant digit), bei dem die niedrigste Stelle beginnt und sich zur höchstwertigen Stelle vorarbeitet.
Die Grundidee dahinter ist eigentlich nur, dass wir bei diesem Sortieralgorithmus mit Queues – also Warteschlagen – arbeiten. Das bedeutet, dass wir mit jedem zusätzlichen Schritt eine weitere Sortierinformation erhalten. Das führt im Endeffekt zur fertigen Sortierung. Beim Radixsort bestehen die Schlüssel aus Zeichen eines endlichen Alphabets der zu ordnenden Elemente. Dabei muss eine totale Quasiordnung zwischen den Zeichen des Alphabets vorhanden sein.
Vorgehensweise
Als Prinzip heißt das, dass wir in jedem Durchlauf die einzelnen Elemente durchgehen und dabei nur einen bestimmten Teil davon begutachten. Als Beispiel kannst du dir ein Geburtsdatum vorstellen, welches aus Tag, Monat und Jahr besteht. Dabei starten wir immer beim letzten Element (z.B. das Jahr) und arbeiten uns – Durchlauf für Durchlauf- zum ersten Element (z.B. Tag) in zwei Phasen vor.
Partitionierungsphase
In der Partitionierungsphase werden die Daten in das vorhandene Fach aufgeteilt. Dabei gibt es für jedes einzelne Zeichen des jeweiligen Alphabets ein eigenes Fach. Für Buchstaben also beispielweise jeweils ein Fach a, ein Fach b, etc. Wir ordnen dann immer die zusammengehörige Elementreihe entsprechend unseres geprüften Elements in eine passende Spalte ein. Heißt also, wenn wir das dritte Element der Reihe von hinten betrachten, würde „abb“ in das Fach „b“ einsortiert werden.
Sammelphase
Die zweite Phase ist die Sammelphase. Dabei fügen wir die Inhalte der einzelnen Fächer wieder zu einer neu sortierten Liste zusammen, beginnend mit dem Fach mit der niedrigsten Wertigkeit. Dabei ist es wichtig zu beachten, dass die Reihenfolge der Elemente innerhalb der Fächer nicht verändert werden darf.
Das Ganze wird so oft wiederholt, bis alle einzelnen Stellen der Schlüssel einmal geprüft worden sind.
Radix Sort Laufzeit
Aber wie sieht es beim Radix Sort mit der Laufzeit aus? Die Laufzeit lässt sich in etwa mit 
abschätzen. Das l ist dabei die Länge eines Schlüssels, also in unserem Beispiel wäre l = 3. n stellt die Anzahl der zu sortierenden Elemente dar. Entsprechend ist natürlich klar, dass die Laufzeit linear proportional mit der Anzahl der vorhandenen Elemente ist – also n. Eine lineare Laufzeit ist davon abhängig, ob die maximale Länge der zu sortierenden Elemente von Beginn an bekannt ist.
Implementierung – Radix Sort Java
Ein Beispielcode für eine Radix Sort Java-Implementierung kann wie folgt aussehen:
class Radix_Sortieralgorithmus {
public static void main (String[] args)
{
int liste[] = {…};
int i = liste.length;
radixsort(liste, i);
ausgeben(liste, i);
}
static int maximum(int liste[], int i)
{
int max = liste[0];
for (int a = 1; a
if (liste[a] > max)
max = liste[a];
return max;
}
static void countingsort(int liste[], int i, int faktor)
{
int ausgabe[] = new int[i];
int a;
int zaehlen[] = new int[10];
Arrays.fill(zaehlen,0);
for (a = 0; a
zaehlen[ (liste[a]/faktor)%10 ]++;
for (a = 1; a
zaehlen[a] += zaehlen[a – 1];
for (a = i – 1; a >= 0; a–)
{
ausgabe[zaehlen[ (liste[a]/faktor)%10 ] – 1] = liste[a];
zaehlen[ (liste[a]/faktor)%10 ]–;
}
for (a = 0; a
liste[a] = ausgabe[a];
}
static void radixsort(int liste[], int i)
{
int m = maximum(liste, i);
for (int faktor = 1; m/faktor > 0; faktor *= 10)
countingsort(liste, i, faktor);
}
static void ausgeben(int liste[], int i)
{
for (int a=0; a
System.out.print(liste[a]+“ „);
}}
Iterativ – Radix Sort Java
Im Folgenden ist ein Radix Sort Java-Methode zum Sortieren einer Integer-Liste. Bei dem Code werden potenzielle Vorzeichen nicht beachtet und sollte nur bei positiven Zahlen genutzt werden. Zusätzlich wird eine Schleife über alle Bits der Schlüssel bei 32 Bit gesetzt.
public static void radixsort(int[] i) {
int nummer;
int[] anzahlfach = new int[2];
int[][] fach = new int[2][i.length];
for (int j=0; j
anzahlfach[0] = 0;
anzahlfach[1] = 0;
for (int k=0; k
nummer = (i[k]>>j)&1;
fach[nummer][anzahlfach[nummer]++] = i[k];
}
System.arraycopy(fach[0], 0, i, 0, anzahlfach[0]);
System.arraycopy(fach[1], 0, i, anzahlfach[0], anzahlfach[1]);
}
}Rekursiv – Radix Sort C++
Hier wird Beispielcode für eine Radix Sort C++-Implementierung zur Sortierung eines Integer-Arrays oder -Containers dargestellt, die Minimum einen Forward-Iterator enthält.
void radixsort(const ForwardIterator erster, const ForwardIterator letzter, int faktor = 10) { std::map > buckets;for (ForwardIterator a = erster; a != letzter; ++a) {if (faktor == 10) buckets[*a%faktor].push_back(*a); else buckets[(*a/(faktor/10)) %10].push_back(*a); } ForwardIterator ersterneu = erster; for (int a = 0; a for (std::vector::const_iterator b = buckets[a].begin(); b != buckets[a].end(); ) *ersterneu++ = *b++; } if (faktor > *std::max(erster, letzter)) { return; } else { faktor *= 10; radixsort(erster, letzter, faktor); } }