MMSearch, Variante 2 (echtes Original)

Hierbei handelt es sich um die Original-Variante.

Eine rekursive Realisierung (Variante 2.b) ist möglich.

Variante 2.a (iterativ)
Typ standard, alternativ
Eigenschaften iterativ, parallelisierbar
Datenstrukturen Felder
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(n) Θ(n) Ο(n)
Vergleiche 3/2n 3/2n 3/2n
Hinweis Die Feldgröße (n) muß gerade sein!

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

int selectmin(field A, int l, int r) {
  q:= l;
  for j:=l+2 to r step 2 do {
    if (A[j] < A[q]) then {
      q:= j;
    }
  }
  return q;
}

int selectmax(field A, int l, int r) {
  q:= l;
  for j:=l+2 to r step 2 do {
    if (A[j] > A[q]) then {
      q:= j;
    }
  }
  return q;
}