Hierbei handelt es sich um eine geringfügig verbesserte Variante. Die Idee ist die selbe, wie bei Variante 2 von Bubblesort.
Variante | 2.a (iterativ) |
Typ | optimiert |
Eigenschaften | iterativ, in-place, stabil, parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n | n²/2 | n²/2 |
Vertauschungen | 0 | n²/4 | n²/2 |
oetsort(field A, int l, int r) {
oet(A, l, r);
for i:=1 to r-l do {
if (not oet(A, l+(i mod 2), r) then {
return;
}
}
}
boolean oet(field A, int l, int r) {
flipped:= false;
for j:=l to r-1 step 2 do parallel {
if (A[j] > A[j+1]) then {
exchange(A[j], A[j+1]);
flipped:= true;
}
}
return flipped;
}
| |
Variante | 2.b (rekursiv) |
Typ | optimiert |
Eigenschaften | rekursiv, in-place, stabil, schlecht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n | n²/2 | n²/2 |
Vertauschungen | 0 | n²/4 | n²/2 |
oetsort(field A, int l, int r) {
oet(A, l, r);
oetsort(A, l, r, r-l);
}
boolean oetsort(field A, int l, int r, int k) {
if (k >= 1) then {
if oetsort(A, l, r, k-1) then {
return oet(A, l+(k mod 2), r);
} else {
return false;
}
} else {
return true;
}
}
oet(field A, int l, int r) {
if (l < r) then {
do parallel {
flipped:= oet(A, l+2, r);
} and {
if (A[l] > A[l+1]) then {
exchange(A[l], A[l+1]);
flipped:= true;
}
}
return flipped;
} else {
return false;
}
}
| |
Oetsort, Variante 2
|