Radix Sort
Sortiert Stelle für Stelle in Buckets, ohne direkten Wertevergleich.
- Vergleiche 0
- Tauschvorgänge 0
- sortierte Indizes 0
- Vergleich
- Tausch
- sortiert
Pseudocode
1 max = max(a); exp = 1
2 while max / exp > 0
3 countingSortByDigit(exp)
4 exp *= 10
5
6 countingSortByDigit(exp):
7 count[0..9] = 0
8 for i from 0 to n - 1: count[digit(a[i], exp)]++
9 for d from 1 to 9: count[d] += count[d - 1]
10 output = new array of size n
11 for i from n - 1 downto 0
12 d = digit(a[i], exp)
13 output[count[d] - 1] = a[i]; count[d]--
14 copy output to a
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Radix Sort sortiert Zahlen Stelle für Stelle, ohne Werte direkt miteinander zu vergleichen. In der LSD-Variante (Least Significant Digit) startet der Algorithmus mit der niederwertigsten Stelle: er verteilt die Elemente in 10 Buckets (für die Ziffern 0 bis 9 im Dezimalsystem) und sammelt sie anschließend in der Bucket-Reihenfolge wieder ein. Dieser Schritt wird für jede Stelle wiederholt, bis die höchste Stelle erreicht ist. Weil das Verteilen pro Stelle stabil erfolgt, behält jede Iteration die Reihenfolge gleicher Schlüssel bei und nach der letzten Stelle ist das Array korrekt sortiert. Die Laufzeit ist O(d · (n + b)) mit d gleich der Stellenanzahl des größten Elements und b gleich der Basis (hier 10); für ganze Zahlen mit bekannter Größenordnung ist d konstant, sodass Radix Sort effektiv linear läuft. Der Speicherbedarf beträgt O(n + b) für die Buckets, und der Algorithmus ist stabil. Anwendbar nur auf nichtnegative Ganzzahlen oder Daten mit fester Stellenstruktur.
Komplexität
- Best Case
O(d · n) - Average Case
O(d · n) - Worst Case
O(d · n) - Zusatz-Speicher
O(n + b)
Wann verwenden?
Sortieren großer Mengen ganzzahliger Schlüssel mit beschränkter Stellenanzahl, etwa Telefonnummern, Postleitzahlen oder IPv4-Adressen. Auch in Datenbank-Engines und in der String-Sortierung als MSD-Variante (Most Significant Digit) zum Einsatz.