Oetsort, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

Variante 1.a (iterativ)
Typ standard
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²/2 n²/2 n²/2
Vertauschungen 0 n²/4 n²/2

oetsort(field A, int l, int r) {
  for i:=l to r do {
    for j:="l+(i mod 2)" to "r-1" step 2 do parallel {
      if (A[j] > A[j+1]) then {
        exchange(A[j], A[j+1]);
      }
    }
  }
}

Variante 1.b (rekursiv)
Typ standard
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²/2 n²/2 n²/2
Vertauschungen 0 n²/4 n²/2

oetsort(field A, int l, int r) {
  oetsort(A, l, r, r);
}

oetsort(field A, int l, int r, int k) {
  if (k >= l) then {
    oetsort(A, l, r, k-1);
    oet(A, l+(k mod 2), r);
  }
}

oet(field A, int l, int r) {
  if (l < r) then {
    do parallel {
      oet(A, l+2, r);
    } and {
      if (A[l] > A[l+1]) then {
        exchange(A[l], A[l+1]);
      }
    }
  }
}


Oetsort, Variante 1