Sortieralgorithmen
Suchalgorithmen
Datenstrukturen
Verschiedenes
Quellen
Bei dem rekursiven Programm ist zu beobachten, daß sich dieses für viele kleine Mengen aufruft, was Laufzeit, wie auch Speicherplatz
kostet. Eine Optimierung wäre es hier auf kleinen Mengen nicht wieder den QuickSort auf diesen auszuführen, sondern den InsertionSort
zu verwenden. Dies würde man durch eine Abrage wie
if( right - left < M )
realisieren, wobei M eine Konstante bezeichnet, die
vom Programmierer festgelegt wird, jedoch klein gehalten werden sollte. Trifft die Auswertung des Ausdrucks zu, so ruft man einen InsertionSort
auf, um die Menge zwischen left und right zu sortieren, ansonsten würde die Menge wie gewohnt zerteilt.. Auch bei der
iterativen Variante würde dieses Verfahren zu besseren Laufzeiten führen.
Eine weitere, sehr häufig anzutreffende Methode, den QuickSort zu verbessern, ist, einen geeigneten Pivotwert auszuwählen. Da aber das berechnen des Mittelwertes ein kostspieliger Aufwand ist, muss man sich eines anderen Verfahrens begnügen. Das Laufzeitproblem zu umgehen, kann erfolgen, indem man drei Elemente aus der Menge wählt und diese für sich sortiert. Anschließend nutzt man diese Elemente zu Zerlegung der Menge. Diese Methode wird auch als median-of-three genannt, und soll an anderer Stellte behandelt werden.
Nächste Seite: MergeSort
Aufwärts: QuickSort
Vorherige Seite: iterativ (nicht rekursiv)
Inhalt
