Überblick über Mergesort

Weil wir die rekursive Teile-und Herrsche Strategie verwenden, müssen wir uns entscheiden, wie unsere Unterprobleme aussehen. Das vollständige Problem ist, ein ganzes Array zu sortieren. Nehmen wir an, dass ein Unterproblem darin besteht, ein Subarray zu sortieren. Genau genommen sortieren wir das Subarray vom Index $p$‍ bis zum Index $r$‍. Es wird zweckmäßig sein, eine Notation für ein Subarray zu haben, also sagen wir, dass array [p..r] das Subarray von array bezeichnet. Beachte, dass diese "Zwei-Punkte" Notation kein gültiges JavaScript ist; Wir verwenden sie nur um den Algorithmus zu beschreiben, anstatt den Algorithmus in Code zu implementieren. In Bezug auf unsere Notation gilt für ein Array mit $n$‍ Elementen, dass das ursprüngliche Problem darin besteht das Array [0..n-1] zu sortieren.

Mergesort verwendet Teile-und-Herrsche wie folgt:

Wir benötigen einen Basisfall. Der Basisfall ist ein Subarray mit weniger als zwei Elementen, das heißt, wenn $p\ge r$‍ ist, da ein Subarray ohne Elemente oder mit nur einem Element bereits sortiert ist. So werden wir nur teilen-herrschen-kombinieren, wenn $p<r$‍ ist.

Wir schauen uns das anhand eines Beispiels an.Wir beginnen mit array, das die Zahlen [14, 7, 3, 12, 9, 11, 6, 2] enthält. Das erste Subarray ist damit das volle Array, array [0..7] (mit $p=0$‍ Und $r=7$‍). Dieses Subarray hat mehr als zwei Elemente, und ist somit kein Basisfall. Das bedeutet, dass wir das Subarray aufteilen können:

Wie wurde das Subarray array [0..3] sortiert? In der gleichen Weise. Es hat mehr als zwei Elemente, ist somit kein Grundfall und wird weiter aufgeteilt. Mit $p=0$‍ und $r=3$‍, berechnen wir $q=1$‍ und sortieren rekursiv array [0..1] ([14, 7]) und array [2..3] ([ 3, 12]), was zu array [0..3]mit dem Inhalt [7, 14, 3, 12] führt. Der Kombinationsschritt führt die erste Hälfte mit der zweiten Hälfte zusammen, wodurch [3, 7, 12, 14] entsteht.

Wie wurde das Subarray array [0..1] sortiert? Mit $p=0$‍ und $r=1$‍, berechnen wir $q=0$‍. Rekursiv sortieren wir array [0..0] ([14]) und array [1..1] ([7] ), was zu array [0..1] führt, das [14, 7] enthält und nach dem Kombinations-Schritt zu [7, 14] wird.

Die Subarrays array [0..0] und array [1..1] sind Basisfälle, da jedes weniger als zwei Elemente enthält. Hier ist unser Mergesort Algorithmus, in seinen einzelnen Schritten:

Die meisten Schritte in Mergesort sind eigentlich ganz einfach. Du kannst den Basisfall leicht überprüfen und die Suche nach dem Mittelpunkt $q$‍ im Teilungs-Schritt ist auch recht einfach. Du musst zwei rekursive Anrufe im Eroberungsschritt machen. Es ist der Kombinations-Schritt, wo man zwei sortierte Subarrays zusammenführen muss, wo die eigentliche Arbeit passiert.

In der nächsten Aufgabe wirst du dich auf die Implementierung des gesamten Merge-Sortieralgorithmus konzentrieren, um sicherzustellen, dass du verstehst, wie man rekursiv teilt und herrscht. Nachdem du das getan hast, tauchen wir tiefer in die Frage ein, wie du zwei sortierte Subarrays effizient zusammenführen kannst und du wirst das in der nächsten Aufgabe implementieren.

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.