QuickSearch, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

Die bei Quicksort erwähnten Optimierungen sind natürlich auch hier anwendbar.

Variante 1.a (iterativ)
Typ standard
Eigenschaften iterativ, nicht parallelisierbar
Datenstrukturen Felder, doppeltverkettete Listen
Speicher Ω(1) Θ(logn) Ο(n)
Laufzeit Ω(n) Θ(n) Ο(n²)
Vergleiche n 2n n²/2

int quicksearch(field A, int l, int r, int i) {
  while (l < r) do {
    q:= partition(A, l, r);
    if (r-q >= i) then {
      l:= q+1;
    } else {
      r:= q;
      i:= i-r+q;
    }
  }
  if (i = 1) then {
    return l;
  } else {
    return -1;
  }
}

int partition(field A, int l, int r) {
  x:= A[(l+r) div 2];
  i:= l-1;
  j:= r+1;
  for ever do {
    do { j--; } while (A[j] > x);
    do { i++; } while (A[i] < x);
    if (i < j) then {
      exchange(A[i], A[j]);
    } else {
      return j;
    }
  }
}

Variante 1.b (rekursiv)
Typ standard
Eigenschaften rekursiv, nicht parallelisierbar
Datenstrukturen Felder, doppeltverkettete Listen
Speicher Ω(1) Θ(logn) Ο(n)
Laufzeit Ω(n) Θ(n) Ο(n²)
Vergleiche n 2n n²/2

int quicksearch(field A, int l, int r, int i) {
  if (l < r) then {
    q:= partition(A, l, r);
    if (r-q >= i) then {
      return quicksearch(A, q+1, r, i);
    } else {
      return quicksearch(A, l, q, i-r+q);
    }
  } else if (i = 1) then {
    return l;
  } else {
    return -1;
  }
}

int partition(field A, int l, int r) {
  x:= A[(l+r) div 2];
  i:= l-1;
  j:= r+1;
  partition1(A, x, i, j);
}

int partition1(field A, ele x, int i, int j) {
  j--;
  if (A[j] > x) then {
    return partition1(A, x, i, j);
  } else {
    return partition2(A, x, i, j);
  }
}

int partition2(field A, ele x, int i, int j) {
  i++;
  if (A[i] < x) then {
    return partition2(A, x, i, j);
  } else {
    if (i < j) then {
      exchange(A[i], A[j]);
      partition1(A, x, i, j);
    } else {
      return j;
    }
  }
}