Robert Sedgewick: Algorithmen

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


9. Quicksort



Der grundlegende Algorithmus

Quicksort ist ein Sortierverfahren vom Typ »Teile und Herrsche«. Es beruht auf einem Zerlegen (partitioning) einer Datei in zwei Teile und dem anschließenden Sortieren der Teile unabhängig voneinander. Wie wir sehen werden, hängt die genaue Position der Zerlegung von der Datei ab, so daß der Algorithmus die folgende rekursive Struktur hat:

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

Die Parameter l und r begrenzen die Teildatei innerhalb der ursprünglichen Datei, die zu sortieren ist; der Aufruf quicksort(1,N) sortiert die gesamte Datei.

Das entscheidende Element der Methode ist die Prozedur partition, die das Feld so umordnen muß, daß die folgenden drei Bedingungen erfüllt sind:

  1. Für ein beliebiges i befindet sich das Element a[i] an seinem endgültigen Platz im Feld.
  2. Alle Elemente in a[l], ..., a[i-1] sind kleiner oder gleich a[i].
  3. Alle Elemente in a[i+1], ..., a[r] sind größer oder gleich a[i].
Dies kann einfach und leicht mittels der folgenden allgemeinen Strategie implementiert werden: Wähle zuerst willkürlich a[r] als das Element, welches in seine endgültige Position gebracht werden soll. Durchsuche dann das Feld von links beginnend, bis ein Element gefunden wird, das größer als a[r] ist, und durchsuche das Feld von rechts beginnend, bis ein Element gefunden wird, das kleiner als a[r] ist. Die beiden Elemente, bei denen das Durchsuchen unterbrochen wurde, sind offensichtlich in dem endgültig zerlegten Feld fehl am Platze, tausche sie daher aus. (Aus Gründen, die weiter unten dargelegt sind, erweist es sich in Wirklichkeit, daß es am besten ist, das Durchsuchen auch bei Elementen zu unterbrechen, die gleich a[r] sind, auch wenn dies einige unnötige Austauschoperationen zu erfordern scheint.) Wenn man in dieser Weise fortfährt, ist gewährleistet, daß alle Elemente des Felds links vom linken Zeiger kleiner und alle Elemente des Felds rechts vom rechten Zeiger größer als a[r] sind. Wenn sich die Zeiger treffen, ist der Zerlegungsprozeß nahezu beendet; alles, was zu tun bleibt, ist, a[r] mit dem am weitesten links befindlichen Element der rechten Teildatei (dem Element, auf das der linke Zeiger zeigt) zu vertauschen.

Abbildung 9.1 zeigt, wie unsere Beispieldatei aus Schlüsseln mit Hilfe dieser Methode zerlegt wird. Das am weitesten rechts befindliche Element E wird als das zerlegende Element gewählt. Zuerst wird das Durchsuchen von links bei S unterbrochen, dann das Durchsuchen von rechts bei A (wie die zweite Zeile der Tabelle zeigt), und dann werden diese beiden Elemente vertauscht. Im nächsten Schritt wird das Durchsuchen von links bei O unterbrochen, dann das Durchsuchen von rechts bei E (wie die dritte Zeile der Tabelle zeigt), dann werden diese beiden Elemente vertauscht. Danach treffen sich die Zeiger. Das Durchsuchen von links wurde bei R unterbrochen und das Durchsuchen von rechts bei E. Die richtige Operation besteht nun darin, das rechts stehende E mit dem R zu vertauschen, wodurch die zerlegte Datei entsteht, die in der letzten Zeile der Abbildung 9.1 gezeigt wird.

Abbildung 9.1
Abbildung 9.1 Zerlegen.

Natürlich ist der Zerlegungsprozeß nicht stabil, da jeder Schlüssel während jedes Austauschvorganges an einer großen Zahl von gleichen Schlüsseln (welche noch nicht einmal untersucht worden sind) vorbei bewegt werden könnte.

Abbildung 9.2
Abbildung 9.2 Zerlegen einer umfangreicheren Datei.

Abbildung 9.2 zeigt das Ergebnis der Zerlegung einer größeren Datei: Die zerlegte Datei weist kleine Elemente auf der linken und große Elemente auf der rechten Seite auf; sie beinhaltet damit wesentlich mehr »Ordnung« als die zufällige Datei. Das Sortieren wird beendet, indem die beiden Teildateien auf jeder Seite des zerlegenden Elements sortiert werden (rekursiv). Das folgende Programm stellt eine vollständige Implementation dieser Methode dar.

    procedure quicksort(l,r: integer);
      var v,t,i,j: integer;
      begin
      if r>l then
        begin
        v:=a[r]; i:=l-1; j:=r;
        repeat
          repeat i:=i+1 until a[i]>=v;
          repeat i:=i-1 until a[j]<=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;
        quicksort(l,i-1);
        quicksort(i+1,r)
        end
      end;

Bei dieser Implementation dient die Variable v zur Speicherung des aktuellen Wertes des »zerlegenden Elements« a[i], während i und j der linke bzw. rechte Zeiger des Durchsuchens sind. Ein zusätzlicher Austausch von a[i] und a[j] mit j<i erfolgt unmittelbar nachdem sich die Zeiger treffen, doch bevor das Treffen festgestellt und die äußere repeat-Schleife verlassen wird. (Dies könnte mit einer goto-Anweisung vermieden werden.) Die drei Zuweisungsbefehle, die nach dieser Schleife folgen, implementieren den Austausch von a[i] und a[j] (um das zusätzliche Austauschen rückgängig zu machen) sowie von a[i] und a[r] (um das zerlegende Element an die richtige Position zu setzen).

Wie bei Insertion Sort wird ein Marken-Schlüssel benötigt, um das Durchsuchen abzubrechen, falls das zerlegende Element zugleich auch das kleinste ist. Für den entgegengesetzten Fall, daß also das zerlegende Element zugleich das größte ist, wird in dieser Implementation kein derartiger Schlüssel benötigt, da das zerlegende Element am rechten Ende steht und dort die Suche abbricht. Wir lernen demnächst eine einfache Methode kennen, wie auf beide Marken-Schlüssel verzichtet werden kann.

Die »innere Schleife« von Quicksort beinhaltet lediglich das Inkrementieren eines Zeigers und den Vergleich eines Feldelementes mit einem festen Wert. Eben das macht Quicksort so schnell; eine einfachere innere Schleife läßt sich kaum vorstellen. Der Vorteil der Benutzung von Marken wird hierdurch gleichfalls unterstrichen, da das Hinzufügen auch nur eines überflüssigen Testes zur inneren Schleife einen spürbaren Einfluß auf die Leistungsfähigkeit hätte.

Nun werden die beiden Teildateien rekursiv sortiert, womit das Sortieren beendet wird. Abbildung 9.3 illustriert den Ablauf dieser rekursiven Aufrufe. Jede Zeile zeigt das Ergebnis der Zerlegung der dargestellten Teildatei unter Benutzung des (im Diagramm schattiert gezeichneten) zerlegenden Elementes. Falls der am Anfang des Programms durchgeführte Test r >= l anstatt r > l lauten würde, so würde jedes Element (schließlich) an seinen Platz gesetzt, indem es als zerlegendes Element benutzt würde; bei der vorliegenden Implementation werden Dateien der Größe 1 nicht zerlegt, wie aus der Abbildung 9.3 ersichtlich ist. Eine Verallgemeinerung dieser Verbesserung wird später ausführlicher erörtert.

Abbildung 9.3
Abbildung 9.3 Teildateien bei Quicksort.

Die am meisten störende Eigenschaft des obigen Programms ist, daß es für einfache Dateien sehr uneffizient ist. Wenn es zum Beispiel für eine Datei aufgerufen wird, die bereits sortiert ist, so entarten die Zerlegungen, und das Programm ruft sich selbst N mal auf, wobei bei jedem Aufruf nur ein Element ausscheidet. Das bedeutet nicht nur, daß die benötigte Zeit ungefähr N2/2 beträgt, sondern auch, daß der erforderliche Platz zur Verarbeitung der Rekursion ungefähr N beträgt (siehe unten), was nicht akzeptabel ist. Glücklicherweise gibt es relativ einfache Methoden, um zu gewährleisten, daß dieser ungünstigste Fall in realen Anwendungen des Programms nicht eintritt.

Wenn in der Datei gleiche Schlüssel vorhanden sind, so treten zwei Besonderheiten auf. Erstens tritt die Frage auf, ob beide Zeiger bei Schlüsseln stehenbleiben sollten, die gleich dem zerlegenden Element sind, oder ob ein Zeiger stehenbleiben und der andere sie durchlaufen sollte, oder ob beide Zeiger sie durchlaufen sollten. Diese Frage ist recht gründlich mathematisch untersucht worden, und die Ergebnisse zeigen, daß es am besten ist, wenn man beide Zeiger anhalten läßt. Dies führt zu ausgeglichenen Zerlegungen, wenn viele identische Schlüssel vorliegen. Zweitens entsteht bei Vorhandensein von gleichen Schlüsseln die Frage nach der richtigen Behandlung des Falles, wenn sich die Zeiger treffen. Tatsächlich kann das obige Programm geringfügig verbessert werden, indem man das Durchsuchen beendet, wenn j<i gilt, und dann quicksort(l,j) für den ersten rekursiven Aufruf verwendet. Dies ist eine Verbesserung, denn wenn j=i gilt, können wir durch die Zerlegung zwei Elemente in die richtige Position bringen, indem wir die Schleife nochmals durchlaufen. (Dieser Fall würde zum Beispiel eintreten, wenn im obigen Beispiel statt des R ein E stehen würde). Es lohnt sich wahrscheinlich, diese Änderung vorzunehmen, da das Programm in der angegebenen Form einen Datensatz mit einem Schlüssel, der gleich dem zerlegenden Schlüssel ist, in a[r] beläßt. Dies hat zur Folge, daß die erste Zerlegung im Aufruf quicksort(i + 1,r) entartet, da ihr am weitesten rechts befindlicher Schlüssel der kleinste dieser Zerlegung ist. Die oben angegebene Implementation der Zerlegung ist jedoch etwas leichter verständlich, weshalb wir sie während der nachfolgenden Erörterung in dieser Form belassen werden, wobei wir uns dessen bewußt sind, daß diese Änderung vorgenommen werden sollte, wenn viele identische Schlüssel vorliegen.


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