Stell Dir vor, Du willst die Geburtsdaten von Personen aus Deiner Familie oder Deinem Freundeskreis sortieren. Wie würdest Du dabei vorgehen? Genau – Du schaust Dir Jahr, Monat und Tag getrennt voneinander an und sortierst die Daten danach.
Wenn Du das schon einmal getan haben solltest, dann herzlichen Glückwunsch, denn Du hast Radix Sort bereits eingesetzt. Wie der Algorithmus genau funktioniert, erfährst Du hier.
Radix Sort Erklärung
Das Grundprinzip beim Radix Sort oder auch Radixsort Sortieralgorithmus ist es, mit Warteschlangen (Queues) zu arbeiten. Mit jedem weiteren Schritt erhältst Du mehr Informationen für die endgültige Sortierung. Das Sortierverfahren ist auch als "Distributionsort" bekannt oder wird als "Fachverteilen" bezeichnet.
Radixsort arbeitet wie Quicksort und Mergesort nach dem Teile-und-Herrsche-Prinzip ("divide an conquer").
"radix" stammt aus dem Lateinischen und bedeutet so viel wie "Wurzel". Mit Wurzelziehen hat der Algorithmus jedoch nichts zu tun. Stattdessen ist mit dem Begriff "Radix Sort" die Basis eines Zahlensystems gemeint. Bei einem Binärsystem wäre das die 2, bei einem Dezimalsystem die 10 usw.
Radix Sort Definition
Radix Sort ist ein linearer, nicht vergleichsbasierter Sortieralgorithmus, der Datenmengen in mehreren Phasen partitioniert, vorsortiert und wieder einsammelt, bis eine sortierte Liste entsteht.
Der Radixsort Sortieralgorithmus baut auf den beiden ebenfalls nicht vergleichsbasierten Sortierverfahren Bucketsort und Countingsort auf.
Mehr zu Bucketsort und Countingsort findest Du in gleichnamigen Erklärungen auf StudySmarter.
Radix Sort Voraussetzungen
Eine Voraussetzung für Radix Sort ist eine totale Quasiordnung, die innerhalb der zu sortierenden Datenmenge vorliegen muss.
Der Begriff totale Quasiordnung stammt aus der Mathematik und besagt, dass zwei Elemente immer vergleichbar sein müssen. Für alle a, b ∈ M muss entsprechend gelten:
a ≤ b ∨ b ≤ a
Damit ist (M, ≤) eine totale Quasiordnung.
Außerdem muss die Länge der Schlüssel von Anfang an bekannt sein, bzw. begrenzt sein. Das liegt daran, dass die Anzahl der Schlüsselstellen eine relativ große Auswirkung auf die Laufzeit des Algorithmus hat.
Radix Sort Beispiel
Der Radixsort Algorithmus lässt sich am besten mit einem Beispiel erklären. Gegeben ist folgendes Array:
Das Array wird jetzt mehrmals durchlaufen, dabei wird immer nur ein bestimmter Teil der Elemente betrachtet. Welcher Teil wird im Vorfeld festgelegt – in diesem Fall wird bei der letzten/niedrigst-wertigen Ziffer begonnen. Elemente werden bei Radixsort in zwei Phasen sortiert:
Partitionierungsphase
Sammelphase
In der Partitionierungsphase sortierst Du die Datenmengen zunächst in Buckets ein – ähnlich, wie Du es vielleicht bereits von Bucketsort kennst. Während der Sammelphase werden die Buckets einzeln durchlaufen und die darin einsortierten Elemente werden von links nach rechts in eine neue Liste geschrieben. Beide Phasen werden abwechselnd so lange durchlaufen, bis das Array vollständig sortiert ist.
1. Partitionierungsphase
Für die Partitionierungsphase legst Du Dir zunächst leere "Buckets" an – in diesem Fall 10 Stück mit den Zahlen 0 bis 9. Gehe nun von links nach rechts durch das gegebene Array und sortiere die Elemente anhand ihrer letzten Ziffer in die Felder ein.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 321 | | 23 | | 5 | 6 | 497 | 28 | |
| | | | | | | | 258 | |
1. Sammelphase
In der 1. Sammelphase durchläufst Du die vorher angelegten Buckets von links nach rechts und "sammelst" die darin einsortierten Elemente ein. Schreibe diese in ein neues Array. Die Reihenfolge innerhalb der Buckets änderst Du dabei nicht. Die 28 ist vor der 258 in das Bucket einsortiert worden, entsprechend wird die 28 auch zuerst wieder herausgenommen.
Nach einer Sammelphase sind die vorher angelegten Buckets wieder leer.
2. Partitionierungsphase
Beginne damit, Dein neues Array wieder von links nach rechts in die Buckets einzusortieren – diesmal jedoch nach ihrer Zehnerstelle.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 05 | | 321 | | | 258 | | | | 497 |
| 06 | | 23 | | | | | | | |
| | 28 | | | | | | | |
Um Dir die Einsortierung zu erleichtern, kannst Du bei den Ziffern, die einstellig sind, einfach eine Null an der Zehnerstelle ergänzen. Das Gleiche gilt im dritten Durchlauf für die Hunderterstellen.
2. Sammelphase
In der 2. Sammelphase sammelst Du die Zahlen wieder aus den Buckets heraus und erstellst ein neues Array.
Denkst Du Dir an dieser Stelle die erste Ziffer der Hunderter-Elemente weg, wird Dir auffallen, dass die Elemente jetzt bereits nach ihren letzten zwei Ziffern richtig sortiert sind. Fehlt nun also noch die Hunderterstelle.
3. Partitionierungsphase
Jetzt folgt das gleiche Prozedere noch einmal für die Hunderterstelle. Sortiere Dein neues Array also erneut in die wieder geleerten Buckets ein, diesmal jedoch nach ihrer ersten Ziffer.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 005 | | 258 | 321 | 497 | | | | | |
| 006 | | | | | | | | | |
| 023 | | | | | | | | | |
| 028 | | | | | | | | | |
3. Sammelphase
Anschließend sammelst Du die Elemente wie gehabt wieder ein und schreibst sie in ein neues Array.
Fertig ist Dein mit Radix Sort sortiertes Array. Das Endergebnis kannst Du jetzt noch ohne die eingefügten Nullen schreiben.
Radix Sort Vorgehensweise
Noch einmal kurz und knapp, wie gehst Du beim Radix Sort Algorithmus vor:
- Führe abwechselnd folgende zwei Phasen so lange durch, bis die Datenmenge vollständig sortiert ist:
- Partitionierungsphase: Sortiere die Datenmenge in vorher angelegte Buckets ein.
- Sammelphase: "Sammele" die Elemente von links nach rechts aus den Buckets heraus und lege eine neue Liste/ein neues Array an.
Vor dem Sortieren musst Du noch festlegen, nach welcher Radixsort Variante Du sortieren willst. Mehr dazu findest Du im nachfolgenden Abschnitt.
Radix Sort Varianten
Den Radix Sort Algorithmus gibt es in zwei Varianten:
- LSD Radix Sort
- MSD Radix Sort
LSD steht für "least significant digit" und bedeutet so viel wie "niedrigst-wertige Stelle". Das heißt, Du beginnst die Elemente nach dem niedrigsten Wert zu sortieren. MSD Radix Sort ("most signifikant digit") sortiert zuerst nach der höchst-wertigsten Stelle.
Das oben gezeigte Beispiel arbeitet nach dem LSD Radix Sort Verfahren – zuerst werden die Einerstellen, dann die Zehner- und anschließend die Hunderterstellen betrachtet.
Neben den hier erwähnten zwei Varianten werden häufiger die Begriffe "Radix Exchange Sort", "Fachverteilen" und "Forward Radix Sort" verwendet. Das Fachverteilen entspricht dem hier bereits beschriebenen LSD Verfahren und der Radix Exchange Sort dem MSD.
Forward Radix Sort ist eine weitere Variante des Fachverteilens, das eine bestimmte Anzahl von Buckets verwendet und ebenfalls nach den höchst wertigsten Ziffern sortiert.
MSD Radix Sort
Wie würdest Du beim MSD Radix Sort vorgehen? Sortiert wird hierbei zunächst nach der höchst-wertigsten Stelle – also der Hunderterstelle. Betrachte noch einmal das Beispiel von oben:
Um das Array sortieren zu können, würdest Du zunächst an den entsprechenden Stellen Nullen ergänzen:
Würdest Du das jetzt sortieren wie bei der LSD Variante, bekommst Du nach den Sammelphasen folgende Ergebnisse:
Du siehst, dass das Sortieren nach Zehner- und Einerstellen die vorherigen Sortierungen wieder durcheinandergebracht hat.
Doch wie löst man das Problem? Nachdem Du nach der Hunderterstelle sortiert hast, darfst Du das neue Array nicht erneut komplett sortieren. Stattdessen sortierst Du die Hunderterstellen in sich. Anders gesagt, die MSD Variante muss rekursiv durchgeführt werden.
Wie sieht das konkret aus? Die erste Partitionierungsphase würde bei dem Beispiel wie folgt aussehen:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 005 | | 258 | 321 | 497 | | | | | |
| 028 | | | | | | | | | |
| 023 | | | | | | | | | |
| 006 | | | | | | | | | |
Anstatt in die Sammelphase zu gehen, führst Du nun erneut eine Partitionierungsphase durch, allerdings auf der Zehnerstelle. Sind Buckets leer oder enthalten sie nur ein Element, musst Du diese nicht weitere partitionieren. In diesem Fall muss also nur das Bucket 0 weiter partitioniert werden.
Da die Buckets 0 und 2 immer noch mehr als ein Element enthalten, müssen diese erneut partitioniert werden.
Jetzt musst Du die einzelnen Partitionen rekursiv wieder durch Sammelphasen zusammenführen – also zuerst Einer- und dann Zehnerstellen. In der folgenden Tabelle ist noch einmal der Zwischenschritt der beiden Schritte in den Buckets abgebildet:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 005 | | 023 | 321 | 497 | | | | | |
| 006 | | 028 | | | | | | | |
| | 258 | | | | | | | |
Anschließend folgt die Sammelphase der Hunderterstelle, wodurch Du wiederum das fertig sortierte Array erhältst:
Radix Sort Komplexität
Die Komplexität von Radix Sort kann in die Laufzeit (Zeitkomplexität) und den zusätzlichen Speicheraufwand (Platzkomplexität) unterschieden werden.
Radix Sort Laufzeit
Radix Sort besitzt sowohl im Best-Case, Average-Case als auch im Worst-Case eine Laufzeit von O(k • (b + n)). Ist die maximale Länge von k bekannt und die Basis b definiert, erreicht der Algorithmus eine lineare Zeitkomplexität von O(n).
n = die Menge an zu sortierenden Elementen; k = die Anzahl möglicher Schlüsselwerte und b = die Basis/Anzahl der Buckets.
Radix Sort Platzkomplexität
Radix Sort kann sowohl in-place als auch out-of-place durchgeführt werden. Die Platzkomplexität beträgt dabei O(b + n). Das "b" wird dabei je nach Variante des Radix Sorts entweder für das Zählen der Elemente oder für die Referenzen auf die einzelnen Teilbereiche (Buckets) benötigt. Die zweite Variable "n" wird für die Buckets oder für zusätzliche Ziel-Arrays verwendet.
Eine Ausnahme ist rekursiv ausgeführtes MSD Radix Sort, welches ohne zusätzlichen Speicher auskommt. Dafür müssen die Elemente jedoch in einer bestimmten Art und Weise partitioniert werden.
Radix Sort – Weitere Begrifflichkeiten
In den folgenden Abschnitten werden noch weitere Begrifflichkeiten rund um Radixsort geklärt.
Radix Sort stabil – instabil
Der Radix Sort Sortieralgorithmus ist in der Regel stabil, nur in Ausnahmefällen ist der Algorithmus instabil. Rekursives MSD Radix Sort ist z. B. nicht stabil.
Radix Sort vergleichsbasiert
Radix Sort arbeitet nicht vergleichsbasiert, stattdessen werden Elemente Ziffer für Ziffer sortiert.
Radix Sort iterativ – rekursiv
Je nach Radixsort Variante wird der Algorithmus iterativ oder rekursiv implementiert.
LSD Radix Sort ist meist iterativ und MSD Radix Sort wird je nach zu sortierender Datenmenge eher rekursiv implementiert.
Radix Sort Parallelisierbarkeit
Sowohl der LSD als auch der MSD Radix Sort lassen sich parallelisieren. Bei der MSD Variante geht das relativ leicht, da Du weitere Partitionierungsphasen nach der ersten einfach parallel durchführen lassen kannst. Die Parallelisierung bei der LSD Variante ist hingegen komplizierter, aber theoretisch auch machbar.
Parallel durchgeführter Radixsort ist in den meisten Fällen deutlich schneller als sequenzieller Radixsort.
Radix Sort Zusammenfassung
In der folgenden Übersicht findest Du das bisher Gelernte auf einem Blick:
| Best-Case | Average-Case | Worst-Case | Platz-komplexität | Stabiles Verfahren | vergleichs-basiert | In-Place / out-of-place | Parallelisier-barkeit | iterativ/rekursiv |
O(k • (b + n)) | O(k • (b + n)) | O(k • (b + n)) | O(b + n) | Meistens stabil | Nein | Beides möglich | Möglich | Beides |
Radix Sort Vorteile
Radix Sort hat verschiedene Vorteile, dazu zählen:
einfach zu implementieren
schnelles Sortierverfahren aufgrund der linearen Laufzeit
eignet sich auch gut für größere Datenmengen
im Vergleich zu Countingsort kommt Radix Sort mit einer größeren Anzahl von Schlüsselwerten klar
Radix Sort Nachteile
Neben Vorteilen hat Radixsort auch Nachteile:
Der Algorithmus hat eine längere Laufzeit, wenn die Schlüsselwerte (k) länger werden.
Sind Operationen wie Einfüge- und Löschfunktionen nicht effizient genug, ist Radix Sort langsamer als z. B. Mergesort oder Quicksort.
Radix Sort vs. Quicksort
Quicksort zerlegt Datenmengen ebenfalls in Teilmengen (Partitionen). Dabei werden Elemente anhand von selbst gewählten Pivot-Elementen sortiert. Quicksort ist im Gegensatz zu Radix Sort ein Sortieralgorithmus mit einer logarithmischen Laufzeit von O(n log n) im Best-Case und Average-Case.
Weitere Informationen zu Quicksort findest Du in einer eigenständigen Erklärung auf StudySmarter.
Bucket Sort vs. Radix Sort
Auch der Bucketsort Sortieralgorithmus arbeitet mit sogenannten Buckets, in die Datenmengen einsortiert werden. Innerhalb dieser Buckets wird dann mithilfe von anderen Sortieralgorithmen weiter sortiert. Bucketsort ist wie Radixsort ein lineares Sortierverfahren mit einer Laufzeit von O(n + k) im Best-Case und Worst-Case und O(n) im Average-Case.
Der hier vorgestellte MSD Radix Sort ist eine Variante des Bucket Sort Algorithmus.
Radix Sort Pseudocode
Es folgt noch ein Beispiel, wie Radix Sort in Pseudocode aussehen könnte:
RadixSort(Array, d) // d = maximale Anzahl an Ziffern des größten Elements im Array
for j = 1 to d do
// A[] --> initialisiere ein Array zum Sortieren
int count[10] = {0};
// lege die Anzahl möglicher Schlüsselwerte k ("keys") in count[] fest
for i = 0 to n do
count[key of(A[i]) in pass j]++
for k = 1 to 10 do
count[k] = count[k] + count[k-1]
// Lege ein neues Array mit den neuen Positionen der Elemente von A[i] an
for i = n-1 downto 0 do
result[count[key of(A[i])]] = A[j]
count[key of(A[i])]--
// Das Hauptarray A[] enthält nun die sortierten Elemente entsprechend der aktuellen Stelle
for i=0 to n do
A[i] = result[i]
end for(j)
end funcRadix Sort – Das Wichtigste
- Radix Sort Erklärung: Radix Sort ist ein linearer, stabiler, nicht vergleichsbasierter Sortieralgorithmus, der Datenmengen in mehreren Phasen partitioniert, vorsortiert und wieder einsammelt, bis eine sortierte Liste entsteht.
- Radix Sort Voraussetzungen: Es muss eine totale Quasiordnung in der zu sortierenden Datenmenge vorliegen und die Anzahl an Schlüsseln sollte begrenzt sein.
- Die Laufzeit vom Radix Sort Algorithmus beträgt O(k • (b + n)). Die Platzkomplexität liegt bei O(b + n).
- Vorteile von Radix Sort sind eine einfache Implementation, außerdem ist der Algorithmus schnell und eignet sich gut für größere Datenmengen.
- Nachteil von Radix Sort ist die längere Laufzeit, wenn die Schlüssel nicht von Anfang an begrenzt sind.
- Radix Sort vs. Quicksort: Quicksort hat im Best-Case und Average-Case eine logarithmische Laufzeit von O(n log n).
- Bucket Sort vs. Radix Sort: Bucket Sort hat im Average-Case eine lineare Laufzeit von O(n).
Nachweise
- Happycoders.eu: Radix Sort – Algorithmus, Quellcode, Zeitkomplexität. (18.11.2022)
- Codingeek.com: Radix Sort – Explanation, Pseudocode and Implementation. (18.11.2022)
Erklärungen 
Magazine 
