|
Hierbei handelt es sich um eine verbesserte Variante, die besonders für Listen geeignet ist. Die Idee ist einfach:
Bei Listen sind Verschiebungen billiger als Vertauschungen. Außerdem werden weniger Bewegungsopterationen benötigt und das
Verfahren ist dann nicht mehr out-of-place.
Eine rekursive Realisierung (Variante 5.b) ist möglich.
| Variante | 5.a (iterativ) |
|---|
| Typ | optimiert |
|---|
| Eigenschaften | iterativ, in-place, stabil, ??? |
|---|
| Datenstrukturen | einfachverkettete Listen (?) |
|---|
| Speicher | Ω(1) | Θ(1) | Ο(1) |
|---|
| Laufzeit | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
|---|
| Vergleiche | nlogn/2 | n(logn-1.25) | nlogn |
|---|
| Verschiebungen | 0 | nlogn/2.3 | nlogn/2 |
|---|
mergesort(field A, int l, int r) {
...
}
merge(field A, int l, int r, bool asc) {
if asc then {
c:= +1;
} else {
swap(l, r);
c:= -1;
}
while (l <> r) do {
if (A[l] > A[r]) then {
move(A[r], A[l]);
}
l:= l + c;
}
}
| |
Bitonic Mergesort, Variante 2+5
Bitonic Mergesort, Variante 2+5
|