Robert Sedgewick: Algorithmen

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


9. Quicksort



Im folgenden Kapitel untersuchen wir den Sortieralgorithmus, der wahrscheinlich am häufigsten angewandt wird, nämlich Quicksort. Der grundlegende Algorithmus wurde 1960 von
C. A. R. Hoare entwickelt; seitdem wurde er von vielen Forschern untersucht. Quicksort ist beliebt, da seine Implementation nicht schwierig ist, da es ein gutes »Mehrzweck«-Sortierverfahren ist (es funktioniert in vielen unterschiedlichen Situationen gut) und da es in vielen Situationen weniger Ressourcen erfordert als jede andere Sortiermethode.

Die Vorzüge des Quicksort-Algorithmus sind, daß er am Ort (»in-place«) abläuft (er verwendet nur einen kleinen Hilfs-Stapel), für das Sortieren von N Elementen im Durchschnitt nur ungefähr N log N Operationen erfordert und eine extrem kurze innere Schleife besitzt. Die Nachteile des Algorithmus bestehen darin, daß er rekursiv ist (die Implementation ist kompliziert, wenn keine Rekursion zur Verfügung steht), daß er im ungünstigsten Fall ungefähr N2 Operationen benötigt und daß er störanfällig ist: Ein einfacher Fehler bei der Implementation kann unbemerkt bleiben und dazu führen, daß der Algorithmus für manche Dateien schlecht arbeitet.

Die Leistungsfähigkeit von Quicksort ist sehr gut erforscht. Quicksort war Gegenstand einer gründlichen mathematischen Analyse, so daß über Fragen der Leistungsfähigkeit sehr genaue Aussagen gemacht werden können. Diese Analyse wurde durch umfangreiche empirische Erfahrungen bestätigt, und der Algorithmus wurde so weit verfeinert, daß er für ein weites Spektrum von praktischen Anwendungen des Sortierens zur bevorzugten Methode wurde. Aus diesem Grunde lohnt es sich für uns, noch etwas sorgfältiger als bei anderen Algorithmen Wege einer effizienten Implementation von Quicksort zu betrachten. Ähnliche Implementationstechniken sind auch für andere Algorithmen geeignet; bei Quicksort können wir sie bedenkenlos anwenden, da seine Leistungsfähigkeit so gut erforscht ist.

Es ist eine große Verlockung, Quicksort verbessern zu wollen, sind doch immer schnellere Sortieralgorithmen eine der größten Herausforderungen der Informatik. Kurz nachdem Hoare den Algorithmus erstmals veröffentlichte, erschienen in der Literatur bereits »verbesserte« Varianten. Viele Ideen wurden ausprobiert und analysiert, doch meist führte das zu einer Enttäuschung. Der Algorithmus ist bereits so ausgewogen, daß die Effekte von Verbesserungen in einem Teil des Programms durch die Auswirkungen verschlechterter Leistungsfähigkeit in einem anderen Teil des Programms mehr als zunichte gemacht werden können. Wir werden jedoch drei Modifikationen ausführlicher untersuchen, die eine erhebliche Verbesserung von Quicksort bewirken.

Eine sorgfältig angepaßte Variante von Quicksort läuft sicher auf den meisten Computern wesentlich schneller als jedes andere Sortierverfahren. Es ist jedoch zu beachten, daß jeder Algorithmus durch eine Anpassung empfindlicher werden kann, wobei für einige Eingabedaten unerwünschte und unerwartete Effekte auftreten können. Wenn eine Variante entwickelt worden ist, die von solchen Effekten frei zu sein scheint, so dürfte das das Programm sein, welches als Bibliotheks-Standardsortierprogramm oder für eine ernsthafte Sortier-Anwendung zu benutzen ist. Wenn man jedoch den Aufwand - um sicher zu sein, daß eine Implementation von Quicksort nicht fehlerbehaftet ist - nicht investieren will, so ist Shellsort durchaus eine sicherere Alternative, die bei geringerem Aufwand für die Implementation recht effizient abläuft.


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