Hierbei handelt es sich um eine Beispiel-Variante für natürliche Zahlen.
Eine rekursive Realisierung (Variante 3.b) ist möglich.
Variante | 3.a (iterativ) |
Typ | Beispiel (positiv integers) |
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:= 0 to size(A[0])*8-1 do {
countingsort(A, l, r, i);
}
}
countingsort(field A, int l, int r, int d) {
C[0]:= l;
C[1]:= r+1;
for i:= l to r do {
C[1] := C[1] - getbit(A[i], d);
}
for i:=l to r do {
B[C[getbit(A[i],d)]]:= A[i];
C[getbit(A[i],d)]++;
}
for i:=l to r do {
A[i]:= B[i];
}
}
int getbit(int i, int d) {
return ((i shr d) and $01);
}
| |
Variante | 3.a (iterativ) |
Typ | Beispiel (positiv integers) |
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:= 0 to size(A[0])-1 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[ByteArray(A[i],d)]++;
}
for i:=1 to 255 do {
C[i]:=C[i]+C[i-1];
}
for i:=l to r do {
B[C[ByteArray(A[i],d)]-1+l]:= A[i];
C[ByteArray(A[i],d)]--;
}
for i:=l to r do {
A[i]:= B[i];
}
}
Byte ByteArray(int v, int i) {
return (v shr (i*8)) and $FF;
// besser: direkter Speicherzugriff!
}
| |
Radixsort, Variante 3
|