Robert Sedgewick: Algorithmen

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


9. Quicksort



Beseitigung der Rekursion

Wie in Kapitel 5 können wir auch im Quicksort-Programm die Rekursion beseitigen, indem wir einen expliziten Stapel verwenden, den wir uns derart vorstellen, daß er die »zu erledigende Arbeit« in Form von zu sortierenden Teildateien enthält. Jedesmal, wenn wir eine Teildatei zum Bearbeiten benötigen, entnehmen wir sie dem Stapel. Wenn wir zerlegen, erzeugen wir zwei zu bearbeitende Teildateien, die im Stapel abgelegt werden können. Dies führt zu der folgenden nichtrekursiven Implementation von Quicksort:

    procedure quicksort;
      var t,i,l,r: integer;
      begin
      l:=1; r:=N; stackinit; 
      push(l); push(r);
      repeat
        if r>l then
          begin
          i:=partition(l,r);
          if (i-l)>(r-i)
            then begin push(l); push(i-1); l:=i+1 end
            else begin push(i+1); push(r); r:=i-1 end;
          end
        else
          begin r:=pop; l:=pop end;
      until stackempty;
      end;

Dieses Programm unterscheidet sich in zweierlei Hinsicht wesentlich von der obigen Beschreibung. Zum einen werden die zwei Teildateien nicht in irgendeiner willkürlichen Reihenfolge im Stapel abgelegt, sondern ihre Größen werden geprüft, und die größere von beiden wird zuerst im Stapel abgelegt. Zum anderen wird die kleinere der beiden Teildateien überhaupt nicht im Stapel abgelegt; die Werte der Parameter werden einfach geändert. Das ist die Methode der »End-Rekursionsbeseitigung«, die in Kapitel 5 betrachtet wurde. Für Quicksort führt die Kombination der End-Rekursionsbeseitigung mit der Politik der Bearbeitung der kleineren von den beiden Teildateien zunächst dazu, daß gewährleistet wird, daß der Stapel für nur ungefähr lg N Eintragungen Platz haben muß, da es sich bei jeder weiteren Ablage nach der ersten im Stapel um eine Teildatei handeln muß, die weniger als halb so groß ist wie die zuvor abgelegte.

Dies steht im krassen Gegensatz zum Umfang des Stapels im ungünstigsten Fall bei der rekursiven Implementation, der die Größe von N erreichen kann (zum Beispiel wenn die Datei schon sortiert ist). Das ist eine subtile, aber reale Schwierigkeit bei einer rekursiven Implementation von Quicksort: Es ist stets ein zugrundeliegender Stapel vorhanden, und ein entarteter Fall bei einer umfangreichen Datei könnte dazu führen, daß das Programm wegen Speicherplatzmangels abbricht; ein solches Verhalten ist für eine Bibliotheks-Routine für das Sortieren offensichtlich nicht wünschenswert. Weiter unten betrachten wir Methoden, wie man entartete Fälle äußerst unwahrscheinlich machen kann. Es ist jedoch kompliziert, dieses Problem bei einer rekursiven Implementation ohne End-Rekursionsbeseitigung zu vermeiden. (Selbst das Wechseln der Reihenfolge, in der Teildateien bearbeitet werden, nützt nichts.)

Die einfache Verwendung eines expliziten Stapels im obigen Programm führt zu einem weit effizienteren Programm als die direkte rekursive Implementation, doch es gibt immer noch Ballast, der entfernt werden könnte. Das Problem besteht darin, daß, wenn beide Teildateien nur ein Element besitzen, eine Datei mit r=l im Stapel abgelegt wird, nur um sofort wieder entnommen und entfernt zu werden. Es ist sehr einfach, das Programm so abzuändern, daß es keine solchen Dateien im Stapel ablegt. Diese Änderung ist sogar noch effizienter, wenn die weiter unten beschriebene nächste Verbesserung mit einbezogen wird. Sie bewirkt, daß auch kleine Teildateien ignoriert werden, so daß die Wahrscheinlichkeit, daß beide Teildateien zu ignorieren sind, zunimmt.

Für jede Datei verarbeitet die nichtrekursive Methode die gleichen Teildateien wie die rekursive Methode, allerdings in anderer Reihenfolge. Die Abbildung 9.4 zeigt die Zerlegungen für unser Beispiel: Die ersten drei Zerlegungen sind die gleichen, doch dann zerlegt die nichtrekursive Methode zuerst die rechte Teildatei von R, da sie kleiner ist als die linke usw.

Abbildung 9.4
Abbildung 9.4 Teildateien bei Quicksort (nichtrekursiv).

Wenn wir die Abbildungen 9.3 und 9.4 »verdichten« und jedes zerlegende Element mit dem Element verbinden, das in seinen beiden Teildateien als zerlegendes benutzt wird, erhalten wir die statische Darstellung des Zerlegungsprozesses, die Abbildung 9.5 zeigt. In diesem binären Baum wird jede Teildatei durch ihr zerlegendes Element repräsentiert (oder durch sich selbst, wenn sie die Größe 1 hat), und die Teilbäume jedes Knotens sind die Bäume, die die Teildateien nach der Zerlegung repräsentieren. Die äußeren Knoten im Baum entsprechen leeren Teildateien. (Der Klarheit wegen sind das zweite A, das I, das P und das T in der Weise dargestellt, daß sie zwei leere Teildateien besitzen; wie oben erläutert wurde, behandeln die Varianten des Algorithmus leere Teildateien auf unterschiedliche Art.) Die rekursive Implementation von Quicksort entspricht dem Besuchen der Knoten dieses Baumes in einer Preorder-Traversierung; die nichtrekursive Implementation entspricht einer Regel »besuche den kleineren Teilbaum zuerst«. In Kapitel 14 werden wir sehen, wie dieser Baum zu einer direkten Beziehung zwischen Quicksort und einem grundlegenden Suchverfahren führt.

Abbildung 9.5
Abbildung 9.5 Baumdiagramm des Zerlegungsprozesses bei Quicksort.


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