Shakersort, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

Analog zu Bubblesort (Variante 2, 3 und 4) sind auch hier einige zusätzliche Optimierungen möglich.

Variante 1.a (iterativ)
Typ standard
Eigenschaften iterativ, in-place, stabil, nicht parallelisierbar
Datenstrukturen Felder, doppeltverkettete Listen
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(n²) Θ(n²) Ο(n²)
Vergleiche n²/2 n²/2 n²/2
Vertauschungen 0 n²/4 n²/2

shakersort(field A, int l, int r) {
  while (l < r) do {
    shaker1(A, l, r);r--;
    shaker2(A, l, r);l++;
  }
}

shaker1(field A, int l, int r) {
  for j:=l to r-1 do {
    if (A[j] > A[j+1]) then {
      exchange(A[j], A[j+1]);
    }
  }
}

shaker2(field A, int l, int r) {
  for j:=r-1 downto l do {
    if (A[j] > A[j+1]) then {
      exchange(A[j], A[j+1]);
    }
  }
}

Variante 1.b (rekursiv)
Typ standard
Eigenschaften rekursiv, in-place, stabil, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(n²) Θ(n²) Ο(n²)
Vergleiche n²/2 n²/2 n²/2
Vertauschungen 0 n²/4 n²/2

shakersort(field A, int l, int r) {
  if (l < r) do {
    shaker(A, l, r);
    shakersort(A, l+1, r-1);
  }
}

shaker(field A, int l, int r) {
  if (l < r) then {
    if (A[l] > A[l+1]) then {
      exchange(A[l], A[l+1]);
    }
    shaker(A, l+1, r);
    if (A[l] > A[l+1]) then {
      exchange(A[l], A[l+1]);
    }
  }
}


Shakersort, Variante 1