SelectSearch, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

Es ist zu empfehlen, die Suche des i. größten Elementes mit der des i. kleinsten Elementes zu verbinden und die günstigere von beiden auszuwählen.

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

Variante 1.a (iterativ)
Typ standard
Eigenschaften iterativ, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(i*n) Θ(i*n) Ο(i*n)
Vergleiche i*(n-i/2) i*(n-i/2) i*(n-i/2)

int selectsearch(field A, int l, int r, int i) {
  for k:=r downto r-i+1 do {
    q:= l;
    for j:=l+1 to k do {
      if (A[j] > A[q]) then {
        q:= j;
      }
    }
    exchange(A[q], A[k]);
  }
  return r-i+1;
}