Analyse des Insertionsort

Genauso wie Selectionsort iteriert auch Insertionsort über die Indizes des Arrays. Es wendet einfach insert auf die Elemente an den Indizes $1, 2, 3, \ldots, n-1$1, comma, 2, comma, 3, comma, dots, comma, n, minus, 1 an . So wie jeder Aufruf von indexOfMinimum eine bestimmte Zeit in Anspruch nahm, die von der Größe des zu sortierenden Subarrays abhing, so dauert entsprechend jeder Aufruf von insert eine bestimmte Zeit. Wir werden im folgenden sehen, warum die Laufzeit von Insertionsort unterschiedliche Größenordnungen annehmen kann.

Wir betrachten nun den Fall in dem wir insert aufrufen, um einen Wert ins Subarray einzufügen, der kleiner ist als alle im Subarray enthaltenen Elemente. Zum Beispiel, wenn wir 0 in das Subarray [2, 3, 5, 7, 11] einfügen, dann muss jedes Element im Subarray eine Position nach rechts rücken. Als Verallgemeinerung: Wenn wir in ein Subarray, bestehend aus $k$k Elementen, einen Wert einfügen, werden bis zu $k$k Elemente um eine Position verschoben. Anstatt zu zählen, wie viele Zeilen Code wir benötigen, um ein Element gegen einen Schlüssel zu testen und das Element zu verschieben, nehmen wir einfach an, dass dafür eine konstante Anzahl von Codezeilen gebraucht wird. Nennen wir die Konstante einfach $c$c. Daher könnten bis zu $c \cdot k$c, dot, k Zeilen Code benötigt werden, um einen Wert in ein Subarray der Größe $k$k einzufügen.

Angenommen, bei jedem Aufruf von insert ist der einzufügende Wert kleiner als jedes Element im Subarray zu seiner Linken. Wenn wir insertdas erste Mal aufrufen, dann ist $k = 1$k, equals, 1. Beim zweiten Mal ist $k = 2$k, equals, 2, beim dritten Mal ist $k = 3$k, equals, 3 und so weiter, bis zum letzten Mal, wenn $k = n-1$k, equals, n, minus, 1 ist. Daher ist die benötigte Gesamtzeit, die man zum Einfügen in ein Subarrays benötigt

$c \cdot 1 + c \cdot 2 + c \cdot 3 + \cdots c \cdot (n-1) = c \cdot (1 + 2 + 3 + \cdots + (n-1))$c, dot, 1, plus, c, dot, 2, plus, c, dot, 3, plus, \@cdots, c, dot, left parenthesis, n, minus, 1, right parenthesis, equals, c, dot, left parenthesis, 1, plus, 2, plus, 3, plus, \@cdots, plus, left parenthesis, n, minus, 1, right parenthesis, right parenthesis .

Diese Summe ist eine arithmetische Reihe, die allerdings nur bis zu $n-1$n, minus, 1 anstatt $n$n geht. Mit unserer Formel für Arithmetische Reihen (siehe Selectionsort), erhalten wir die Gesamtdauer des Einfügens in sortierte Subarrays

$c \cdot (n-1+1)((n-1)/2) = cn^2/2 - cn/2$c, dot, left parenthesis, n, minus, 1, plus, 1, right parenthesis, left parenthesis, left parenthesis, n, minus, 1, right parenthesis, slash, 2, right parenthesis, equals, c, n, squared, slash, 2, minus, c, n, slash, 2 .

Wenn wir die Big-Θ Notation verwenden, dann dürfen wir den niederwertigen Term $cn/2$c, n, slash, 2, sowie die konstanten Faktoren $c$c und 1/2 verwerfen, so dass in diesem Fall im Ergebnis die Laufzeit von Insertionsort $\Theta (n^2)$\Theta, left parenthesis, n, squared, right parenthesis ist.

Die Frage ist nun, ob Insertionsort weniger Zeit als $\Theta (n^2)$\Theta, left parenthesis, n, squared, right parenthesis in Anspruch nehmen könnte? Die Antwort darauf ist ja. Angenommen, wir haben das Array [2, 3, 5, 7, 11], wobei das sortierte Subarray die ersten vier Elemente darstellt und die Zahl 11 den einzufügenden Wert repräsentiert. Beim ersten Vergleich stellen wir fest, dass 11 größer als 7 ist, und so müssen keine Elemente im Subarray nach rechts verschoben werden. Dann dauert dieser Aufruf von insert nur eine konstante Zeit. Angenommen, dass jeder Aufruf von insert eine konstante Zeit dauert. Weil es $n-1$n, minus, 1 Anrufe von insert gibt, und jeder Anruf eine konstante Zeit $c$c dauert, dann ist die Gesamtzeit für Insertionsort gleich $c \cdot (n-1)$c, dot, left parenthesis, n, minus, 1, right parenthesis, das ist $\Theta (n)$\Theta, left parenthesis, n, right parenthesis, statt $\Theta (n ^ 2)$\Theta, left parenthesis, n, squared, right parenthesis.

Könnte eine dieser Situationen in der Realität auftreten? Könnte also jeder Aufruf von insert dazu führen, dass jedes Element im Subarray eine Position nach rechts wandert? Und könnte jeder Aufruf von insert zu gar keiner Verschiebung führen? Beide Fragen können bejaht werden. Zur ersten Frage: Wenn ein Array in umgekehrt-sortierter Reihenfolge vorliegt, wie z.B. [11, 7, 5, 3, 2], dann bewirkt jeder Aufruf von insert, dass jedes einzufügende Element (der Schlüssel) kleiner ist als jedes Element im Subarray zu seiner Linken. Wenn also jeder Schlüssel kleiner ist als jedes Element zu seiner Linken, dann ist die Laufzeit von Insertionsort $\Theta (n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Damit ist ein umgekehrt-sortiertes Array ein Worst-Case für Insertionsort.

Wie verhält es sich mit der zweiten Frage: Könnte jeder Aufruf von insert dazu führen, dass keine Elemente verschoben wird? Das ist ja der Fall, wenn der Schlüssel größer oder gleich jedem Element zu seiner Linken ist. Dann ist die Laufzeit von Insertionsort $\Theta (n)$\Theta, left parenthesis, n, right parenthesis. Dieser Fall tritt auf, wenn das Array bereits sortiert ist, und damit ist ein bereits sortiertes Array der Best-Case für Insertionsort.

Was können wir sonst noch über die Laufzeit von Insertionsort herausfinden? Angenommen, das Array enthält Werte in einer zufälligen Reihenfolge. Dann würden wir im Durchschnitt erwarten, dass in der Hälfte der Fälle der Schlüssel kleiner als die Elemente zu seiner Linken ist. In diesem Fall würde ein Aufruf von insert auf ein Subarray von $k$k -Elementen $k/2$k, slash, 2 davon verschieben. Die Laufzeit wäre also die Hälfte der Worst-Case Laufzeit. Aber in der asymptotischen Notation, in der konstante Koeffizienten keine Rolle spielen, wäre die Laufzeit im durchschnittlichen Fall immer noch $\Theta (n^2)$\Theta, left parenthesis, n, squared, right parenthesis, genau wie im Worst-Case.

Was wäre, wenn man wüsste, dass das Array "fast sortiert" ist? Jedes Element ist fast am richtigen Platz, und nur eine konstante Anzahl von Positionen, z.B. 17 Positionen, vom richtigen Platz entfernt? Dann verschiebt jeder Aufruf zu insert höchstens 17 Elemente, und die benötigte Zeit für einen Aufruf von insert auf ein Subarray von $k$k Elementen wäre höchstens $17 \cdot c$17, dot, c. Für alle $n-1$n, minus, 1 Anrufe von insert wäre dann die Laufzeit $17 \cdot c \cdot (n-1)$17, dot, c, dot, left parenthesis, n, minus, 1, right parenthesis, das ist $\Theta (n)$\Theta, left parenthesis, n, right parenthesis, genau wie der Best-Case. Damit ist Insertionsort schnell, wenn ein fast sortiertes Array gegeben ist.

Fassen wir die Laufzeitbetrachtung von Insertionsort zusammen:

Die generelle Aussage, die für alle Fälle von Insertionsort gilt, lautet, dass sie $O (n ^ 2)$O, left parenthesis, n, squared, right parenthesis Zeit benötigt (wir geben also die obere Schranke an). Wir können nicht sagen, dass sie in allen Fällen in $\Theta (n ^ 2)$\Theta, left parenthesis, n, squared, right parenthesis Zeit läuft, da der Best-Case $\Theta (n)$\Theta, left parenthesis, n, right parenthesis ist. Und wir können auch nicht behaupten, dass sie immer $\Theta (n)$\Theta, left parenthesis, n, right parenthesis ist, da die Worst-Case Laufzeit $\Theta (n ^ 2)$\Theta, left parenthesis, n, squared, right parenthesis ist.

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.