StudySmarter: Besser Lernen
4.5 • +22k Bewertungen
Mehr als 22 Millionen Downloads
Kostenlos
|
|
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.

Mockup Schule Mockup Schule

Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.

Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

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:

528497236258321

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.

528497236258321
0123456789
321235649728
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.

321235649728258

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.

32123050649728258
0123456789
05321258497
0623
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.

05063212328258497

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.

005006321023028258497
0123456789
005258321497
006
023
028

3. Sammelphase

Anschließend sammelst Du die Elemente wie gehabt wieder ein und schreibst sie in ein neues Array.

005006023028258321497

Fertig ist Dein mit Radix Sort sortiertes Array. Das Endergebnis kannst Du jetzt noch ohne die eingefügten Nullen schreiben.

562328258321497

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:

528497236258321

Um das Array sortieren zu können, würdest Du zunächst an den entsprechenden Stellen Nullen ergänzen:

005028497023006258321

Würdest Du das jetzt sortieren wie bei der LSD Variante, bekommst Du nach den Sammelphasen folgende Ergebnisse:

005028023006258321497
005006028023321258497
321023005006028258497

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:

0123456789
005258321497
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.

0123456789
0528
0623

Da die Buckets 0 und 2 immer noch mehr als ein Element enthalten, müssen diese erneut partitioniert werden.

0123456789
56
0123456789
2328

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:

0123456789
005023321497
006028
258

Anschließend folgt die Sammelphase der Hunderterstelle, wodurch Du wiederum das fertig sortierte Array erhältst:

562328258321497

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-CaseAverage-CaseWorst-CasePlatz-komplexitätStabiles Verfahrenvergleichs-basiertIn-Place / out-of-placeParallelisier-barkeititerativ/rekursiv

O(k • (b + n))

O(k • (b + n))

O(k • (b + n))

O(b + n)Meistens stabilNeinBeides möglichMöglichBeides

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 func

Radix 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

  1. Happycoders.eu: Radix Sort – Algorithmus, Quellcode, Zeitkomplexität. (18.11.2022)
  2. Codingeek.com: Radix Sort – Explanation, Pseudocode and Implementation. (18.11.2022)

Häufig gestellte Fragen zum Thema Radix Sort

Beim Radix Sort werden abwechselnd Partitionierungsphasen und Sammelphasen durchgeführt, bis eine Datenmenge vollständig sortiert ist. In der Partitionierungsphase werden die Daten in Buckets einsortiert, in der Sammelphase werden die Elemente wieder aus den Buckets geholt und in eine neue Liste geschrieben.

Radix Sort ist in der Regel ein stabiles Sortierverfahren. Ein Ausnahmefall ist rekursives MSD Radix Sort, das nicht stabil ist. 

Radix Sort ist ein linearer, nicht vergleichsbasierter Sortieralgorithmus, der Datenmengen in mehreren Phasen partitioniert, vorsortiert und wieder einsammelt, bis eine sortierte Liste entsteht. 

Teste dein Wissen mit Multiple-Choice-Karteikarten

Auf welchen zwei Sortierverfahren baut Radix Sort auf?

Wahr oder falschNach jeder Sammelphase sind die vorher angelegten Buckets wieder leer.

Wahr oder falsch Radix Sort ist ein stabiles Sortierverfahren

Weiter

Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

  • Karteikarten & Quizze
  • KI-Lernassistent
  • Lernplaner
  • Probeklausuren
  • Intelligente Notizen
Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App! Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Melde dich an für Notizen & Bearbeitung. 100% for free.

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration

Entdecke Lernmaterial in der StudySmarter-App