Teile-und-herrsche-Algorithmen

Die beiden Sortieralgorithmen, die wir bisher angeschaut haben, Auswahl sortieren und Insertionsort, haben Worst-Case-Laufzeiten von $\mathrm{\Theta }(n^2)$‍. Wenn die Größe des Eingabe-Arrays groß ist, können diese Algorithmen lange laufen. In diesem und dem folgenden Tutorial werden wir zwei weitere Sortieralgorithmen kennenlernen deren Laufzeiten besser sind: Mergesort und Quicksort. Insbesondere ist die Laufzeit von Mergesort in jedem Fall $\mathrm{\Theta }(n\lg n)$‍ , und Quicksort läuft in $\mathrm{\Theta }(n\lg n)$‍ sowohl im besten Fall als auch im Durchschnitt. Seine schlechteste Laufzeit ist $\mathrm{\Theta }(n^2)$‍. Hier ist eine Tabelle dieser vier Sortieralgorithmen und ihre jeweiligen Laufzeiten:

Mergesort als auch Quicksort liegt ein gemeinsames algorithmisches Paradigma auf der Grundlage von Rekursion zugrunde. Dieses Paradigma, Teile-und-Herrsche , zerlegt ein Problem in Unterprobleme, die dem ursprünglichen Problem ähnlich sind, löst die Unterprobleme rekursiv und kombiniert schließlich die Lösungen der Unterproblemen, um das ursprüngliche Problem zu lösen. Weil Teile-und-Herrsche Unterprobleme rekursiv löst, muss jedes Unterproblem kleiner sein als das ursprüngliche Problem, und es muss einen Basisfall für Subprobleme geben. Du kannst Dir einen Teile-und-Herrsche Algorithmus als aus drei Teilen bestehend vorstellen:

Du kannst dir leicht die Schritte eines Teile-und-Herrsche Algorithmus merken als: teile, herrsche, kombiniere. Im folgenden zeigen wir einen Schritt, unter der Annahme, dass der Teile-Schritt zwei Subprobleme erzeugt. (Einige Teile-und-Herrsche Algorithmen produzieren mehr als zwei Subprobleme):

Wenn wir die Subprobleme wiederum in Subprobleme unterteilen, und diese wiederum in Subprobleme, erhalten wir:

Weil Teile-und-Herrsche mindestens zwei Subprobleme erzeugt, macht ein Teile-und-Herrsche Algorithmus mehrere rekursive Aufrufe.

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.