Shakersort, Variante 2 (Richtungsauswahl)

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