Hierbei handelt es sich um eine alternative Variante (Teil 1). Sie liefert das typische Bild eines "breadth first"-Algorithmus.
Diese Variante kann nur angewendet werden, wenn die Feldgröße (n) eine 2er-Potenz ist. Abwandlungen für beliebige Feldgrößen sind möglich.
Eine rekursive Realisierung (Variante 2.b) ist möglich.
Diese Variante muß noch mit einer anderen Variante (ab 4) kombiniert werden.
Variante | 2.a (iterativ) |
Typ | alternativ |
Eigenschaften | iterativ, ???, stabil, parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
Vergleiche | ??? | ??? | ??? |
Vertauschungen | ??? | ??? | ??? |
mergesort(field A, int l, int r) {
for m:= 2 to r-l+1 step m do {
asc:= true;
for i:= l to r step m do parallel {
merge(A, i, i+m-1, asc);
asc:= not asc;
}
}
}
merge(field A, int l, int r, bool asc) {
...
}
| |
Bitonic Mergesort, Variante 2+5
Bitonic Mergesort, Variante 2+6
|