Radix Sort

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.

"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

Der Radixsort Sortieralgorithmus baut auf den beiden ebenfalls nicht vergleichsbasierten Sortierverfahren Bucketsort und Countingsort auf.

Radix Sort Voraussetzungen

Eine Voraussetzung für Radix Sort ist eine totale Quasiordnung, die innerhalb der zu sortierenden Datenmenge vorliegen muss.

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.

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.

2. Partitionierungsphase

Beginne damit, Dein neues Array wieder von links nach rechts in die Buckets einzusortieren – diesmal jedoch nach ihrer Zehnerstelle.

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.

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.

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.

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:

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.

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:

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).

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.

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.

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.

Radix Sort Zusammenfassung

In der folgenden Übersicht findest Du das bisher Gelernte auf einem Blick:

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 func