Hierbei handelt es sich um eine Beispiel-Variante für Strings.
Eine rekursive Realisierung (Variante 2.b) ist möglich.
Variante | 2.a (iterativ) |
Typ | Beispiel (strings, lexikografische Ordnung) |
Eigenschaften | iterativ, out-of-place, stabil, nicht parallelisierbar |
Datenstrukturen | Felder |
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) {
for i:= maxlength(A)-1 downto 0 do {
countingsort(A, l, r, i);
}
}
countingsort(field A, int l, int r, int d) {
for i:= 0 to 255 do {
C[i]:= 0;
}
for i:= l to r do {
C[getid(A[i],d)]++;
}
for i:=1 to 255 do {
C[i]:=C[i]+C[i-1];
}
for i:=l to r do {
B[C[getid(A[i],d)]-1+l]:= A[i];
C[getid(A[i],d)]--;
}
for i:=l to r do {
A[i]:= B[i];
}
}
int getid(String S, int i) {
if (S.length > i) then {
return CharToInt(S[i]);
} else {
return 0;
}
}
int maxlength(field A) {
l:= 0;
for i:= l to r do {
if (A[i].length > l) then {
l:= A[i].length;
}
}
return l;
}
| |
Radixsort, Variante 2
|