Insertionsort: Unterschied zwischen den Versionen

Zeile 40:

ende prozedur

</syntaxhighlight >

== Komplexität ==

=== Worst Case ===

Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

[11,7,5,3,2,0]

Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n.

Beim ersten äußeren Schleifendurchlauf ist c = 1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe oben) der Datenstruktur. Beim zweiten Durchlauf der äußeren Schleife benötigen wir zwei Vergleiche , c = 2. Beim dritte Mal, c = 3 bis zum letzten Mal, wenn c = n-1. Es gilt also:

c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))

Hierbei handelt es sich um eine arithmetische Reihe, mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für arithmetische Reihen, erhalten wir:

c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2

Für sehr große n können wir den niederwertigen Term cn/2 und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

Der InsertionSort liegt hier in der Komplexitätsklasse O(n2)

=== Best Case ===

Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. O(n)). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen.

@@ Zeile 40: / Zeile 40: @@
 ende prozedur
 </syntaxhighlight >
+== Komplexität ==
+=== Worst Case ===
+Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:
+[11,7,5,3,2,0]
+Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n.
+Beim ersten äußeren Schleifendurchlauf ist c = 1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe oben) der Datenstruktur.  Beim zweiten Durchlauf der äußeren Schleife benötigen wir zwei Vergleiche , c = 2. Beim dritte Mal, c = 3 bis zum letzten Mal, wenn c = n-1. Es gilt also:
+c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))
+Hierbei handelt es sich um eine arithmetische Reihe, mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für arithmetische Reihen, erhalten wir:
+c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2
+Für sehr große n können   wir den niederwertigen Term cn/2  und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:
+Der InsertionSort liegt hier in der  Komplexitätsklasse O(n2)
+=== Best Case ===
+Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. O(n)). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen.