Hierbei handelt es sich um geringfügig verbesserte Variante. Die Idee ist einfach: In einigen Fällen ist shaker1 und in anderen shaker2
günstiger. Daher sollte auch die günstigere Richtung bevorzugt werden. Außerdem erfolgt die Realisierung der
Optimierungsidee von Variante 2 aus Bubblesort implizit.
Analog zu Bubblesort (Variante 3 und 4) sind auch hier einige zusätzliche Optimierungen möglich.
Eine rekrusive Lösung (Variante 2.b) wäre ebenfalls realisierbar.
Variante | 2.a (iterativ) |
Typ | optimiert |
Eigenschaften | iterativ, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | Felder, doppeltverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n | 3/8*n² | n²/2 |
Vertauschungen | 0 | n²/4 | n²/2 |
shakersort(field A, int l, int r) {
s1:= r-l;
s2:= r-l;
while ((s1 <> 0) and (s2 <> 0)) do {
if (s1 > s2) then {
s1:= shaker1(A, l, r);
r--;
} else {
s2:= shaker2(A, l, r);
l++;
}
}
}
int shaker1(field A, int l, int r) {
c:= 0;
for j:=l to r-1 do {
if (A[j] > A[j+1]) then {
exchange(A[j], A[j+1]);
c++;
}
}
return c;
}
int shaker2(field A, int l, int r) {
c:= 0;
for j:=r-1 downto l do {
if (A[j] > A[j+1]) then {
exchange(A[j], A[j+1]);
c++;
}
}
return c;
}
| |
Shakersort, Variante 2
|