|
Hierbei handelt es sich um eine alternative verbesserte Variante. Die Idee ist einfach: Ein temporäres Indexfeld
mach aus jedem "out-of-place"-Verfahren ein "in-place"-Verfahren.
Eine rekursive Realisierung (Variante 2.b) ist möglich.
| Variante | 2.a (iterativ) |
|---|
| Typ | alternativ, optimiert |
|---|
| Eigenschaften | iterativ, in-place, stabil, (parallelisierbar) |
|---|
| Datenstrukturen | Felder, doppeltverkettete Listen |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit | Ω(n+k) | Θ(n+k) | Ο(n+k) |
|---|
| Interpretationen | 2n | 2n | 2n |
|---|
| Vertauschungen | 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]]++;
B[0][i]:= i;
B[1][i]:= i;
}
for i:=1 to k-1 do {
C[i]:= C[i]+C[i-1];
}
for i:=l to r do {
s:= B[0][i];
j:= C[A[s]]-1+l;
t:= B[1][j];
exchange(A[s], A[j]);
B[0][t]:= s;
B[1][s]:= t;
C[A[j]]--;
}
}
| |
Countingsort, Variante 2
|