Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


9. Quicksort



Auswählen

Eine mit dem Sortieren zusammenhängende Anwendung, bei der ein vollständiges Sortieren nicht immer erforderlich sein muß, ist das Problem der Bestimmung des Medians einer Menge von Zahlen. Dies ist eine häufig auftretende Berechnung in der Statistik und in verschiedenen anderen Anwendungen der Datenverarbeitung. Eine Vorgehensweise besteht darin, die Zahlen zu sortieren und die mittlere zu betrachten, doch es zeigt sich, daß es günstiger ist, den Zerlegungsprozeß von Quicksort zu benutzen.

Die Aufgabe der Bestimmung des Medians ist ein Spezialfall der Aufgabe des Auswählens (selection): Finde aus einer Menge von Zahlen die »k-kleinste«, d. h., diejenige, die an k-ter Stelle steht, wenn man die Zahlen der Größe nach ordnet. Da ein Algorithmus nicht garantieren kann, daß ein bestimmtes Element das k-kleinste ist, ohne die k - 1 Elemente, die kleiner sind, und die N - k Elemente, die größer sind, bestimmt zu haben, können die meisten Auswahlalgorithmen ohne allzu viele zusätzliche Berechnungen sämtliche k kleinsten Elemente einer Datei angeben.

Das Auswählen besitzt viele Anwendungen bei der Verarbeitung von Versuchs- und sonstigen Daten. Die Benutzung des Medians und anderer Ordnungsstatistiken 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 beispielsweise die zehn Prozent größten Elemente der Datei auswählen kann, besser geeignet sein als ein vollständiges Sortierverfahren.

Wir haben bereits einen Algorithmus kennengelernt, der direkt zum Auswählen angepaßt werden kann. Wenn k sehr klein ist, ist Selection Sort sehr gut geeignet und benötigt eine Zeit, die proportional zu Nk ist: Finde zuerst das kleinste Element, finde dann das zweitkleinste, indem das kleinste der restlichen Elemente bestimmt wird usw. Für etwas größere k lernen wir in Kapitel 11 Verfahren kennen, die sofort so angepaßt werden können, daß sie in einer Zeit ablaufen, die proportional zu N log k ist.

Ein interessantes Verfahren, welches für alle Werte von k gut geeignet ist und im Durchschnitt in linearer Zeit abläuft, kann mit Hilfe der in Quicksort benutzten Zerlegungsprozedur formuliert werden. Wir erinnern daran, daß die Zerlegungsmethode von Quicksort ein Feld a[1..N] umordnet und eine ganze Zahl i zurückgibt, so, daß a[1],...,a[i - 1] kleiner oder gleich, a[i + 1],...,a[N] größer oder gleich a[i] sind. Wird das k-kleinste Element in der Datei gesucht und gilt k=i, so sind wir am Ziel. Andernfalls müssen wir, wenn k < i gilt, das k-kleinste Element in der linken Teildatei suchen, und wenn k > i gilt, so müssen wir das (k - i)-kleinste Element in der rechten Teildatei suchen. Indem wir diese Überlegungen auf die Aufgabe der Bestimmung des k-kleinsten Elementes in einem Feld a[l..r] übertragen, erhalten wir unmittelbar die folgende rekursive Formulierung.

 
    procedure select(l,r,k: integer);
      var i;
      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] kleiner oder gleich a[k] sind und a[k+1],...,a[r] größer oder gleich a[k] sind.

Zum Beispiel zerlegt der Aufruf select(1,N,(N+1) div 2) das Feld bezüglich seines Medians. Für die Schlüssel unseres Sortierbeispiels benötigt dieses Programm, wie Abbildung 9.7 zeigt, nur drei rekursive Aufrufe, um den Median zu finden. Die Datei wird dabei so umgeordnet, daß der Median sich an seinem Platz befindet, mit kleineren Elementen links und größeren Elementen rechts von ihm (gleiche Elemente könnten sich auf jeder Seite befinden); sie ist jedoch nicht vollständig sortiert.

Abbildung 9.7
Abbildung 9.7 Zerlegung zum Auffinden des Median.

Da die Prozedur select stets mit nur einem Aufruf von sich selbst endet, ist sie nicht wirklich rekursiv, da kein Stapel benötigt wird, um die Rekursion zu beseitigen; wenn der rekursive Aufruf erfolgt, können wir einfach die Parameter neusetzen und zum Anfang zurückkehren, da weiter nichts zu tun bleibt. Wir können auch die einfachen Berechnungen eliminieren, in denen k vorkommt, wie in der folgenden Implementation.

    procedure select(k: integer);
      var v,t,i,j,l,r: integer;
      begin
      l:=1; r:=N;
      while r>l do
        begin
        v:=a[r]; i:=l-1; j:=r;
        repeat
          repeat i:=i+1 until a[i]>=v;
          repeat j:=j-1 until a[i]<=v;
          t:=a[i]; a[i]:=a[j]; a[j]:=t;
        until j<=i;
        a[j]:=a[i]; a[i]:=a[r]; a[r]:=t;
        if i>=k then r:=i-1;
        if i<=k then r:=i+1;
        end;
      end;

Wir benutzen die gleiche Zerlegungsprozedur wie bei Quicksort und können diese wie bei Quicksort leicht abändern, wenn viele gleiche Schlüssel zu erwarten sind.

Abbildung 9.8 zeigt den Prozeß des Auswählens für eine größere (zufällige) Datei. Wie bei Quicksort können wir (ganz grob) so argumentieren, daß bei einer sehr großen Datei jede Zerlegung das Feld ungefähr halbieren müßte, so daß der Gesamtprozeß ungefähr N + N/2 + N/4 + N/8 + ... = 2N Vergleiche erfordern müßte. Wie bei Quicksort kommen diese Überlegungen der Wahrheit recht nahe.

Abbildung 9.8
Abbildung 9.8 Auffinden des Median.

Eigenschaft 9.2 Auswählen auf der Basis von Quicksort benötigt im durchschnittlichen Fall lineare Zeit.

Eine Analyse, die ähnlich wie die bereits für Quicksort angegebene durchgeführt wird, jedoch wesentlich komplexer ist, liefert das Ergebnis, daß die durchschnittliche Anzahl von Vergleichen ungefähr 2N + 2k ln(N/k) + 2(N - k) ln (N/(N - k)) beträgt, was für jeden zulässigen Wert von k linear ist. Für k = N/2 (Finden des Medians) erhält man hieraus ungefähr (2 + 2 ln 2)N Vergleiche. w.z.b.w.

Der ungünstigste Fall ist etwa der gleiche wie bei Quicksort: Die Benutzung dieser Methode zum Auffinden des kleinsten Elements in einer bereits sortierten Datei würde zu einer quadratischen Laufzeit führen. Man könnte ein willkürlich oder zufällig ausgewähltes zerlegendes Element benutzen, doch hierbei ist einige Vorsicht geboten: Wenn zum Beispiel das kleinste Element gesucht wird, wollen wir die Datei wahrscheinlich nicht in der Nähe der Mitte aufspalten. Es ist möglich, diese auf Quicksort beruhende Auswahlprozedur so zu modifizieren, daß ihre Laufzeit garantiert linear ist. Diese Änderungen sind zwar theoretisch von Bedeutung, jedoch äußerst komplex und für praktische Anwendungen kaum geeignet.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]