Theoretische Informatik

2.2 Effiziente Sortieralgorithmen: Merge-, Quick-, Heapsort

Ich hoffe, die Diskussion am Ende des letzten Abschnitts hat gezeigt: um große Datenmengen sortieren zu können, brauchen wir nicht unbedingt schnellere Rechner sondern bessere Algorithmen. SelectionSort und InsertionSort sind vom Prinzip her einfach zu langsam.

MergeSort

Der einfachste "effiziente" Sortieralgorithmus ist wahrscheinlich MergeSort. Er funktioniert nach folgendem Prinzip: teile das Array in zwei Teile, die jeweils ungefähr $n/2$ Elemente enthalten; sortiere jeden Teil (rekursiv); füge die beiden sortierten Listen wieder zu einer Liste zusammen (merge). Als Pseudocode schaut das dann so aus:

mergesort(array):
    left = array[0..n/2] 
    right = array[n/2..n] 
    leftSorted = mergesort(left)
    rightSorted = mergesort(right)
    return merge(leftSorted, rightSorted)

Wie aber fügen wir zwei sortierte Listen (bzw. Arrays)zu einer sortierten zusammen? Wir vergleichen die jeweils ersten Elemente von array1 und array2; das kleinere davon muss nun an den Anfang der Gesamtliste verschoben werden. Dann wiederholen wir diesen Schritt bis eine der beiden Listen leer ist. Hier sehen Sie eine Animation:

Hier sehen Sie meinen Pseudocode für merge:

merge(array1, array2):
  if array1 empty: 
      return array2
  else if array2 empty:
      return array1
  else if array1[0] <  array2[0]: 
      return array1[0] + merge(array1[1..], array2)    
  else:
      return array2[0] + merge(array1, array2[1..])

Die Schreibweise array1[1..] bezeichnet hier das Subarray von array1, von dem wir das erste Element entfernt haben.

Übungsaufgabe Implementieren Sie eine Funktion merge in Elm:

merge : List comparable -> List comparable -> List comparable

Elm ist dafür gebaut, mit Listen zu arbeiten, und somit ist es relativ einfach, merge in Elm zu implementieren. In Java würde ich hier empfehlen, auf Rekursion zu verzichten und mit drei Pointern zu arbeiten: $p_1, p_2$, die auf das nächste noch nicht bearbeitete Element von array1 bzw. array2 zeigen und $p$, der auf die nächste Stelle im Ergebnisarray zeigt.

Übungsaufgabe Imlemenntieren Sie MergeSort in Java und testen Sie es auf der Datei german-50000.txt.

Demo. Wir testen MergeSort mit der Datei german-50000.txt:

time java MergeSort < german-50000.txt > /dev/null

Auf meinem Rechner benötgit dies ca 0,7 Sekunden, ist also rund vierzigmal schneller als InsertionSort.

Komplexitätsanalyse

Die Laufzeitanalyse von MergeSort ist deutlich herausfordernder als die von SelectionSort und InsertionSort. Beginnen wir mit der Subroutine merge.

Übungsaufgabe Seien array1 und array2 zwei sortierte Arrays der Länge $a$ bzw. $b$. Finden Sie heraus, wieviele Vergleichsoperationen merge(array1, array2) im Besten Fall und im schlechtesten Fall ausführt.

Übungsaufgabe Nehmen Sie ein Array Ihrer Wahl (z.B. 20 Elemente bestehend aus Zahlen, unsortiert). Simulieren Sie per Hand Mergsort auf diesem Array und zeichnen Sie den Rekursionsbaum, also baumartig alle Aufrufe von mergesort; schreiben Sie zu jedem Knoten in diesem Baum, wieviele Vergleiche der dortige Aufruf von merge durchführt.

Übungsaufgabe Leiten Sie eine obere Schranke her, wieviele Vergleiche ein Aufruf von mergesort auf einem Array der Größe $n$ maximal durchführt.

Seien Sie so präzise, wie Sie können! Geben Sie möglichst genau an, wieviele Vergleiche mergesort im Worst-Case durchführt.

Spoiler alert. Lesen Sie erst weiter, wenn Sie die letzten drei Übungsaufgaben gelöst (oder dabei aufgegeben) haben.

Lemma merge(array1, array2) tätigt höchstens $n-1$ Vergleichsoperationen, wobei $n$ die Größe des Ergebnisarrays ist (also Länge von array1 plus Länge von array2).

Wie können wir von hier aus die maximale Anzahl von Vergleichsoperationen in einem Aufruf von mergeSort(array) bestimmen? Da MergeSort ein rekursiver Algorithmus ist, bietet es sich immer an, seinen Rekursionsbaum zu skizzieren. Für ein Array der Größe 14 sähe der zum Beispiel so aus:

Jedes graue Rechteck stellt einen Aufruf von mergesort dar, und die Zahl darin ist die Größe des Arrays bei diesem Aufruf. Die Anzahl der Vergleichsoperationen, die merge tätigt, um zwei sortierte Arrays der Größen $a,b$ zu einem sortierten Array der Größe $a+b$ zusammenzufügen, ist höchstens $a+b-1$, also eins weniger als die Größe des Ergebnis-Arrays. In der folgenden Abbildung schreiben wir nun neben jedes graue Rechteck in rot die maximale Anzahl der getätigten Vergleichsoperationen.

Die insgesamte Anzahl der Vergleichsoperationen, die ein Aufruf von mergesort(array) nach sich zieht, ist also die Summe der roten Zahlen.

Theorem. Sei A ein Array aus $n$ Elementen. Dann tätigt mergesort(A) maximal $$ n \floor{1 + \log n} - 2^{\floor{1 + \log n}} $$ Vergleichsoperationen.

Für $n = 14$ wäre also $\floor {1+ \log n} = 4 $, also $ 14 \cdot 4 - 2^{4} + 1 = 41$.

Beweis. Zählen wir als erstes die Ebenen im Rekursionsbaum. Der obige Rekursionsbaum hat die Ebenen 0, 1, 2, 3 und 4, wobei der Index zählt, wie tief in der Rekursion wir stecken (der ursprüngliche Aufruf mergesort(array) liegt in Ebene 0). Die unterste Ebene, also Ebene 4, ist unvollständig, weil es bereits auf Ebene 3 Arrays mit nur einem Element gibt. Fragen wir uns also: Wieviele vollständige Ebenen gibt es? Eine erste Beobachtung ist

Beobachtung. Die Arrays in Ebene $k$ haben entweder $\floor{n/2^k}$ oder $\ceil{n/2^k}$ viele Elemente.

Die letzte vollständige Ebene ist also die, wo zuerst Arrays der Größe 1 auftreten; denn die haben dann keine Kinderknoten im Baum mehr. Eine 1 wird zum ersten Mal in Ebene $k$ auftreten, wenn $\floor{n/2^k} = 1$ ist, wenn also $k := \floor{\log n}$ ist; bei $n=14$ also auf Ebene $k = 3$. Wir haben also insgesamt $k+1$ vollständige Ebenen (beachten Sie, dass wir bei Ebene 0 anfangen, zu zählen). In jeder Ebene summieren sich die schwarzen Zahlen zu $n$ auf; die Summe der schwarzen Zahlen in allen vollständigen Ebenen ist also $n (k+1)$. Um die Summe der roten Zahlen zu erhalten, müssen wir für jeden Knoten 1 abziehen, also insgesamt $$ n (k+1) - \textnormal{ Anzahl der Knoten in Ebenen $0, \dots, k$} \ . $$ Beachten Sie, dass wir Ebene $k+1$ ignorieren können: hier haben alle Arrays die Größe 1, haben also eine rote 0 und verursachen keine Vergleichsoperationen. Die Anzahl der Knoten in den Ebenen $0, \dots, k$ ist $1 + 2 + 4 + 8 + \dots + 2^k = 2^{k+1} - 1$. Die Anzahl der Vergleichsoperationen ist höchstens die Summe der roten Zahlen, welche wiederum exakt $n (k+1) - (2^{k+1} - 1)$ ist, für $k = \floor{\log n}$. $\square$

In der Vorlesung Algorithmen und Komplexität im dritten Semester werden Sie weitere Sortieralgorithmen kennenlernen, z.B. QuickSort und HeapSort. Beide führen ähnlich viele Vergleichsoperationen aus wie MergeSort.