Robert Sedgewick: Algorithmen

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


12. Mergesort



In
Kapitel 9 untersuchten wir die Operation des Auswählens, des Auffindens des k-kleinsten Elements in einer Datei. Wir sahen, daß das Auswählen mit der Aufteilung einer Datei in zwei Teile, in die k kleinsten Elemente und die N - k größten Elemente, zusammenhängt. Im vorliegenden Kapitel untersuchen wir einen in gewisser Hinsicht komplementären Prozeß, das Mischen (merging), die Operation der Vereinigung zweier sortierter Dateien zu einer größeren sortierten Datei. Wie wir sehen werden, ist das Mischen die Grundlage für einen sehr einfachen rekursiven Sortieralgorithmus.

Auswählen und Mischen sind komplementäre Operationen in dem Sinne, daß das Auswählen eine Datei in zwei unabhängige Dateien aufspaltet und das Mischen zwei unabhängige Dateien zu einer Datei zusammenfügt. Die Beziehnung zwischen diesen Operationen wird auch dann offensichtlich, wenn man versucht, das Prinzip des »Teilens und Herrschens« anzuwenden, um eine Sortiermethode zu entwickeln. Die Datei kann entweder so umgeordnet werden, daß die ganze Datei sortiert ist, wenn zwei Teile sortiert sind, oder sie kann in zwei Teile zerlegt werden, die zu sortieren und dann so zu kombinieren sind, daß die sortierte Gesamtdatei entsteht. Wir haben bereits gesehen, was sich im ersten Falle ergibt: Dies ist Quicksort, das im wesentlichen aus einer Auswahlprozedur besteht, der zwei rekursive Aufrufe folgen. Im weiteren werden wir Mergesort (Mischsortieren) betrachten, das Komplement zu Quicksort in dem Sinne, daß es im wesentlichen aus zwei rekursiven Aufrufen besteht, denen eine Mischprozedur folgt.

Mergesort besitzt wie Heapsort den Vorteil, daß es eine aus N Elementen bestehende Datei in einer Zeit sortiert, die sogar im ungünstigsten Fall proportional zu N log N ist. Der hauptsächliche Nachteil von Mergesort besteht darin, daß zu N proportionaler zusätzlicher Speicherplatz erforderlich zu sein scheint, es sei denn, man ist bereit, große Anstrengungen zu unternehmen, um dieses Hindernis zu überwinden. Die Länge der inneren Schleife liegt etwa zwischen der von Quicksort und der von Heapsort, so daß Mergesort in Betracht kommt, wenn die Geschwindigkeit wesentlich ist, insbesondere dann, wenn Platz zur Verfügung steht. Darüber hinaus kann Mergesort so implementiert werden, daß es den Zugriff auf die Daten hauptsächlich sequentiell realisiert (ein Element nach dem anderen), was manchmal ein klarer Vorteil ist. Zum Beispiel ist Mergesort die bevorzugte Methode für das Sortieren einer verketteten Liste, wo ein sequentieller Zugriff die einzige mögliche Zugriffsart ist. In ähnlicher Weise ist das Mischen, wie wir in Kapitel 13 sehen werden, die Grundlage für das Sortieren auf Geräten mit sequentiellem Zugriff, obwohl die in diesem Zusammenhang angewandten Methoden sich etwas von denen unterscheiden, die für Mergesort verwendet werden.


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