Robert Sedgewick: Algorithmen

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


12. Mergesort



Mischen

In vielen Datenverarbeitungssystemen wird eine umfangreiche (sortierte) Datei verwaltet, zu der regelmäßig neue Eintragungen hinzugefügt werden. Eine typische Vorgehensweise ist dann, daß eine Anzahl von neuen Eingabedaten zusammengefaßt und an die (viel größere) Hauptdatei angehängt werden, und daß alles neu sortiert wird. Diese Situation ist für das Mischen wie geschaffen: Eine weit bessere Strategie besteht darin, die (kleine) Gruppe von neuen Eingabedaten zu sortieren und sie dann mit der großen Hauptdatei zu mischen. Das Mischen besitzt viele andere ähnliche Anwendungen, die seine Untersuchung lohnend machen. Wir werden auch eine auf dem Mischen beruhende Sortiermethode betrachten.

In diesem Kapitel konzentrieren wir uns auf Programme für das Zweiweg-Mischen (two-way merging): Programme, die zwei sortierte Eingabedateien kombinieren, um eine sortierte Ausgabedatei zu erzeugen. Im folgenden Kapitel werden wir das Mehrweg-Mischen (multiway merging) genauer betrachten, bei dem mehr als zwei Dateien beteiligt sind. (Die wichtigste Anwendung des Mehrweg-Mischens ist das externe Sortieren, der Gegenstand des nächsten Kapitels.)

Nehmen wir zunächst an, daß zwei sortierte Felder a[1..M] und b[1..N] aus ganzen Zahlen vorliegen, die wir in ein drittes Feld c[1..M+N] mischen wollen. Das folgende Programm ist eine direkte Implementation der offensichtlichen Strategie, schrittweise für c das kleinste verbleibende Element aus a und b zu wählen:

    i:=1; j:=1;
    a[M+1]:=maxint; b[N+1]:=maxint;
    for k:=1 to M+N do
      if a[i]<b[j]
        then begin c[k]:=a[i]; i:=i+1 end
        else begin c[k]:=b[j]; j:=j+1 end;

Die Implementation ist vereinfacht, indem in den Feldern a und b Platz bereitgestellt wurde für Marken-Schlüssel mit Werten, die größer sind als alle anderen Schlüssel. Wenn das Feld a (b) erschöpft ist, kopiert die Schleife einfach den Rest des Feldes b (a) in das Feld c. Diese Methode benutzt offensichtlich M + N Vergleiche. Falls a[M+1] und b[N+1] für die Marken-Schlüssel nicht zur Verfügung stehen, müssen Tests hinzugefügt werden, um zu gewährleisten, daß i stets kleiner gleich M und j stets kleiner gleich N ist. Ein anderer Weg, um diese Schwierigkeit zu umgehen, wird weiter unten für die Implementation von Mergesort benutzt.

Anstatt zusätzlichen Speicherplatz zu verwenden, der zur Größe der gemischten Datei proportional ist, wäre es wünschenswert, eine »am Ort« ablaufende Methode zu haben, die c[1..M] für den einen Teil der Eingabedaten und c[M+1..M+N] für den anderen benutzt. Am Anfang ist es schwierig, sich davon zu überzeugen, daß dies auf einfache Weise nicht realisierbar ist; tatsächlich existieren derartige Methoden, doch sie sind so kompliziert, daß selbst ein Sortieren am Ort wahrscheinlich effizienter ist, außer wenn sehr viel Sorgfalt aufgewandt wird. Wir werden weiter unten auf diese Frage zurückkommen.

Da für eine praktische Implementation zusätzlicher Speicherplatz notwendig zu sein scheint, können wir ebensogut eine Implementation mittels verketteter Listen betrachten. Tatsächlich ist diese Methode sehr gut für verkettete Listen geeignet. Nachstehend wird eine vollständige Implementation angegeben, die alle von uns getroffenen Vereinbarungen veranschaulicht; wie wir sehen, ist das Programm für das eigentliche Mischen genauso einfach wie das obige Programm:

    type link^=node;
         node= record key: integer; next: link end;
    var t,z: link;
        N: integer;
    function merge(a,b: link): link;
      var c: link;
      begin
      c:=z;
      repeat
        if a^.key<=b^.key 
          then begin c^.next:=a; c:=a; a:=a^.next end
          else begin c^.next:=b; c:=b; b:=b^.next end
      until c^.key=maxint;
      merge:=z^.next; z^.next:=z;
      end;

Dieses Programm mischt die Liste, auf die a zeigt, mit der Liste, auf die b zeigt, mit Hilfe eines Hilfszeigers c. Es wird angenommen, daß die Listen einen »End«-Pseudoknoten besitzen, wie er in Kapitel 3 erörtert wurde: Alle Listen enden mit dem Pseudoknoten z, der normalerweise auf sich selbst zeigt und auch als Marke dient, mit z^.key=maxint. Während des Mischens wird z benutzt, um auf den Anfang der neu gemischten Liste zu zeigen (ähnlich wie bei der Implementation von readlist), und c zeigt auf das Ende der neu gemischten Liste (den Knoten, dessen Verkettungsfeld geändert werden muß, um ein neues Element zur Liste hinzuzufügen). Nachdem die gemischte Liste hergestellt worden ist, wird der auf ihren ersten Knoten weisende Zeiger von z wiederhergestellt, und z wird zurückgesetzt, so daß es auf sich selbst zeigt.

Der Vergleich der Schlüssel in merge schließt Gleichheit mit ein, so daß das Mischen stabil ist, wenn angenommen wird, daß die Liste b nach der Liste a folgt. Weiter unten werden wir sehen, wie diese Stabilität beim Mischen Stabilität in den Sortierprogrammen nach sich zieht, die dieses Mischen verwenden.


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