Der Algorithmus
Der Radix Sort-Algorithmus sortiert Zahlensysteme anhand ihrer Stellen. Der Radix Sort wird daher auch Base Sort genannt. Dies bedeutet, dass je Stelle ein eigenes Sortierverfahren (zumeist Counting Sort weil Wertebereich überschaubar) eingesetzt wird. Man würde also bei 3 Stellen auch 3x sortieren.
Es gibt einen Most- und Least-Significant-Radix-Sort (MSD / LSD Radix Sort). LSD beginnt bei der niedrigsten Stelle (z.B. den Einern) und bewegt sich zu den höheren Stellen (z.B. Zehner, Hunderter). Bei MSD Radix Sort ist das umgekehrt.
Eine wichtige Voraussetzung ist, das man die gleiche Anzahl an Stellen hat (also z.B. 2 (Tupel), 3 (Tripel) oder mehr Stellen). Weiterhin müssen die vorhandenen Elemente in dem Zahlensystem (z.B. Dezimal 0-9) in einer Reihenfolge nach Rang sortierbar sein. D.h. es sollte z.B. klar sein dass ein A vor einem B ist (z.B. durch ASCII-Werte).
Nehmen wir an, wir möchten die Zahlen [170, 45, 75, 90, 802, 24, 2, 66] sortieren:
LSD Radix Sort (von rechts nach links):
- Sortierung nach der 1er-Stelle: [170, 90, 802, 2, 24, 45, 75, 66]
- Sortierung nach der 10er-Stelle: [802, 2, 24, 45, 66, 170, 75, 90]
- Sortierung nach der 100er-Stelle: [2, 24, 45, 66, 75, 90, 170, 802]
Anwendung: Oft bei der Sortierung von Zahlen und Wörtern verwendet.
Vorteil: Einfacher zu implementieren und erfordert weniger komplexe Vergleiche.
MSD Radix Sort (von links nach rechts):
- Sortierung nach der 100er-Stelle: [170, 24, 2, 45, 66, 75, 802, 90]
- Sortierung nach der 10er-Stelle: [2, 24, 45, 66, 75, 90, 170, 802]
- Sortierung nach der 1er-Stelle: [2, 24, 45, 66, 75, 90, 170, 802]
Anwendung: Eignet sich gut für große Zahlenmengen oder lange Zeichenketten.
Vorteil: Kann effizienter sein, wenn die Daten ungleichmäßig verteilt sind.
Code von LSD Radix Sort
Der folgende Code hat die vergangenen Implementierungen von QuickSort und Counting Sort (ohne Stellensortierung durch Radix / Base Sort) mit einer Zeitmessung in Echtzeit verglichen und muss angepasst werden. Das nachfolgende Beispiel sortiert Dezimalzahlen (also ein Zahlensystem zur Basis 10).
package AlgoDat;
import java.util.Arrays;
public class RadixSort {
// Zu sortierendes Array
private static int myArrayRadixSort[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
public boolean verbose = false;
// Hält die Klassen als instanziertes Objekt
@SuppressWarnings("unused")
private static RadixSort programRadixSort;
@SuppressWarnings("unused")
private static HelperUtil helper;
// Hilfsfunktion für das Ausgeben des Arrays
public void OutputOfIntArray(int myArray[])
{
if (myArray != null)
{
for (int i = 0; i < myArray.length; i++) {
if (i > 0) System.out.print(";");
System.out.print(myArray[i]);
}
System.out.println();
}
}
public void radixSort(int[] arr)
{
int max = Arrays.stream(arr).max().getAsInt();
if (verbose) System.out.println("Größte Zahl im Array: " + max);
// Bei Dezimalzahlen muss die Basis 10 genommen werden
// ... bei Großbuchstaben z.B. die Basis 27
for (int exp = 1; max / exp > 0; exp *= 10)
{
if (verbose) System.out.println("Suche " + exp + "er.");
countingSort(arr, exp);
}
}
public void countingSort(int[] arr, int exp)
{
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// Alle 10 Elemente mit 0 initialisieren
for (int i = 0; i < 10; i++)
{
count[i] = 0;
}
// Histogramm erstellen
for (int i = 0; i < n; i++)
{
count[(arr[i] / exp) % 10]++;
}
// Kummuliere, so dass die Anfangspositionen in dem Array stehen
for (int i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
// Ausgabearray erstellen
for (int i = n - 1; i >= 0; i--)
{
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Kopiere das neu erstellte Array auf das zu ändernde Array
for (int i = 0; i < n; i++)
{
arr[i] = output[i];
}
}
// Konstruktor
public RadixSort(int[] toSort)
{
this.radixSort(toSort);
}
// Konstruktor
public RadixSort()
{
System.out.print("Vorher: ");
this.OutputOfIntArray(myArray);
this.radixSort(myArray);
System.out.print("Nachher: ");
this.OutputOfIntArray(myArray);
}
public static void main(String[] args)
{
helper = new HelperUtil();
// Es gibt 80 Mio Menschen in Deutschland, von denen keiner älter als 120 ist -> Kleiner Wertebereich
int[] alterDerMenschenInDeutschlandRS = helper.generateIntegerArrayOfSize(80000000, 120);
int[] alterDerMenschenInDeutschlandQS = alterDerMenschenInDeutschlandRS.clone();
int[] alterDerMenschenInDeutschlandCS = alterDerMenschenInDeutschlandRS.clone();
// Erwartung: Da Counting Sort eine lineare Laufzeit hat sollte er bei kleinem Wertebereich am Besten performen
System.out.println("\nEs gibt 80 Mio Menschen in Deutschland, von denen keiner älter als 120 ist -> Kleiner Wertebereich");
System.out.println("===================================================================");
long startZeitRS = System.nanoTime();
programRadixSort = new RadixSort(alterDerMenschenInDeutschlandRS);
long endZeitRS = System.nanoTime();
System.out.println((endZeitRS-startZeitRS) + " ns (Radix Sort)");
}
}
Ausgabe
Es gibt 80 Mio Menschen in Deutschland, von denen
keiner älter als 120 ist -> Kleiner Wertebereich
=======================================================
347584000 ns (Counting Sort)
2544168000 ns (Radix Sort)
3335958900 ns (Quick Sort)
Komplexität: O-Notation (Ordnung)
O(n*l) (l=Länge also bei ABC = Länge: 3 – Anzahl der max. Stellen0)
‣ Sortieren von Strings über einem endlichen Alphabet durch
mehrmaliges Anwenden von Counting Sort.
‣ Angenommen: Alle Wörter haben die Länge
‣ Z.b. Postleitzahlen
Laufzeit von Radix Sort: 𝒪(n), weil l ⋅ n Durchläufe
(Anzahl der Elemente des Eingabearrays) und 
(die Größe des Zahlenintervalls) ab. Die for-Schleifen werden jeweils 
.
