Insertion-sort: Unterschied zwischen den Versionen

(8 dazwischenliegende Versionen von einem anderen Benutzer werden nicht angezeigt)

Zeile 1:

Einführung

== Einführung ==

Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist ~~relative~~ simpel. Das Prinzip von Insertion Sort ist: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links ~~weitergereicht~~ – und ~~das~~ so lange, bis das ~~bewegte~~ Element größer oder gleich dem Element ist, das an der ~~im Augenblick abgefragten~~ Position ~~liegt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm)~~.

Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist relativ simpel. Das Prinzip von Insertion Sort ist folgendes: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links verschoben – und zwar so lange, bis das einzufügende Element größer oder gleich dem Element ist, das an der aktuell betrachteten Position steht.

Der Platz für das Element, das verschoben wird, ist frei. Diese Lücke wird mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

Der Platz für das Element, das verschoben wird, ist währenddessen frei. Diese Lücke wird anschließend mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

== Beispiel ==

[[Datei:Animation Insertio-Sort.gif|mini]]

Die folgende Tabelle zeigt die ~~Sortierschritte~~ zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite grün dargestellt befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links ~~gewandert ist~~. Das aktuell eingefügte Element ist fett markiert. ~~(http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertion.htm).~~

Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite (grün dargestellt) befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links verschoben wurde. Das aktuell eingefügte Element ist fett markiert.

{| class="wikitable" style="text-align:center; font-family:monospace;"

|-

Zeile 25:

Zeile 26:

| 0 || '''''1''''' || 2 || 3 || 4 || 5 || 6 || 7 || (6)

|}

~~== Pseudo Code ==~~

~~Der Algorithmus sieht im Pseudocode so aus:~~

~~<syntaxhighlighting>~~

~~prozedur INSERTIONSORT(A ist Liste sortierbarer Elemente)~~

~~wiederhole bis zur~~ Länge von A und ~~beginne beim~~ 2. ~~Element~~

== Pseudocode ==

Der [[Algorithmus]] sieht im Pseudocode so aus:

prozedur insertionSort(A ist Liste sortierbarer Elemente)

n = Länge von A

für i von 1 bis n - 1 wiederhole

einzusortierenderWert = A[i]

j = i - 1

solange j ≥ 0 und A[j] > einzusortierenderWert wiederhole

A[j + 1] = A[j]

j = j - 1

ende solange

A[j + 1] = einzusortierenderWert

ende für

ende prozedur

</syntaxhighlight>

== Komplexität ==

=== Worst Case ===

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

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

~~einzusortierender_wert~~ = ~~A an der Stelle i~~

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.

~~j = i~~

Die Gesamtanzahl der Vergleiche ergibt sich zu:

~~wiederhole solange j~~ > 1 ~~und A an der Stelle j~~-1 > ~~einzusortierender_wert~~

~~A an~~ der ~~Stelle j = A an der Stelle j-1~~

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

~~j = j −~~ 1

~~ende wiederhole~~

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

~~A an~~ der ~~Stelle j = einzusortierender_wert~~

=== 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.

~~ende wiederhole~~

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

~~ende prozedur~~

[[Kategorie:Programmierung]]

~~</syntaxhighlighting>~~

[[Kategorie:AHR_I_Informatik_LK]]

[[Kategorie:FI_I_TP2]]

@@ Zeile 1: / Zeile 1: @@
-Einführung
+== Einführung ==
-Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist relative simpel. Das Prinzip von Insertion Sort ist: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links weitergereicht – und das so lange, bis das bewegte Element größer oder gleich dem Element ist, das an der im Augenblick abgefragten Position liegt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).
+Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist relativ simpel. Das Prinzip von Insertion Sort ist folgendes: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links verschoben – und zwar so lange, bis das einzufügende Element größer oder gleich dem Element ist, das an der aktuell betrachteten Position steht.
-Der Platz für das Element, das verschoben wird, ist frei. Diese Lücke wird mit dem entsprechenden Wert an der richtigen Stelle gefüllt.
+Der Platz für das Element, das verschoben wird, ist währenddessen frei. Diese Lücke wird anschließend mit dem entsprechenden Wert an der richtigen Stelle gefüllt.
 == Beispiel ==
 [[Datei:Animation Insertio-Sort.gif|mini]]
-Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite grün dargestellt befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links gewandert ist. Das aktuell eingefügte Element ist fett markiert. (http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertion.htm).
+Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite (grün dargestellt) befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links verschoben wurde. Das aktuell eingefügte Element ist fett markiert.
 {| class="wikitable" style="text-align:center; font-family:monospace;"
 |-
@@ Zeile 25: / Zeile 26: @@
 | <span style="color:green;">0</span> || '''''<span style="color:green;">1</span>''''' || <span style="color:green;">2</span> || <span style="color:green;">3</span> || <span style="color:green;">4</span> || <span style="color:green;">5</span> || <span style="color:green;">6</span> || <span style="color:green;">7</span> || (6)
 |}
-== Pseudo Code ==
-Der Algorithmus sieht im Pseudocode so aus:
-<syntaxhighlighting>
-prozedur INSERTIONSORT(A ist Liste sortierbarer Elemente)
-wiederhole bis zur Länge von A und beginne beim 2. Element
+== Pseudocode ==
+Der [[Algorithmus]] sieht im Pseudocode so aus:
+<syntaxhighlight lang="text">
+prozedur insertionSort(A ist Liste sortierbarer Elemente)
+    n = Länge von A
+    für i von 1 bis n - 1 wiederhole
+        einzusortierenderWert = A[i]
+        j = i - 1
+        solange j ≥ 0 und A[j] > einzusortierenderWert wiederhole
+            A[j + 1] = A[j]
+            j = j - 1
+        ende solange
+        A[j + 1] = einzusortierenderWert
+    ende für
+ende prozedur
+</syntaxhighlight>
+== Komplexität ==
+=== Worst Case ===
+Eine Liste in umgekehrter Reihenfolge stellt das Worst-Case-Szenario für InsertionSort dar:
+<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.
-einzusortierender_wert = A an der Stelle i
+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.
-j = i
+Die Gesamtanzahl der Vergleiche ergibt sich zu:
-wiederhole solange j > 1 und A an der Stelle j-1 > einzusortierender_wert
+<math>1 + 2 + 3 + \dots + (n - 1)</math>
-A an der Stelle j = A an der Stelle j-1
+Dies ist eine [[Arithmetische-reihe|arithmetische Reihe]]. Mit der gaußschen Summenformel erhält man:
-j = j − 1
+<math>\frac{n(n-1)}{2}</math>
-ende wiederhole
+Für große n dominiert der quadratische Term, sodass InsertionSort im Worst Case in der Komplexitätsklasse <math>O(n^2)</math> liegt.
-A an der Stelle j = einzusortierender_wert
+=== 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.
-ende wiederhole
+InsertionSort besitzt im Best Case daher eine lineare Laufzeit von <math>O(n)</math>.
-ende prozedur
+[[Kategorie:Programmierung]]
-</syntaxhighlighting>
+[[Kategorie:AHR_I_Informatik_LK]]
+[[Kategorie:FI_I_TP2]]