Robert Sedgewick: Algorithmen

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


9. Quicksort



Zerlegung mit Hilfe des mittleren von drei Elementen

Die dritte Verbesserung von Quicksort besteht darin, ein besseres zerlegendes Element zu verwenden. Hierzu gibt es verschiedene Möglichkeiten. Der ungünstigste Fall ließe sich am sichersten vermeiden, wenn man ein zufälliges Element aus dem Feld als zerlegendes Element wählen würde. Dann würde der ungünstigste Fall mit einer vernachlässigbar kleinen Wahrscheinlichkeit eintreten. Dies ist ein einfaches Beispiel eines »stochastischen Algorithmus«, eines Algorithmus, der den Zufall ausnutzt, um unabhängig von der Anordnung der Eingabedaten fast immer eine gute Leistungsfähigkeit zu erreichen. Randomisierung kann ein nützliches Werkzeug bei der Entwicklung von Algorithmen sein, besonders dann, wenn in den Eingabedaten eine gewisse Systematik vermutet wird. Für Quicksort wäre es jedoch wahrscheinlich weit übertrieben, nur für diesen Zweck einen vollständigen Zufallszahlengenerator einzusetzen; eine beliebige Zahl genügt ebenso (siehe Kapitel 35).

Eine nützlichere Verbesserung kann erfolgen, indem drei Elemente aus der Datei entnommen werden und das mittlere von ihnen dann als das zerlegende Element benutzt wird. Wenn die drei gewählten Elemente aus dem linken, mittleren und rechten Teil des Feldes stammen, kann die Verwendung von Marken wie folgt vermieden werden: Sortiere die drei Elemente (unter Verwendung des Verfahrens zum Sortieren von drei Elementen aus dem vorangegangenen Kapitel), tausche dann das mittlere Element gegen a[r - 1] aus und arbeite den Zerlegungsalgorithmus für a[l + 1 .. r - 2] ab. Diese Verbesserung wird Zerlegungsmethode des mittleren von drei Elementen (median-of-three) genannt.

Die Methode des mittleren von drei Elementen verbessert Quicksort auf dreierlei Weise. Erstens wird es durch sie wesentlich unwahrscheinlicher, daß bei irgendeinem realen Sortierproblem der ungünstigste Fall eintritt. Damit das Sortierverfahren eine Zeit von N2 benötigt, müßten zwei der drei untersuchten Elementen zu den größten oder zu den kleinsten Elementen in der Datei gehören, und dies müßte ständig bei nahezu allen Zerlegungen der Fall sein. Zweitens erübrigt sich durch diese Methode die Notwendigkeit von Marken-Schlüsseln für den Zerlegungsprozeß, da diese Funktion von den drei vor der Zerlegung untersuchten Elementen erfüllt wird. Drittens verkürzt sich die durchschnittliche Gesamtlaufzeit des Algorithmus um etwa 5%.

Die Kombination einer nichtrekursiven Implementation der Methode des mittleren von drei Elementen mit einem Beschneiden für kleine Teildateien kann die Laufzeit von Quicksort im Vergleich zu der einfachen rekursiven Implementation um 25% bis 30% verkürzen. Weitere Verbesserungen des Algorithmus sind möglich (zum Beispiel könnte das mittlere von fünf oder mehr Elementen verwendet werden), doch die Zeitersparnis ist unerheblich. Erheblich mehr Zeit kann eingespart werden (mit weniger Aufwand), indem man die inneren Schleifen (oder das gesamte Programm) in Assembler oder Maschinensprache kodiert. Diese Wege sind jedoch nur für Experten bei ernsthaften Sortieranwendungen zu empfehlen.


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