StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
Americas
Europe
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,…
Entdecke über 200 Millionen kostenlose Materialien in unserer App
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenStell 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.
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 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.
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.
Der Radixsort Algorithmus lässt sich am besten mit einem Beispiel erklären. Gegeben ist folgendes Array:
5 | 28 | 497 | 23 | 6 | 258 | 321 |
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.
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.
5 | 28 | 497 | 23 | 6 | 258 | 321 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
321 | 23 | 5 | 6 | 497 | 28 | ||||
258 |
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.
321 | 23 | 5 | 6 | 497 | 28 | 258 |
Nach einer Sammelphase sind die vorher angelegten Buckets wieder leer.
Beginne damit, Dein neues Array wieder von links nach rechts in die Buckets einzusortieren – diesmal jedoch nach ihrer Zehnerstelle.
321 | 23 | 05 | 06 | 497 | 28 | 258 |
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.
In der 2. Sammelphase sammelst Du die Zahlen wieder aus den Buckets heraus und erstellst ein neues Array.
05 | 06 | 321 | 23 | 28 | 258 | 497 |
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.
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.
005 | 006 | 321 | 023 | 028 | 258 | 497 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
005 | 258 | 321 | 497 | ||||||
006 | |||||||||
023 | |||||||||
028 |
Anschließend sammelst Du die Elemente wie gehabt wieder ein und schreibst sie in ein neues Array.
005 | 006 | 023 | 028 | 258 | 321 | 497 |
Fertig ist Dein mit Radix Sort sortiertes Array. Das Endergebnis kannst Du jetzt noch ohne die eingefügten Nullen schreiben.
5 | 6 | 23 | 28 | 258 | 321 | 497 |
Noch einmal kurz und knapp, wie gehst Du beim Radix Sort Algorithmus vor:
Vor dem Sortieren musst Du noch festlegen, nach welcher Radixsort Variante Du sortieren willst. Mehr dazu findest Du im nachfolgenden Abschnitt.
Den Radix Sort Algorithmus gibt es in zwei Varianten:
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.
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:
5 | 28 | 497 | 23 | 6 | 258 | 321 |
Um das Array sortieren zu können, würdest Du zunächst an den entsprechenden Stellen Nullen ergänzen:
005 | 028 | 497 | 023 | 006 | 258 | 321 |
Würdest Du das jetzt sortieren wie bei der LSD Variante, bekommst Du nach den Sammelphasen folgende Ergebnisse:
005 | 028 | 023 | 006 | 258 | 321 | 497 |
005 | 006 | 028 | 023 | 321 | 258 | 497 |
321 | 023 | 005 | 006 | 028 | 258 | 497 |
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.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
05 | 28 | ||||||||
06 | 23 |
Da die Buckets 0 und 2 immer noch mehr als ein Element enthalten, müssen diese erneut partitioniert werden.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
5 | 6 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
23 | 28 |
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:
5 | 6 | 23 | 28 | 258 | 321 | 497 |
Die Komplexität von Radix Sort kann in die Laufzeit (Zeitkomplexität) und den zusätzlichen Speicheraufwand (Platzkomplexität) unterschieden werden.
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 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.
In den folgenden Abschnitten werden noch weitere Begrifflichkeiten rund um Radixsort geklärt.
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 arbeitet nicht vergleichsbasiert, stattdessen werden Elemente Ziffer für Ziffer sortiert.
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.
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.
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 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
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.
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.
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.
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
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.
Wie möchtest du den Inhalt lernen?
94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmelden94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmeldenWie möchtest du den Inhalt lernen?
Kostenloser informatik Spickzettel
Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!
Sei rechtzeitig vorbereitet für deine Prüfungen.
Teste dein Wissen mit spielerischen Quizzes.
Erstelle und finde Karteikarten in Rekordzeit.
Erstelle die schönsten Notizen schneller als je zuvor.
Hab all deine Lermaterialien an einem Ort.
Lade unzählige Dokumente hoch und habe sie immer dabei.
Kenne deine Schwächen und Stärken.
Ziele Setze dir individuelle Ziele und sammle Punkte.
Nie wieder prokrastinieren mit unseren Lernerinnerungen.
Sammle Punkte und erreiche neue Levels beim Lernen.
Lass dir Karteikarten automatisch erstellen.
Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.
Melde dich an für Notizen & Bearbeitung. 100% for free.