Radix-Sort Visualisierung:
57
24
86
05
99
42
19
Was ist der Radix-Sort-Algorithmus?
▪
Es spielt keine Rolle wo sich die Elemente im Array befinden
▪ Die Elemente werden
meist von der letzten Stelle aus „LSD“
▪
identische Elemente bleiben in ihrer ursprünglichen Reihenfolge
▪ Baut auf oder auf
JavaScript Implementierung
Ein kompakter Radix-Sort mit Bucket-Sort
function RadixSort(array) {
let maxDigit = Math.max(...array).toString().length;
for (let k = 0; k < maxDigit; k++) {
let digitBuckets = Array.from({ length: 10 }, () => []);
for (let i = 0; i < array.length; i++) {
let digit = Math.floor(Math.abs(array[i]) / Math.pow(10, k)) % 10;
digitBuckets[digit].push(array[i]);
}
array = [].concat(...digitBuckets);
}
return array;
}
Radix-Sort Demo
Durchgang 0:
---
Durchgang 1:
---
Durchgang 2:
---
Durchgang 3:
---
Stats:
| Elemente (n) | Längste Ziffer (l) | Schritte: |
|---|---|---|
| 0 | - | - |
Laufzeit
Elemente werden mal sortiert.
Es ergibt sich die Laufzeit
ist am geeignetsten für ein Array mit Elementen, die sich nicht groß in der Anzahl ihrer Ziffern unterscheiden
Fazit : Vor- und Nachteile von Radix-Sort
(➡ unabhängig von der Verteilung der Werte innerhalb des Arrays)
➡ kein Best- oder Worstcase ➡
➡ schnell bei Arrays überschaubaren Ausmaßes
- die ursprüngliche Reihenfolge identischer Elemente bleibt vorhanden
für Elemente mit vielen Ziffern
➡ zusätzlicher Speicher für Count- und Output-Array nötig
(▪ Outputlänge = n ▪ Countlänge = 10)
für viele Datentypen ist notwendig
Die Ziffernanzahl des längsten Elemnts muss vorab bekannt sein
Exkurs: Counting-Sort
Gegeben ist dieses unsortierte Array:
Ursprungs-Array:
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|
| 4 | 6 | 9 | 1 | 5 | 0 | 6 | 7 | 2 | 1 |
Erstellt ein noch leeres " und ein
2 Phasen:
CountArray:
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 2 | 1 | 0 | 1 | 1 | 2 | 1 | 0 | 1 |
= Geht Array durch, liest aus ➡ CountArray[] +1
Anschließend wird das von Vorne nach Hinten durch addiert
CountArray:
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 2 | 3 | 3 | 4 | 5 | 7 | 8 | 8 | 9 |
= Geht Array durch, liest aus
➡ List Wert von Countarray[] aus und verringet den Wert im CountArray um -1
➡ OutputArray[] = Array[]
OutputArray:
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 2 | 4 | 5 | 6 | 6 | 7 | 9 |
Die Laufzeit ist:
Hierbei werden lang die Elemente gezählt,
und dann werden lang die Elemente aus dem CountArray übertragen
Fazit : Vor- und Nachteile von Counting-Sort
bei kleinen Elementen
- die ursprüngliche Reihenfolge identischer Elemente bleibt vorhanden
bei großen Zahlen
➡ zusätzlicher Speicher für Count- und Output-Array nötig
➡ Mehr als Radix-Sort
für viele Datentypen ist notwendig
Größte Zahl muss vorab bekannt sein
Danke für eure Aufmerksamkeit!
Das war Radix-Sort mit einem kleinem Einblick in Counting-Sort
Diese Präsentation ist erreichbar auf