 |
Kleine Teildateien | |
|
Die zweite Verbesserung von Quicksort. Ein rekursives Programm ruft stets sich selbst für viele kleine Teildateien auf. Es sollte eine gute Methode für die Bearbeitung von kleinen Teildateien entwickelt werden. Ein möglicher Weg ist zu Beginn des rekursiven Programms in folgender Weise abzuändern: "if r-l <= M then insertion (l,r)". M ist 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 5 bis 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%. Noch eine einfachere Methode der Behandlung kleiner Teildateien besteht darin, den Test zu Beginn einfach in "if r-l > M then" umzuändern, d.h., während des Zerlegens kleine Teildateien einfach zu ignorieren. Bei eine nichtrekursiven Implementation würde das realisiert werden, indem Dateien, die kleiner als M sind, nicht im Stapel abgelegt werden. Für solche Dateien ist die Insertion Sort die am besten geeignete Methode. Nur soll man aufpassen, 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. |
