Shakersort, Variante 3 (schnelle Min-Max-Suche)

Hierbei handelt es sich um stark verbesserte Variante. Die Idee ist einfach: Es soll "gleichzeitig" das größte und kleinste Element gesucht werden. Das geht schneller.

Analog zu Bubblesort (Variante 2 und 4) sind auch hier einige zusätzliche Optimierungen möglich. Eine rekrusive Lösung (Variante 3.b) wäre ebenfalls realisierbar.

Variante 3.a (iterativ)
Typ optimiert
Eigenschaften iterativ, in-place, instabil, parallelisierbar
Datenstrukturen Felder
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit (p) Ω(n²) Θ(n²) Ο(n²)
Laufzeit Ω(n²) Θ(n²) Ο(n²)
Vergleiche 3/8*n² 3/8*n² 3/8*n²
Vertauschungen 0 1/8*n² 3/8*n²

shakersort(field A, int l, int r) {
  while (l < r) do {
    q:= split(A, l, r);
    do parallel {    
      { shaker2(A, l  , q);l++; }
      { shaker1(A, q+1, r);r--; }
    }
  }
}

int split(field A, int l, int r) {
  q:= (r-l+1)/2;
  for i:= l+q to r do parallel {
    if (A[i-q] > A[i]) then {
      exchange(A[i-q], A[i]);
    }
  }
  return r-q;
}

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]);
    }
  }
}


Shakersort, Variante 3