|
Hierbei handelt es sich um das Grundgerüst. Als internes Sortierverfahren kann ein beliebiges (optimales algemeines) Sortierverfahren (kann auch wieder Bucketsort sein) verwendet werden.
Eine rekursive Realisierung (Variante 1.b) ist möglich.
| Variante | 1.a (iterativ) |
|---|
| Typ | standard |
|---|
| Eigenschaften | iterativ, out-of-place, ???, parallelisierbar |
|---|
| Datenstrukturen | Felder, einfachverkettete Listen |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit (p) | Ω(n) | Θ(nlog(n/k)/k) | Ο(nlogn) |
|---|
| Laufzeit | Ω(n) | Θ(nlog(n/k)) | Ο(nlogn) |
|---|
| Interpretationen | n | n | n |
|---|
| Vergleiche | n | nlog(n/k) | nlogn |
|---|
| Kopierungen | 2n | 2n | 2n |
|---|
| Vertauschungen | 0 | n | n |
|---|
bucketsort(field A, int l, int r, int k) {
for b:= 0 to k-1 do parallel {
B[b].clear();
}
for i:= l to r do {
B[RoundUp(k*(A[i]-a)/(b-a))-1].add(A[i]);
}
for b:= 0 to k-1 do parallel {
// Wende auf B[b] ein beliebiges
// Sortierverfahren an.
B[b].sort();
}
i:= l;
for b:= 0 to k-1 do {
for j:= 0 to B[b].length()-1 do {
A[i]:= B[b][j];
i++;
}
}
}
| |
Bucketsort, Variante 1
|