Selectsort, Variante 3 (Vergleichsreduzierung)

Hierbei handelt es sich um eine verbesserte Variante. Aufgrund dieser Verbesserung ist eine iterative Realisierung nichtmehr möglich. Die Idee ist analog zu Variante 3 von Bubblesort.

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

selectsort(field A, int l, int r) {
  while (l < r) do {
    r:= select(A, l, r);
  }
}

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

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

selectsort(field A, int l, int r) {
  if (l < r) then {
    r:= select(A, l, l+1, r);
    selectsort(A, l, r);
  }
}

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


Selectsort, Variante 3