Zusammenführen in Linearzeit

Der letzte Teil dvom Mergesort ist die merge-Funktion, die zwei benachbarte sortierte Subarrays array [p..q] und array [q + 1..r] in ein einzelnes sortiertes Subarray array [ p..r] zusammenführt (kombiniert). Wir werden sehen, wie man diese Funktion so konstruiert, dass sie so effizient wie möglich ist. Nehmen wir an, dass die beiden Subarrays insgesamt $n$‍ Elemente haben. Wir müssen jedes der Elemente untersuchen, um sie zusammenzuführen, und so ist das Beste, was wir erwarten können eine Verschmelzungszeit von $\mathrm{\Theta }(n)$‍. In der Tat werden wir sehen, wie man insgesamt $n$‍ Elemente in $\mathrm{\Theta }(n)$‍ Zeit zusammenführt.

Um die sortierten Subarrays array [p..q] und array [q + 1..r] zusammenzuführen und das Ergebnis in array [p..r] zu erhalten, müssen wir zunächst temporäre Arrays erstellen. Wir kopieren array [p..q] und array [q + 1..r] in diese temporären Arrays. Wir dürfen das array [p..r] nicht überschreiben, bis wir die ursprünglichen Elemente in array [p..q] und array [q + 1..r] sicher kopiert haben.

Die erste Aufgabe in der Merge-Funktion besteht daher darin, zwei temporäre Arrays, lowHalf und highHalf zu erzeugen, um alle Elemente in array [p..q] nach lowHalf zu kopieren und alle Elemente aus array [q + 1..r] in highHalf zu kopieren. Wie groß sollte lowHalf sein? Das Subarray array [p..q] enthält $q-p+1$‍ Elemente. Und highHalf? Das Subarray array[q+1..r] enthält $r-q$‍ Elemente. (In JavaScript müssen wir nicht die Dimension eines Arrays angeben, wenn wir es erzeugen, aber da wir das in vielen anderen Programmiersprachen machen müssen, betrachten wir es oft bei der Beschreibung eines Algorithmus.)

Nehmen wir unser Beispiel Array [14, 7, 3, 12, 9, 11, 6, 2]. Nachdem wir rekursiv sortiert haben erhalten wir array [0..3] und array [4..7 ] (Mit $p=0$‍, $q=3$‍ und $r=7$‍) und kopiert diese Subarrays in lowHalf und highHalf:

Die Zahlen in array sind grau, um anzuzeigen, dass, obwohl diese Arraypositionen Werte enthalten, die "echten" Werte nun in lowHalf und highHalf enthalten sind. Wir können die grauen Zahlen nach Belieben überschreiben.

Als nächstes fusionieren wir die beiden sortierten Subarray lowHalf und highHalf, zurück in array[p..r]. Der kleinsten Wert in einem der beiden Subarrays gehört nach array[p]. Wo könnte dieser kleinste Wert sein? Da die Subarrays sortiert sind, kann der kleinste Wert nur an einer von zwei möglichen Stellen sein: entweder lowHalf [0] oder highHalf [0]. (Es ist möglich, dass der gleiche Wert an beiden Stellen ist, und dann nehmen wir einen von beiden.) Mit nur einem Vergleich können wir feststellen, ob wir lowHalf [0] oder highHalf[0] nach array[p] kopieren müssen. In unserem Beispiel war highHalf[0] kleiner. Wir brauchen drei Variablen, um die Arrays zu indizieren:

Nachdem wir von lowHalf oder highHalf nach array kopiert haben, müssen wir k inkrementieren (d.h. um 1 erhöhen), damit wir das nächstgrössere Element in die nächste Position von array kopieren können. Wir müssen desweiteren i inkrementieren, wenn wir von lowHalf kopiert haben oder j inkrementieren, wenn wir von highHalf kopiert haben. Hier sind die Arrays vor und nachdem das ersten Element nach array kopiert wurde:

Wir haben highHalf [0] ausgegraut, um anzuzeigen, dass es nicht mehr länger einen Wert enthält, den wir beachten werden. Der restliche Teil des highHalf-Arrays beginnt bei Index j, was nun 1 \ ist. Der Wert in array [p] ist nicht mehr ausgegraut, weil wir einen "echten" Wert in ihn kopiert haben.

Was ist der nächste Wert, der in array kopieren werden soll? Es ist entweder das erste freie Element in lowHalf ( lowHalf [0] ) oder das erste freie Element in highHalf (highHalf [1]). Mit einem Vergleich bestimmen wir, dass lowHalf[0] kleiner ist, und so kopieren wir es in array[k] und erhöhen k und i:

Als nächstes vergleichen wir lowHalf [1] und highHalf [1] und stellen fest fest, dass wir highHalf [1] in array [k] kopieren müssen. Dann erhöhen wir k und j:

Wir fahren fort, indem wir stets, lowHalf[i] mit highHalf[j] vergleichen, das kleinere der beiden in array [k] kopieren und k, sowie entweder i oder j inkrementieren:

Irgendwann sind alle Elemente auslowHalf oder highHalf ins array kopiert worden. In unserem Beispiel sind alle highHalfElemente kopiert worden, aber lowHalf enthält noch weitere Elemente. Wir beenden, indem wir die letzen verbleibenden Elemente aus lowHalf oder highHalf kopieren:

Wir behaupteten, dass das Fusion von $n$‍ -Elementen $\mathrm{\Theta }(n)$‍ Zeit benötigt, und daher ist die Laufzeit des Kombinations-Schritt proportional zur Subarray-Größe. Mal schauen, warum das so ist. Der Kombinations-Schritt besteht aus drei Teilen:

Wie viele Zeilen Code müssen wir für jeden dieser Schritte ausführen? Es ist eine konstante Zahl pro element. Jedes Element aus array wird in Schritt 1 genau einmal entweder in lowHalf oder in highHalf kopiert. Jeder Vergleich in Schritt 2 dauert gleich lang, da nur zwei Elemente verglichen werden und jedes mal genau ein Gewinner bestimmt wird. Jedes Element wird in den Schritten 2 und 3 zusammengenommen genau einmal in array kopiert. Da wir jede Zeile des Codes eine gleiche Anzahl von Malen pro Element ausführen und wir wissen, dass das Subarray array[p..q] $n$‍ Elemente enthält, ist die Laufzeit für das Kombinieren in der Tat $\mathrm{\Theta }(n)$‍ .

In der nächsten Aufgabe implementierst du diese Merge-Operation in linearer Zeit. Wenn du die beiden Aufgaben kombinierst, hast du den kompletten Merge Sort Algorithmus implementiert.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.