Robert Sedgewick: Algorithmen

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


12. Mergesort



Weitere Bemerkungen zur Rekursion

Die Programme im vorliegenden Kapitel stellen zusammen mit Quicksort typische Implementationen von Algorithmen des Typs »Teile und Herrsche« dar. In späteren Kapiteln lernen wir verschiedene Algorithmen mit ähnlicher Struktur kennen, weshalb es angebracht ist, einige grundlegende Merkmale dieser Implementationen näher zu betrachten.

Quicksort ist in Wirklichkeit ein Algorithmus vom Typ »Herrsche und Teile«: In einer rekursiven Implementationen wird die Hauptarbeit vor den rekursiven Aufrufen erledigt. Demgegenüber hat das rekursive Mergesort eher den Geist von »Teile und Herrsche«: Zuerst wird die Datei in zwei Teile zerlegt, danach wird jeder Teil für sich bewältigt. Das erste Problem, das bei Mergesort tatsächlich bearbeitet wird, ist klein; die größte Teildatei wird erst zum Schluß bearbeitet. Quicksort beginnt die Bearbeitung mit der größten Teildatei und bearbeitet die kleinen am Ende.

Dieser Unterschied kommt in den nichtrekursiven Implementationen der beiden Methoden deutlich zum Ausdruck. Bei Quicksort muß ein Stapel unterhalten werden, da umfangreiche Teilprobleme gespeichert werden müssen, die in einer von den Daten abhängigen Weise aufgeteilt werden. Mergesort besitzt eine einfache nichtrekursive Variante, da die Art und Weise, wie die Datei zerlegt wird, von den Daten unabhängig ist. Daher kann die Reihenfolge, in der Teilprobleme bearbeitet werden, etwas umgestellt werden, so daß ein einfacheres Programm entsteht.

Ein weiterer praktischer Unterschied, der dabei deutlich wird, besteht darin, daß Mergesort (wenn es richtig implementiert ist) stabil ist, Quicksort dagegen nicht (außer wenn sehr viel zusätzlicher Aufwand getrieben wird). Wenn wir bei Mergesort (induktiv) annehmen, daß die Teildateien stabil sortiert worden sind, brauchen wir nur abzusichern, daß das Mischen auf stabile Weise erfolgt, was sich leicht erreichen läßt. Bei Quicksort bietet sich jedoch kein einfacher Weg an, wie das Zerlegen in stabiler Weise realisiert werden könnte, so daß die Möglichkeit der Stabilität schon ausgeschlossen ist, bevor die Rekursion ins Spiel kommt.

Eine abschließende Bemerkung: Wie Quicksort oder jedes andere rekursive Programm läßt sich Mergesort verbessern, indem kleine Teildateien anders behandelt werden. In den rekursiven Varianten des Programms kann dies genauso wie für Quicksort implementiert werden, indem entweder kleine Teildateien sofort bei Auftreten mit Insertion Sort behandelt werden, oder indem nachträglich ein Durchlauf zur Herstellung der Ordnung vorgenommen wird. In den nichtrekursiven Varianten können in einem Durchlauf am Anfang unter Benutzung von Insertion Sort oder Selection Sort kleine sortierte Teildateien aufgebaut werden. Eine andere Idee, die für Mergesort vorgeschlagen wurde, besteht darin, die »natürliche« Ordnung in der Datei auszunutzen, indem eine Bottom-Up-Methode verwendet wird, die die ersten beiden sortierten Sequenzen in der Datei mischt (gleichgültig, wie lang diese sind), dann die nächsten beiden Sequenzen usw., wobei dieser Prozeß so lange wiederholt wird, bis die Datei sortiert ist. Doch so günstig diese Methode scheinen mag, hält sie doch einem Vergleich mit der betrachteten Standardmethode nicht stand, da die Kosten für die Identifizierung der Sequenzen, die in der inneren Schleife erfolgen muß, die erzielten Einsparungen mehr als zunichte machen, von gewissen entarteten Fällen (z.B. bei einer Datei, die bereits sortiert ist) einmal abgesehen.


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