Robert Sedgewick: Algorithmen

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


9. Quicksort



Kenngrößen der Leistungsfähigkeit von Quicksort

Das Beste, was bei Quicksort passieren könnte, wäre, daß jede Zerlegung die Datei genau halbiert. Dann würde die Anzahl der von Quicksort benutzten Vergleiche der rekurrenten Beziehung vom Typ »Teile und Herrsche«

CN = 2CN/2 + N

genügen. (Die Größe 2CN/2 beinhaltet die Kosten des Sortierens der zwei Teildateien; N drückt die Kosten für die Prüfung jedes Elementes unter Benutzung des einen oder anderen Zerlegungszeigers aus.) Aus Kapitel 6 wissen wir, daß diese rekurrente Beziehung die Lösung

CN rund N lg N

besitzt. Obwohl die Situation nicht immer so günstig ist, trifft es jedoch zu, daß die Zerlegung im Durchschnitt auf die Mitte fällt. Die Berücksichtigung der exakten Wahrscheinlichkeit jeder Position der Zerlegung macht die rekurrente Beziehung komplizierter und schwerer auflösbar, doch das Endergebnis ist ähnlich.

Eigenschaft 9.1 Quicksort benötigt im Mittel ungefähr 2N ln N Vergleiche.

Die exakte rekurrente Beziehung für die Anzahl der Vergleiche, die Quicksort für eine zufällige Permutation von N Elementen benötigt, lautet

Formel

Der Term N + 1 beinhaltet die Kosten des Vergleichs des zerlegenden Elements mit jedem der anderen Elemente (mit zwei zusätzlichen Vergleichen, wenn die Zeiger sich treffen); der Rest ergibt sich aus der Beobachtung, daß jedes Element k mit der Wahrscheinlichkeit 1/k das zerlegende Element sein kann, wonach zufällige Dateien der Größe k - 1 und N - k vorliegen.

Obwohl diese rekurrente Beziehung recht kompliziert aussieht, läßt sie sich in Wirklichkeit in drei Schritten leicht auflösen. Zunächst ist C0 + C1 + ... + CN-1 gleich CN-1 + CN-2 + ... + C0, so daß

Formel

gilt.

Zweitens können wir die Summe eliminieren, indem wir beide Seiten mit N multiplizieren und die gleiche Formel für N - 1 subtrahieren:

NCN - (N - 1)CN-1 = N(N+1) - (N - 1)N + 2CN-1.

Durch Vereinfachung ergibt sich die rekurrente Beziehung

NCN = (N + 1)CN-1 + 2N.

Drittens erhält man durch Division beider Seiten durch N(N + 1) eine rekurrente Beziehung, die sich wie folgt fortsetzen läßt:

Formel

Dieses exakte Ergebnis entspricht ziemlich genau einer Summe, die leicht durch ein Integral approximiert werden kann:

Formel

woraus sich die Behauptung ergibt. Nicht unerwähnt bleiben sollte, daß 2N ln N rund 1,38N lg N gilt, so daß die durchschnittliche Zahl der Vergleiche nur um etwa 38% größer ist als im besten Fall.

Daraus ist ersichtlich, daß die obige Implementation für zufällige Dateien sehr leistungsfähig ist, wodurch sie zu einem sehr brauchbaren Mehrzweck-Sortierverfahren wird. Falls das Sortierverfahren jedoch sehr oft zur Anwendung kommen soll, oder wenn es zum Sortieren einer sehr umfangreichen Datei benutzt werden soll, könnte es sich lohnen, einige der im folgenden betrachteten Verbesserungen zu implementieren. Diese können die Wahrscheinlichkeit des Eintretens eines ungünstigen Falls wesentlich verringern, die durchschnittliche Laufzeit um 20% verkürzen und leicht den Verzicht auf einen Marken-Schlüssel ermöglichen.


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