Robert Sedgewick: Algorithmen

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


12. Mergesort



Optimierte Implementationen

Bei unserer Betrachtung von Marken haben wir der inneren Schleife von Mergesort auf der Grundlage von Feldern bereits einige Aufmerksamkeit geschenkt. Dabei sahen wir, daß in der inneren Schleife die Tests auf die Feldgrenzen vermieden werden können, indem die Reihenfolge in einem der Felder umgekehrt wird. Hierdurch wird unsere Aufmerksamkeit auf eine größere Unzulänglichkeit in den obigen Implementationen gelenkt: das Kopieren von a nach b. Wie wir für Straight Radix Sort in Kapitel 10 gesehen haben, kann dieses Kopieren vermieden werden, indem man zwei Kopien des Programms benutzt: eine, um a nach b, und eine, um b nach a zu mischen.

Um diese beiden Verbesserungen kombiniert zu realisieren, ist es erforderlich, Änderungen dahingehend vorzunehmen, daß merge Felder entweder in steigender oder fallender Reihenfolge ausgeben kann. Bei der nichtrekursiven Variante wird das erreicht, indem zwischen steigender und fallender Ausgabe gewechselt wird; bei der rekursiven Variante haben wir vier rekursive Routinen: für das Mischen von a (b) nach b (a) mit dem Ergebnis in fallender oder steigender Reihenfolge. Jede von ihnen würde die innere Schleife von Mergesort auf einen Vergleich, ein Abspeichern, zwei Inkrementierungen von Zeigern (i oder j sowie k) und einen Zeigertest reduzieren. Dies steht in einem günstigen Verhältnis zu den Vergleichen, Inkrementieren und Testen sowie (teilweisen) Austauschen bei Quicksort, und die innere Schleife von Quicksort wird 2 ln N rund 1,38 lg N Male ausgeführt, etwa 38% öfter als die von Mergesort.


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