Robert Sedgewick: Algorithmen

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


9. Quicksort



Kleine Teildateien

Die zweite Verbesserung von Quicksort ergibt sich aus der Beobachtung, daß ein rekursives Programm stets sich selbst für viele kleine Teildateien aufruft; daher sollte es eine möglichst gute Methode verwenden, wenn es kleine Teildateien verarbeitet. Ein offensichtlich möglicher Weg, um das zu erreichen, besteht darin, den Test »if r>l M then« zu Beginn des rekursiven Programms in der Weise abzuändern, daß Insertion Sort aufgerufen wird (nachdem dieses derart modifiziert wurde, daß es Parameter akzeptiert, die die zu sortierende Teildatei definieren), also »if r - l <= M then insertion (l,r)«. Dabei ist M ein Parameter, dessen genauer Wert von der Implementation abhängt. Der für M gewählte Wert muß nicht der bestmögliche sein; für M im Bereich von etwa 5 bis etwa 25 läuft der Algorithmus ungefähr mit gleicher Effizienz ab. Die Verkürzung der Laufzeit liegt für die meisten Anwendungen in der Größenordnung von 20%.

Eine etwas einfachere Methode der Behandlung kleiner Teildateien, die außerdem etwas effizienter ist, besteht darin, den Test zu Beginn einfach in »if r - l > M then« umzuändern, das heißt, während des Zerlegens kleine Teildateien einfach zu ignorieren. Bei der nichtrekursiven Implementation würde das realisiert, indem Dateien, die kleiner als M sind, nicht im Stapel abgelegt werden. Nach dem Zerlegen liegt dann eine Datei vor, die fast sortiert ist. Für solche Dateien ist jedoch, wie im vorangegangenen Kapitel erläutert wurde, Insertion Sort die am besten geeignete Methode. Das heißt, daß Insertion Sort für eine solche Datei etwa ebenso gut abläuft wie für die Menge von kleinen Dateien, die entstehen würden, wenn es direkt angewandt würde. Diese Methode sollte jedoch mit Vorsicht angewandt werden, da Insertion Sort immer sortiert, selbst, wenn in Quicksort ein Fehler vorliegt, durch den es überhaupt nicht funktioniert. Der übermäßige Zeitbedarf kann dann das einzige Anzeichen dafür sein, daß etwas nicht stimmt.

Abbildung 9.6
Abbildung 9.6 Quicksort (rekursive Implementation, M = 12).

Abbildung 9.6 veranschaulicht diesen Prozeß für ein umfangreiches, zufällig angeordnetes Feld. In diesen Diagrammen ist grafisch dargestellt, wie jede Zerlegung ein Teilfeld in zwei unabhängige Teilprobleme aufteilt, die dann unabhängig voneinander in Angriff genommen werden. Ein Teilfeld ist in diesen Abbildungen als ein Quadrat dargestellt, welches zufällig angeordnete Punkte enthält; durch den Zerlegungsprozeß wird ein solches Quadrat in zwei kleinere Quadrate unterteilt, wobei sich ein Element (das zerlegende Element) auf der Diagonalen befindet. Elemente, die nicht am Zerlegungsprozeß beteiligt sind, befinden sich am Ende sehr nahe bei der Diagonalen, wodurch ein Feld übrigbleibt, welches sich mit Insertion Sort leicht bearbeiten läßt. Wie oben erwähnt wurde, ist das entsprechende Diagramm für die nichtrekursive Implementation von Quicksort ähnlich, nur daß die Zerlegungen in anderer Reihenfolge vorgenommen werden.


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