Hierbei handelt es sich um eine alternative, verbesserte Variante. Die Idee ist einfach: Ein temporäres Indexfeld
(bidirektional) spart Speicherplatz, Kenntnisse über die Elemente und reduziert das Risiko eines Datenverlustes (da in-place).
Eine rekursive Realisierung (Variante 6.b) ist möglich.
Variante | 6.a (iterativ) |
Typ | optimiert |
Eigenschaften | iterativ, in-place, stabil, ??? |
Datenstrukturen | Felder |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
Vergleiche | nlogn | nlogn | nlogn |
Verschiebungen | 0 | nlogn | nlogn |
mergesort(field A, int l, int r) {
...
}
merge(field A, int l, int r, bool asc) {
for i:= l to r do parallel {
B[0][i]:= i;
B[1][i]:= i;
}
if asc then {
k:= l;
c:= +1;
} else {
k:= r;
c:= -1;
}
i:= l;
j:= r;
while (i < j) do {
s:= B[0][i];
t:= B[0][j];
if (A[s] < A[t]) or (asc and (A[s] = A[t])) then {
i++;
} else {
s:= t;
j--;
}
exchange(A[k], A[s]);
t:= B[1][k];
B[0][t]:= s;
B[1][s]:= t;
k:= k + c;
}
}
| |
Bitonic Mergesort, Variante 1+6
Bitonic Mergesort, Variante 2+6
|