|
Hierbei handelt es sich um das Grundgerüst aller Varianten. Als internes Sortierverfahren wird in der Regel Countingsort (Variante 1) verwendet.
Eine rekursive Realisierung (Variante 1.b) ist möglich.
Beim Vergleich spezieller mit allgemeinen Sortierverfahren ist größte Vorsicht geboten. Die Vergleiche und damit deren Aufwand ist in der Regel völlig unterschiedlich!
In der Regel sind die Vergleiche bei allgemeinen Sortieralgorithmen d-mal komplexer (Laufzeit) als hier.
| Variante | 1.a (iterativ) |
|---|
| Typ | standard |
|---|
| Eigenschaften | iterativ, in-place, stabil, nicht parallelisierbar |
|---|
| Datenstrukturen | Felder, einfachverkettete Listen |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit | Ω(dn) | Θ(dn) | Ο(dn) |
|---|
| Interpretationen | 2d*n | 2d*n | 2d*n |
|---|
| Kopierungen | 2d*n | 2d*n | 2d*n |
|---|
radixsort(field A, int l, int r, int d) {
for i:= 0 to d-1 do {
sort(A, l, r, i);
// Wende auf A ein stabiles
// Sortierverfahren für die
// i-te Ziffer an.
}
}
| |
Radixsort, Variante 1
|