Robert Sedgewick: Algorithmen

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


12. Mergesort



Mergesort von Listen

Dieser Prozeß beinhaltet bereits so viele Bewegungen von Daten, daß eine Darstellung mittels verketteter Listen gleichfalls betrachtet werden sollte. Das folgende Programm ist eine direkte rekursive Implementation einer Funktion, welche als Eingangsgröße einen auf eine unsortierte Liste weisenden Zeiger verwendet und als ihren Wert einen auf die sortierte Variante der Liste weisenden Zeiger zurückgibt. Das Programm realisiert dies durch Umordnen der Knoten der Liste; es brauchen keine zeitweiligen Knoten oder Listen vorgesehen zu werden. (Es ist zweckmäßig, die Länge der Liste dem rekursiven Programm als Parameter zu übergeben; eine andere Möglichkeit wäre, sie gemeinsam mit der Liste zu speichern oder das Programm die Liste durchlaufen zu lassen, um ihre Länge festzustellen.)

    function mergesort(c: link): link;
      var a,b: link;
      begin
      if c^.next=z then mergesort:=c else
        begin
        a:=c; b:=c^.next; b:=b^.next; b:=b^.next;
        while b<>z do begin c:=c^.next; b:=b^.next; b:=b^.next end
        b:=c^.next; c^.next:=z;
        mergesort:=merge(mergesort(a),mergesort(b));
        end;
      end;

Dieses Programm sortiert, indem es die Liste, auf die c zeigt, in zwei Hälften zerlegt, auf die a und b zeigen, darauf die beiden Hälften rekursiv sortiert und dann merge benutzt, um das Endergebnis zu erhalten. Auch für dieses Programm gilt die Vereinbarung, daß alle Listen mit z enden: Die Eingabeliste muß mit z enden (und daher ist das auch bei der Liste b der Fall), und die explizite Anweisung c^.next:=z setzt z an das Ende der Liste a. Dieses Programm ist in einer rekursiven Formulierung sehr leicht verständlich, obwohl es in Wirklichkeit ein recht raffinierter Algorithmus ist.


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