Robert Sedgewick: Algorithmen

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


12. Mergesort



Mergesort

Nachdem wir über eine Prozedur für das Mischen verfügen, ist es nicht schwer, sie als Grundlage für eine rekursive Prozedur für das Sortieren zu verwenden. Um eine gegebene Datei zu sortieren, teile man sie in zwei Hälften, sortiere die beiden Hälften (rekursiv) und mische sie dann. Die folgende Implementation dieses Prozesses sortiert ein Feld a[l..r] (unter Verwendung eines Hilfsfeldes b[l..r]:

    procedure mergesort(l,r: integer);
      var i,j,k,m: integer;
      begin
      if r-l>0 then
        begin
        m:=(r+l) div 2;
        mergesort(l,m); mergesort(m+1,r);
        for i:=m downto l do b[i]:=a[i]; 
        for j:=m+1 to r do b[r+m+1-j]:=a[j];
        for k:=l to r do
          if b[i]<b[j] 
            then begin a[k]:=b[i]; i:=i+1 end
            else begin a[k]:=b[j]; j:=j-1 end;
          end;
        end;

Dieses Programm realisiert das Mischen ohne Marken, indem es das zweite Feld in eine Position unmittelbar neben dem ersten, jedoch in umgekehrter Reihenfolge kopiert. Dadurch dient jedes Feld als »Marke« für das andere: Das größte Element (das sich in dem einen oder anderen Feld befindet) sorgt dafür, daß alles richtig abläuft, nachdem das andere Feld für das Mischen erschöpft ist. Die »innere Schleife« dieses Programms ist recht kurz (Kopieren nach b, Zurückkopieren nach a, Inkrementieren von i oder j, Inkrementieren und Testen von k), und sie könnte sogar noch weiter verkürzt werden, wenn zwei Kopien des Codes verwendet würden (eine für das Mischen von a nach b und eine für das Mischen von b nach a), obwohl es dann erforderlich wäre, auf Marken zurückzugreifen.

Unsere Datei von Beispielschlüsseln wird wie in Abbildung 12.1 dargestellt verarbeitet. Jede Zeile zeigt das Ergebnis eines Aufrufs von merge. Zuerst mischen wir A und S und erhalten A S, dann mischen wir O und R und erhalten O R. Diese mischen wir mit A S und erhalten A O R S. Später mischen wir I T mit G N und erhalten G I N T, mischen dies mit A O R S und erhalten A G I N O R S T usw. Somit werden bei dieser Methode aus kleinen sortierten Dateien rekursiv größere aufgebaut.

Abbildung 12.1
Abbildung 12.1 Rekursives Mergesort.


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