Robert Sedgewick: Algorithmen

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


12. Mergesort



Bottom-Up Mergesort

Wie in Kapitel 5 erläutert wurde, besitzt jedes rekursive Programm ein nichtrekursives Analogon, das, obwohl es äquivalent ist, die Berechnungen möglicherweise in anderer Reihenfolge ausführt. Mergesort ist tatsächlich ein Musterbeispiel für die Strategie des »Kombinierens und Herrschens«, die für viele derartige Berechnungen charakteristisch ist, und es lohnt sich, seine nichtrekursiven Implementationen ausführlich zu untersuchen.

Die einfachste nichtrekursive Variante von Mergesort verarbeitet eine etwas andere Menge von Dateien in einer etwas anderen Reihenfolge: Durchlaufe zuerst die Liste und führe dabei Mischoperationen »1 mit 1« aus, so daß sortierte Teillisten der Größe 2 erzeugt werden, durchlaufe dann die Liste und führe Mischoperationen »2 mit 2« aus, so daß sortierte Teillisten der Größe 4 erzeugt werden, führe dann Mischoperationen »4 mit 4« aus, um sortierte Teillisten der Größe 8 zu bekommen usw., bis die gesamte Liste sortiert ist.

Abbildung 12.2 zeigt, daß diese Methode für unsere Beispieldatei (da ihre Größe nahe bei einer Zweierpotenz liegt) im wesentlichen die gleichen Mischoperationen ausführt wie in Abbildung 12.1, jedoch in einer anderen Reihenfolge. Im allgemeinen sind für das Sortieren einer Datei aus N Elementen log N Durchläufe erforderlich, da sich die Größe der sortierten Teildateien bei jedem Durchlauf verdoppelt.

Abbildung 12.2
Abbildung 12.2 Nichtrekursives Mergesort.

Es ist wichtig anzumerken, daß die tatsächlichen Mischoperationen, die von dieser Bottom-Up-Methode ausgeführt werden, nicht die gleichen sind wie die Mischoperationen, die bei der obigen rekursiven Implementation ausgeführt werden. Betrachten wir das Sortieren von 95 Elementen, das in Abbildung 12.3 dargestellt ist. Das letzte Mischen ist ein Mischen »64 mit 31«, während es beim rekursiven Sortieren ein Mischen »47 mit 48« wäre. Es ist jedoch möglich, dafür zu sorgen, daß die Folge der von den beiden Methoden ausgeführten Mischoperationen die gleiche ist, obwohl es keinen besonderen Grund gibt, das zu tun.

Abbildung 12.3
Abbildung 12.3 Mergesort einer zufälligen Permutation.

Eine ausführliche Implementation dieser Bottom-Up-Methode unter Verwendung verketteter Listen ist nachstehend angegeben.

    function mergesort(c: link): link;
      var a,b,head,todo,t: link;
          i,N: integer;
      begin
      N:=1; new(head); head^.next:=c;
      repeat
        todo:=head^.next; c:=head;
        repeat
          t:=todo;
          a:=t; for i:=1 to N-1 do t:=t^.next;
          b:=t^.next; t^.next:=z;
          t:=b; for i:=1 to N-1 do t:=t^.next;
          todo:=t^.next; t^.next:=z;
          c^.next:=merge(a,b);
          for i:=1 to N+N do c:=c^.next
        until todo=z;
        N:=N+N;
      until a=head^.next;
      mergesort:=head^.next
      end;

Dieses Programm verwendet einen »Listenknoten« (auf den head zeigt), dessen Verkettungsfeld auf die sortierte Datei zeigt. Bei jeder Iteration der äußeren repeat-Schleife wird die Datei durchlaufen, und es wird eine verkettete Liste erzeugt, die aus sortierten Teildateien besteht, welche doppelt so lang sind wie beim vorangegangenen Durchlauf. Dies erfolgt unter Verwendung von zwei Zeigern, einem, der auf den noch nicht sichtbaren Teil der Liste zeigt (todo), und einem, der auf das Ende des Teils der Liste zeigt, für den die Teildateien bereits gemischt wurden (c). Die innere repeat-Schleife mischt die zwei Teildateien der Länge N, wobei sie bei dem Knoten beginnt, auf den todo zeigt, und eine Teildatei der Länge N+N erzeugt, welche mit der resultierenden Liste c verbunden ist.

Das eigentliche Mischen wird ausgeführt, indem eine Verkettung zur ersten zu mischenden Teildatei in a aufbewahrt wird, indem danach N Knoten übersprungen werden (unter Verwendung der zeitweiligen Verkettung t), indem z mit dem Ende der Liste a verbunden wird und indem dann das gleiche getan wird, um eine weitere Liste aus N Knoten zu bekommen, auf die b zeigt (wobei todo mittels der Verkettung des letzten besuchten Knotens aktualisiert wird), und indem dann merge aufgerufen wird. (Danach wird c aktualisiert, indem einfach hinunter zum Ende der soeben gemischten Liste gegangen wird. Dies ist eine einfachere (jedoch etwas weniger effiziente) Methode, als die verschiedenen zur Verfügung stehenden Alternativen, wie etwa merge Zeiger zurückgeben zu lassen, die auf den Anfang und das Ende zeigen, oder mehrfache Zeiger in jedem Knoten der Liste aufzubewahren.)

Bottom-Up-Mergesort ist auch eine interessante Methode für eine Implementation mit Feldern; dies wird dem Leser als nützliche Übung überlassen.


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