Hierbei handelt es sich um das Grundgerüst. Das Prinzip wird im Folgenden an der Standardvariante von Bubblesort demonstriert.
Die best-case-Laufzeiten betreffen nicht dieses Beispiel, sondern den Idealfall (Verwendung der optimalsten Algorithmen).
Die Split-Operation wird hier implizit realisiert, da nur Nachbarverschmelzungen stattfinden. Im Speicher muß maximal ein Feld der Größe "2m" gehalten werden!
Eine rekursive Realisierung (Variante 1.b) ist möglich.
Variante | 1.a (iterativ) |
Typ | standard, Beispiel |
Eigenschaften | iterativ, in-place, stabil, parallelisierbar |
Datenstrukturen | Felder, Listen |
Speicher | Ω(m) | Θ(m) | Ο(m) |
Laufzeit (p) | Ω(mlog(n²/m)) | Θ(2n-2m-n/m) | Ο(2n-2m-n/m) |
Laufzeit | Ω(nlog(n²/m)) | Θ(nm/2+n²/m) | Ο(nm/2+n²/m) |
Vergleiche | nlog(n²/m) | nm/2+n²/m | nm/2+n²/m |
Vertauschungen | 0 | nm/4+n²/m/2 | nm/2+n²/m |
Hinweis |
Die Feldgröße n (r-l+1) muß durch m teilbar sein.
|
mssort(field A, int l, int r, int m) {
for i:= l to r-m+1 step m do parallel {
sort1(A, i, i+m-1);
}
sort2(A, l, r, m);
}
sort1(field A, int l, int r) {
// Ein beliebiges Sortierverfahren
for i:=r downto l+1 do {
for j:=l to i-1 do {
if (A[j] > A[j+1]) then {
exchange(A[j], A[j+1]);
}
}
}
}
sort2(field A, int l, int r, int m) {
// Ein beliebiges modifiziertes Sortierverfahren
for i:=r-m+1 downto l+m step m do {
for j:=l to i-m step m do {
merge(A, j, j+m-1, j+2*m-1);
}
}
}
merge(field A, int l, int q, int r) {
// Eine beliebige Merge-Operation
// Siehe Mergesort, BTMsort, Bitonicsort, ...
}
| |
MSsort, Variante 1
|