Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/MergeSort

MergeSort

In diesem Kapitel wird der Sortieralgorithmus MergeSort behandelt.

Rückblick

Die bisherige Verfahren erforderten einen direkten Zugriff auf einzelne Elemente (z.B. in einem Array). Sie sind besonders geeignet für internes Sortieren. Allerdings gibt es Probleme, wenn Daten sortiert werden sollen, die nicht in den den Hauptspeicher passen. Daher brauchen wir andere Verfahren, die nicht zwingend Elemente intern verwalten. Das Prinzip dieser Algorithmen ist das Sortieren in mehreren Phasen oder Schritten.

Idee

MergeSort ist ein Divide-and-Conquer Algorithmus zum vergleichsbasierten Sortieren. Zuerst wird die zu sortierende Folge in zwei Teile geteilt. Anschließend werden beide Teile voneinander getrennt sortiert. Zuletzt werden beide Teilergebnisse in der richtigen Reihenfolge zusammen gemischt.

Beispiel

Algorithmus

void mergeSort(int[] F) {
    int[] tmpF = new int[F.length];
    mergeSort(F, tmpF, 0, F.length -1);
}


void mergeSort(int[] F, int[] tmpF, int left,int right)
{ 
    if (left < right) {
        int m = (left + right)/2;
        mergeSort(F, tmpF, left, m);
        mergeSort(F, tmpF, m+1, right);
        merge(F, tmpF, left, m+1, right);
    }
}
void merge(int[] F, int[] tmpF, int startLeft, int startRight, int endRight) {
  int endLeft = startRight-1;
  int tmpPos = startLeft;
  int numElements = endRight – startLeft +1;
  while (startLeft <= endLeft && startRight <= endRight)
     if (F[startLeft] < F[startRight])
         tmpF[tmpPos++] = F[startLeft++];
     else
         tmpF[tmpPos++] = F[startRight++];
  
  while (startLeft <= endLeft)
      tmpF[tmpPos++] = F[startLeft++];
  while (startRight <= endRight)
      tmpF[tmpPos++] = F[startRight++];
  
  for (int i = 0; i < numElements; i++, endRight--)
         F[endRight] = tmpF[endRight];
}

Das Abbruchkriterium für den rekursiven Aufruf ist eine einelementige Liste.Der Misch-Vorgang erfordert in der Regel doppelten Speicherplatz, da eine neue Folge aus den beiden Sortierten generiert werden muss. Eine Alternative ist das Mischen in einem Feld (in-place), das erfordert aber aufwendiges Verschieben.

Analyse

Theorem der Terminierung

Das Theorem der Terminierung besagt, dass der Algorithmus MergeSort für jeden Eingabe int[]F nach endlicher Zeit terminiert.

Beweis

Zeige zunächst, dass jeder Aufruf mergeSort(int[] F, int[] tmpF, int left,int right) terminiert:  

Falls lef < right nicht gilt, terminiert der Aufruf sofort
Andernfalls rufen wir mergeSort rekursiv auf, wobei entweder lef einen echt größeren oder right einen echt kleineren Wert erhält. In jedem Fall wird nach einem gewissen rekursiven

Abstieg irgendwann lef<right nicht mehr gelten.

Theorem der Korrektheit

Das Theorem der Korrektheit besagt, dass der Algorithmus MergeSort das Problem des vergleichsbasierten Sortierens löst.

Beweis

Durch Induktion nach n = F.length. Annahme n=2 für eine ganze Zahl k.

n=1: Für n=1 ist der erste Aufruf der mergeSort Hilfsmethode mergeSort(F, tmpF, 0, 0)

und somit gilt nicht lef < right. Die Methode terminiert ohne Änderung an F. Dies ist korrekt, da jedes einelementige Array sortiert ist.

n/2 → n: Sei F[0...n‐1] ein beliebiges Array. Der erste Aufruf mergeSort(F, tmpF, 0, n-1) erfüllt lef<right und es werden folgende Rekursive Aufrufe getätigt: mergeSort(F, tmpF, 0, n/2-1) mergeSort(F, tmpF, n/2, n-1) Beide Aufrufe erhalten ein Array der Länge n/2. Nach Induktionsannahme gilt, dass anschliessend sowohl F[0...n/2‐1] als auch F[n/2...n‐1] separat sortiert sind. Noch zu zeigen ist, dass merge korrekt zwei sortierte Arrays in ein sortiertes Array mischt.

Theorem der Laufzeit

Das Theorem der Laufzeit besagt, dass der Algorithmus MergeSort eine Laufzeit von $\Theta (nlog_{2}n)$ hat. Diese Laufzeit ist die selbe für den besten, mittleren und schlechtesten Fall.

Beweis

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&{\text{für }}n\leq 1\\2T(n/2)+\Theta (n)&sonst\end{array}}\right.$

Nun wenden wir das Master Theorem an.

Im 2. Fall, wenn $f(n)\in \Theta (n^{log_{b}a}*ld^{k}n){\text{ für ein }}k\geq 0{\text{ dann }}T(n)=\Theta (n^{log_{b}a}*ld^{k+1}n)$

Hier ist a=2 und b=2 und es folgt $n^{log_{b}a}=n^{log_{2}2}=n^{1}=n.$

Es ist zudem f(n)=n und es gilt für k=0:

$n\in \Theta (n~ld^{k}~n)=\Theta (n)$

Es folgt $T(n)\in \Theta (n~ld^{k+1}~n)=\Theta (n~ld~n).$

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.5 zu finden.