Hierbei handelt es sich um eine alternative verbesserte Variante. Die Idee ist einfach: Eine eineindeutige Abbildung
erspart Zeit und Speicherplatz.
Eine rekursive Realisierung (Variante 3.b) ist möglich.
Variante | 3.a (iterativ) |
Typ | alternativ, optimiert |
Eigenschaften | iterativ, in-place, stabil, (parallelisierbar) |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n+k) | Θ(n+k) | Ο(n+k) |
Interpretationen | n | n | n |
Generierung | n | n | n |
countingsort(field A, int l, int r, int k) {
for i:= 0 to k-1 do parallel {
C[i]:= 0;
}
for i:= l to r do {
C[A[i]]++;
}
c:=0;
for i:=0 to k-1 do {
for j:=1 to C[i] do {
A[l+c]:= i;
c++;
}
}
}
| |
Countingsort, Variante 3
|