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.

Radix Sort Radix Sort

Erstelle Lernmaterialien über Radix Sort mit unserer kostenlosen Lern-App!

  • Sofortiger Zugriff auf Millionen von Lernmaterialien
  • Karteikarten, Notizen, Übungsprüfungen und mehr
  • Alles, was du brauchst, um bei deinen Prüfungen zu glänzen
Kostenlos anmelden
Inhaltsverzeichnis
Inhaltsangabe

    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

    Wie funktioniert 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.

    Ist Radix Sort stabil? 

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

    Was ist Radix Sort? 

    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

    Entdecken Lernmaterialien mit der kostenlosen StudySmarter App

    Kostenlos anmelden
    1
    Über StudySmarter

    StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.

    Erfahre mehr
    StudySmarter Redaktionsteam

    Team Radix Sort Lehrer

    • 12 Minuten Lesezeit
    • Geprüft vom StudySmarter Redaktionsteam
    Erklärung speichern

    Lerne jederzeit. Lerne überall. Auf allen Geräten.

    Kostenfrei loslegen

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

    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!