Hierbei handelt es sich um die Original-Variante.
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 sind in der Regel völlig unterschiedlich!
Variante | 1.a (iterativ) |
Typ | standard |
Eigenschaften | iterativ, out-of-place, stabil, (parallelisierbar) |
Datenstrukturen | Felder |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n+k) | Θ(n+k) | Ο(n+k) |
Interpretationen | 2n | 2n | 2n |
Kopierungen | 2n | 2n | 2n |
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]]++;
}
for i:=1 to k-1 do {
C[i]:=C[i]+C[i-1];
}
for i:=l to r do {
B[C[A[i]]-1+l]:= A[i];
C[A[i]]--;
}
for i:=l to r do {
A[i]:= B[i];
}
}
| |
Countingsort, Variante 1
|