Bitonicsort, Variante 1 (Original, depth first) |
---|
Hierbei handelt es sich um die Original-Variante. Sie liefert das typische Bild eines "depth first"-Algorithmus.
Für dieses Verfahren gibt es keine vollständig iterative Realisierung.
Variante | 1.a (halbrekursiv) |
Typ | standard |
Eigenschaften | halbrekursiv, in-place, instabil, parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(logn) | Θ(logn) | Ο(logn) |
Laufzeit (p) | Ω((logn)²) | Θ((logn)²) | Ο((logn)²) |
Laufzeit | Ω(n(logn)²) | Θ(n(logn)²) | Ο(n(logn)²) |
Vergleiche | n(logn)²/4 | n(logn)²/4 | n(logn)²/4 |
Vertauschungen | 0 | n(logn)²/8 | n(logn)²/4 |
bitonicsort(field A, int l, int r) {
bitonicsort(A, l, r, true);
}
bitonicsort(field A, int l, int r, bool asc) {
if (l < r) then {
q:= (l+r) div 2;
do parallel {
bitonicsort(A, l, q, true);
bitonicsort(A, q+1, r, false);
}
bitonicmerge(A, l, r, asc);
}
}
bitonicmerge(field A, int l, int r, bool asc) {
if (l < r) then {
q:= (l+r) div 2;
k:= q-l+1;
for i:= l to q do parallel {
if ((A[i] > A[i+k]) = asc) then {
exchange(A[i],A[i+k]);
}
}
do parallel {
bitonicmerge(A, l, q, asc);
bitonicmerge(A, q+1, r, asc);
}
}
}
| |
Variante | 1.b (rekursiv) |
Typ | standard |
Eigenschaften | rekursiv, in-place, instabil, parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(logn) | Θ(logn) | Ο(logn) |
Laufzeit (p) | Ω((logn)²) | Θ((logn)²) | Ο((logn)²) |
Laufzeit | Ω(n(logn)²) | Θ(n(logn)²) | Ο(n(logn)²) |
Vergleiche | n(logn)²/4 | n(logn)²/4 | n(logn)²/4 |
Vertauschungen | ??? | n(logn)²/8 | n(logn)²/4 |
bitonicsort(field A, int l, int r) {
bitonicsort(A, l, r, true);
}
bitonicsort(field A, int l, int r, bool asc) {
if (l < r) then {
q:= (l+r) div 2;
do parallel {
bitonicsort(A, l, q, true);
bitonicsort(A, q+1, r, false);
}
bitonicmerge(A, l, r, asc);
}
}
bitonicmerge(field A, int l, int r, bool dir) {
if (l < r) then {
q:= (l+r) div 2;
comp(A, l, q, q-l+1, asc);
do parallel {
bitonicmerge(A, l, q, asc);
bitonicmerge(A, q+1, r, asc);
}
}
}
comp(field A, int l, int r, int k, bool asc) {
if (l < r) then {
q:= (l+r) div 2;
do parallel {
comp(A, l , q, k, asc);
comp(A, q+1, r, k, asc);
}
} else {
if ((A[l] > A[l+k]) = asc) then {
exchange(A[l],A[l+k]);
}
}
}
| |
Bitonicsort, Variante 1
| |