Mergesort

Ein weiterer rekursiver Algorithmus zum Sortieren ist Mergesort.

Auftrag 1:

Studiere die erste Seite der PDF-Datei zum Problem.

Auftrag 2:

Im angegebenen Text wird die Aufteilung (Split) und das Mischen (Merge) wie folgt dargestellt:

Split-------------------------
     5  1  8  9  3  2

   5  1  8          9  3  2

 5  1       8      9  3       2

 5     1    8    9      3     2

Merge-------------------------

  1  5      8      3  9       2

    1  5  8         2  3  9

        1  2  3  5  8  9

Verfahre ebenso mit dem hier angegebenen Feld.

Das Programm zur Lösung des Problems ist hier in rekursiver Formulierung angegeben. Verschaffe dir einen Überblick über den Ablauf. Die genauen Berechnungen der Indizes müssen nicht nachvollzogen werden.

public void mergesort(int links, int rechts)
{ if (rechts > links) // mehr als ein Element
       { // Feld teilen und Teilfelder sortieren
         int mitte = (links + rechts)/2;
         mergesort(links, mitte);
         mergesort(mitte+1, rechts);
         // Hilfsfeld fuellen
         for (int k=links; k<=mitte; k++)    // linken Teil normal kopieren
              ablage[k] = feld[k];
         for (int k=mitte+1; k<=rechts; k++) // rechten Teil umgekehrt kopieren
              ablage[rechts + mitte - k + 1] = feld[k];
         // Aus Ablage zurueck ins urspruengliche Feld mischen
         int nachlinks = rechts; // Laufvariable von rechts nach links
         int nachrechts = links; // Laufvariable von links nach rechts
                                 // Die kleinsten Elemente stehen jeweils
                                 // an den Enden des Hilfsfeldes
         for (int k=links; k<=rechts; k++)
         {  if (ablage[nachrechts] < ablage[nachlinks])
                 { feld[k] = ablage[nachrechts];
                   nachrechts++;
                 }
            else { feld[k] = ablage[nachlinks];
                   nachlinks--;
                 }
         }
       } // end if
}  // mergesort

Auftrag 2:

In der Datei MergesortDemo.zip ist ein direkt lauffähiges BlueJ-Projekt gespeichert. Entpacke die Dateien und starte das Programm. Vergleiche mit Quicksort.