Oetsort, Variante 2 (vorzeitiger Abbruch)

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