Kurs:Algorithmen und Datenstrukturen/Vorlesung/MergeSort
MergeSort
BearbeitenIn diesem Kapitel wird der Sortieralgorithmus MergeSort behandelt.
Rückblick
BearbeitenDie 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
BearbeitenMergeSort 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
BearbeitenAlgorithmus
Bearbeitenvoid 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
BearbeitenTheorem der Terminierung
BearbeitenDas Theorem der Terminierung besagt, dass der Algorithmus MergeSort für jeden Eingabe int[]F nach endlicher Zeit terminiert.
Beweis
BearbeitenZeige 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
BearbeitenDas Theorem der Korrektheit besagt, dass der Algorithmus MergeSort das Problem des vergleichsbasierten Sortierens löst.
Beweis
BearbeitenDurch 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
BearbeitenDas Theorem der Laufzeit besagt, dass der Algorithmus MergeSort eine Laufzeit von hat. Diese Laufzeit ist die selbe für den besten, mittleren und schlechtesten Fall.
Beweis
Bearbeiten
Nun wenden wir das Master Theorem an.
Im 2. Fall, wenn
Hier ist a=2 und b=2 und es folgt
Es ist zudem f(n)=n und es gilt für k=0:
Es folgt
Literatur
BearbeitenDa 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.