Das Auswählen besitzt viele Anwendungen bei der Verarbeitung von Versuchs- und sonstigen Daten. Die Benutzung des Medians zur Aufteilung einer Datei in kleinere Gruppen ist sehr verbreitet. Oft soll nur ein kleiner Teil einer umfangreichen Datei für die weitere Verarbeitung aufbewahrt werden. In solchen Fällen kann ein Programm, das z.B. die 10% größten Elemente der Datei auswählen kann, besser geeignet sein als ein vollständiges Sortierverfahren.

Ein interessantes Verfahren, welches für alle Werte von k gut geeignet ist, kann mit Hilfe der in Quicksort benutzten Zerlegungsprozedur formuliert werden. Die Zerlegungsmethode ordnet ein Feld a[1..N] um und gibt ganze Zahl i zurück, so daß a[1],...,a[i-1] <= a[i], a[i+1],..,a[N]>=a[i] sind. Wird das kleinste Element in der Datei gesucht und gilt k=i,so ist der Ziel erreicht. Andersfalls, wenn k<i ist, soll das k-kleinste Element in der linken Teildatei gesucht, und wenn k>i ist, in der rechten Teildatei gesucht werden.

Rekursive Formulierung:

procedure select (l,r,k : integer);
  var i: integer;
  begin
  if r > l then
         begin
           i := partition(l,r);
          if i>l+k-1 then select(l,i-1,k);
          if i<l+k-1 then select(i+1,r,k-i);
          end
  end;

Diese Prozedur ordnet das Feld so um, daß a[l],...,a[k-1]<=a[k] und a[k+1],...,a[r]>=a[k] sind.

Zurück