Selectsort, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

Variante 1.a (iterativ)
Typ standard
Eigenschaften iterativ, in-place, instabil, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(n²) Θ(n²) Ο(n²)
Vergleiche n²/2 n²/2 n²/2
Vertauschungen 0 n n

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

Variante 1.b (rekursiv)
Typ standard
Eigenschaften rekursiv, in-place, stabil, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(n²) Θ(n²) Ο(n²)
Vergleiche n²/2 n²/2 n²/2
Vertauschungen 0 n n

selectsort(field A, int l, int r) {
  if (l < r) then {
    q:= max(A, l, l+1, r);
    exchange(A[q], A[r]);
    selectsort(A, l, r-1);
  }
}

int max(field A, int q, int l, int r) {
  if (l <= r) then {
    if (A[l] > A[q]) then {
      return max(A, l, l+1, r);
    } else {
      return max(A, q, l+1, r);
    }
  } else {
    return q;
  }
}


Selectsort, Variante 1