Insertionsort: Unterschied zwischen den Versionen

(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)

Zeile 46:

== Komplexität ==

=== Best Case ===

Die optimale Eingabe ist ein bereits sortiertes [[Array]]. In diesem Fall wird pro Iteration lediglich ein Vergleich durchgeführt, und die innere Schleife wird nie betreten. Die Gesamtanzahl der Vergleiche ist somit proportional zur Anzahl der Elemente <math>n</math>.

Insertion Sort besitzt im Best Case daher eine lineare Laufzeit von <math>O(n)</math>.

=== Average Case ===

Das Average-Case-Szenario geht von einer zufälligen Verteilung der Werte in der Liste aus.

Im Durchschnitt ist das aktuell betrachtete Element kleiner als die Hälfte der bereits sortierten Elemente. Die innere Schleife muss das Element also im Mittel nur bis in die Mitte des bisher sortierten Teilbereichs verschieben. Die Anzahl der Vergleiche und Verschiebungen halbiert sich im Vergleich zum Worst Case dadurch in etwa.

Da in der asymptotischen Landau-Notation konstante Faktoren (wie diese Halbierung) ignoriert werden, dominiert weiterhin die höchste Potenz das Wachstum. Die Zeitkomplexität liegt im Average Case demnach bei <math>O(n^2)</math>.

=== Worst Case ===

Eine Liste in umgekehrter Reihenfolge stellt das Worst-Case-Szenario für ~~InsertionSort~~ dar:

Eine Liste in umgekehrter (absteigender) Reihenfolge stellt das Worst-Case-Szenario für Insertion Sort dar, beispielsweise:

Wir betrachten nur die Vergleichsoperationen, die mit der Variablen c gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt n.

Wir betrachten nur die Vergleichsoperationen, die mit der Variablen <math>c</math> gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt <math>n</math>.

Beim ersten äußeren Schleifendurchlauf ist c = 1, da nur ein Vergleich durchgeführt wird. Beim zweiten Durchlauf sind es 2 Vergleiche, beim dritten 3 usw., bis zum letzten Durchlauf mit ~~n−1~~ Vergleichen.

Beim ersten äußeren Schleifendurchlauf ist <math>c = 1</math>, da nur ein Vergleich durchgeführt wird. Beim zweiten Durchlauf sind es 2 Vergleiche, beim dritten 3 usw., bis zum letzten Durchlauf mit <math>n - 1</math> Vergleichen.

Die Gesamtanzahl der Vergleiche ergibt sich zu:

Zeile 60:

Zeile 72:

Dies ist eine [[~~Arithmetische-reihe~~|arithmetische Reihe]]. Mit der gaußschen Summenformel erhält man:

Dies ist eine [[Arithmetische_Reihe|arithmetische Reihe]]. Mit der gaußschen Summenformel erhält man:

Für große n dominiert der quadratische Term, sodass ~~InsertionSort~~ im Worst Case in der Komplexitätsklasse <math>O(n^2)</math> liegt.

Für große <math>n</math> dominiert der quadratische Term, sodass Insertion Sort im Worst Case in der Komplexitätsklasse <math>O(n^2)</math> liegt.

~~=== Best Case ===~~

~~Die optimale Eingabe ist ein bereits sortiertes [[Array]]. In diesem Fall wird pro Iteration lediglich ein Vergleich durchgeführt. Die Gesamtanzahl der Vergleiche ist somit proportional zu n.~~

~~InsertionSort besitzt im Best Case daher eine lineare Laufzeit von <math>O(n)</math>~~.

[[Kategorie:Programmierung]]

[[Kategorie:AHR_I_Informatik_LK]]

[[Kategorie:FI_I_TP2]]

@@ Zeile 46: / Zeile 46: @@
 == Komplexität ==
+=== Best Case ===
+Die optimale Eingabe ist ein bereits sortiertes [[Array]]. In diesem Fall wird pro Iteration lediglich ein Vergleich durchgeführt, und die innere Schleife wird nie betreten. Die Gesamtanzahl der Vergleiche ist somit proportional zur Anzahl der Elemente <math>n</math>.
+Insertion Sort besitzt im Best Case daher eine lineare Laufzeit von <math>O(n)</math>.
+=== Average Case ===
+Das Average-Case-Szenario geht von einer zufälligen Verteilung der Werte in der Liste aus.
+Im Durchschnitt ist das aktuell betrachtete Element kleiner als die Hälfte der bereits sortierten Elemente. Die innere Schleife muss das Element also im Mittel nur bis in die Mitte des bisher sortierten Teilbereichs verschieben. Die Anzahl der Vergleiche und Verschiebungen halbiert sich im Vergleich zum Worst Case dadurch in etwa.
+Da in der asymptotischen Landau-Notation konstante Faktoren (wie diese Halbierung) ignoriert werden, dominiert weiterhin die höchste Potenz das Wachstum. Die Zeitkomplexität liegt im Average Case demnach bei <math>O(n^2)</math>.
 === Worst Case ===
-Eine Liste in umgekehrter Reihenfolge stellt das Worst-Case-Szenario für InsertionSort dar:
+Eine Liste in umgekehrter (absteigender) Reihenfolge stellt das Worst-Case-Szenario für Insertion Sort dar, beispielsweise:
-<math>[11,7,5,3,2,0]</math>
+<math>[11, 7, 5, 3, 2, 0]</math>
-Wir betrachten nur die Vergleichsoperationen, die mit der Variablen c gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt n.
+Wir betrachten nur die Vergleichsoperationen, die mit der Variablen <math>c</math> gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt <math>n</math>.
-Beim ersten äußeren Schleifendurchlauf ist c = 1, da nur ein Vergleich durchgeführt wird. Beim zweiten Durchlauf sind es 2 Vergleiche, beim dritten 3 usw., bis zum letzten Durchlauf mit n−1 Vergleichen.
+Beim ersten äußeren Schleifendurchlauf ist <math>c = 1</math>, da nur ein Vergleich durchgeführt wird. Beim zweiten Durchlauf sind es 2 Vergleiche, beim dritten 3 usw., bis zum letzten Durchlauf mit <math>n - 1</math> Vergleichen.
 Die Gesamtanzahl der Vergleiche ergibt sich zu:
@@ Zeile 60: / Zeile 72: @@
 <math>1 + 2 + 3 + \dots + (n - 1)</math>
-Dies ist eine [[Arithmetische-reihe|arithmetische Reihe]]. Mit der gaußschen Summenformel erhält man:
+Dies ist eine [[Arithmetische_Reihe|arithmetische Reihe]]. Mit der gaußschen Summenformel erhält man:
 <math>\frac{n(n-1)}{2}</math>
-Für große n dominiert der quadratische Term, sodass InsertionSort im Worst Case in der Komplexitätsklasse <math>O(n^2)</math> liegt.
+Für große <math>n</math> dominiert der quadratische Term, sodass Insertion Sort im Worst Case in der Komplexitätsklasse <math>O(n^2)</math> liegt.
-=== Best Case ===
-Die optimale Eingabe ist ein bereits sortiertes [[Array]]. In diesem Fall wird pro Iteration lediglich ein Vergleich durchgeführt. Die Gesamtanzahl der Vergleiche ist somit proportional zu n.
-InsertionSort besitzt im Best Case daher eine lineare Laufzeit von <math>O(n)</math>.
 [[Kategorie:Programmierung]]
 [[Kategorie:AHR_I_Informatik_LK]]
 [[Kategorie:FI_I_TP2]]