Insertionsort - Versionsgeschichte

Flbkwikiadmin: Flbkwikiadmin verschob die Seite Insertion-sort nach Insertionsort

2026-04-28T08:52:09Z

Flbkwikiadmin verschob die Seite Insertion-sort nach Insertionsort

← Nächstältere Version		Version vom 28. April 2026, 10:52 Uhr
(kein Unterschied)

Flbkwikiadmin am 28. April 2026 um 08:48 Uhr

2026-04-28T08:48:13Z

← Nächstältere Version		Version vom 28. April 2026, 10:48 Uhr
Zeile 46:		Zeile 46:

	== Komplexität ==		== 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 ===		=== 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:		Die Gesamtanzahl der Vergleiche ergibt sich zu:
Zeile 64:		Zeile 76:
	<math>\frac{n(n-1)}{2}</math>		<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:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]
	[[Kategorie:FI_I_TP2]]		[[Kategorie:FI_I_TP2]]

Flbkwikiadmin am 2. März 2026 um 11:30 Uhr

2026-03-02T11:30:11Z

← Nächstältere Version		Version vom 2. März 2026, 13:30 Uhr
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 ==		== Beispiel ==
	[[Datei:Animation Insertio-Sort.gif\|mini]]		[[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;"		{\| 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)		\| <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~~ ==
			== Pseudocode ==
	Der [[Algorithmus]] sieht im Pseudocode so aus:		Der [[Algorithmus]] sieht im Pseudocode so aus:
	<syntaxhighlight ~~line~~>
	prozedur ~~INSERTIONSORT~~(A ist Liste sortierbarer Elemente)		<syntaxhighlight lang="text">
	~~wiederhole bis zur~~ Länge von A ~~und beginne beim 2. Element~~		prozedur insertionSort(A ist Liste sortierbarer Elemente)
	~~einzusortierender_wert~~ = A ~~an der Stelle~~ i		n = Länge von A
	j = i		für i von 1 bis n - 1 wiederhole
	~~wiederhole~~ solange j ~~> 1~~ und A ~~an der Stelle~~ j-1 > ~~einzusortierender_wert~~		einzusortierenderWert = A[i]
	A ~~an der Stelle~~ j = A ~~an der Stelle~~ j-1		j = i - 1
	j = j − 1		solange j ≥ 0 und A[j] > einzusortierenderWert wiederhole
	ende ~~wiederhole~~		A[j + 1] = A[j]
	A ~~an der Stelle~~ j = ~~einzusortierender_wert~~		j = j - 1
	ende ~~wiederhole~~		ende solange
			A[j + 1] = einzusortierenderWert
			ende für
	ende prozedur		ende prozedur
	</syntaxhighlight >		</syntaxhighlight>

	== Komplexität ==		== Komplexität ==

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

	<math>[11,7,5,3,2,0]</math>		<math>[11,7,5,3,2,0]</math>

	Wir betrachten nur die Vergleichsoperationen, die ~~wir~~ mit der ~~Variable~~ c ~~messen~~. Die Anzahl der zu sortierenden Elemente ~~ist entspricht~~ n.		Wir betrachten nur die Vergleichsoperationen, die mit der Variablen c gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt 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:~~		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.

	~~<math>c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))</math>~~		Die Gesamtanzahl der Vergleiche ergibt sich zu:

	~~Hierbei handelt es sich um eine [[Arithmetische-reihe\|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu~~ n-1 ~~anstatt n ansteigt. Unter Verwendung unserer Formel für [[Arithmetische-reihe\|arithmetische Reihen]], erhalten wir:~~		<math>1 + 2 + 3 + \dots + (n - 1)</math>

	~~<math>c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2</math>~~		Dies ist eine [[Arithmetische-reihe\|arithmetische Reihe]]. Mit der gaußschen Summenformel erhält man:

	~~Für sehr große n können wir den niederwertigen Term~~ <math>~~cn/~~2 </math> ~~und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:~~		<math>\frac{n(n-1)}{2}</math>

	~~Der~~ InsertionSort ~~liegt hier~~ in der Komplexitätsklasse <math>O(~~n2~~)</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.

	=== Best Case ===		=== Best Case ===
	Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall ~~hat Insertion Sort~~ eine lineare Laufzeit ~~(d. h.~~ <math>O(n)</math>~~). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen~~.		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:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]
	[[Kategorie:FI_I_TP2]]		[[Kategorie:FI_I_TP2]]

Thomas: /* Komplexität */

2026-02-20T10:59:10Z

Komplexität

← Nächstältere Version		Version vom 20. Februar 2026, 12:59 Uhr
Zeile 63:		Zeile 63:
	=== Best Case ===		=== Best Case ===
	Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. <math>O(n)</math>). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen.		Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. <math>O(n)</math>). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen.

			[[Kategorie:Programmierung]]
			[[Kategorie:AHR_I_Informatik_LK]]
			[[Kategorie:FI_I_TP2]]

Thomas: /* Pseudo Code */

2026-02-20T07:44:57Z

Pseudo Code

← Nächstältere Version		Version vom 20. Februar 2026, 09:44 Uhr
Zeile 26:		Zeile 26:
	\|}		\|}
	== Pseudo Code ==		== Pseudo Code ==
	Der Algorithmus sieht im Pseudocode so aus:		Der [[Algorithmus]] sieht im Pseudocode so aus:
	<syntaxhighlight line>		<syntaxhighlight line>
	prozedur INSERTIONSORT(A ist Liste sortierbarer Elemente)		prozedur INSERTIONSORT(A ist Liste sortierbarer Elemente)

Thomas: /* Best Case */

2026-02-18T13:39:29Z

Best Case

← Nächstältere Version		Version vom 18. Februar 2026, 15:39 Uhr
Zeile 62:		Zeile 62:

	=== Best Case ===		=== 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.		Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. <math>O(n)</math>). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen.

Thomas: /* Worst Case */

2026-02-18T13:39:13Z

Worst Case

← Nächstältere Version		Version vom 18. Februar 2026, 15:39 Uhr
Zeile 57:		Zeile 57:
	<math>c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2</math>		<math>c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2</math>

	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:		Für sehr große n können wir den niederwertigen Term <math>cn/2 </math> und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

	Der InsertionSort liegt hier in der Komplexitätsklasse O(n2)		Der InsertionSort liegt hier in der Komplexitätsklasse <math>O(n2)</math>

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

Thomas: /* Worst Case */

2026-02-18T13:38:29Z

Worst Case

← Nächstältere Version		Version vom 18. Februar 2026, 15:38 Uhr
Zeile 45:		Zeile 45:
	Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:		Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

	[11,7,5,3,2,0]		<math>[11,7,5,3,2,0]</math>

	Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n.		Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n.
Zeile 51:		Zeile 51:
	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:		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))		<math>c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))</math>

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

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

	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:		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:

Thomas: /* Komplexität */

2026-02-18T13:37:46Z

Komplexität

← Nächstältere Version		Version vom 18. Februar 2026, 15:37 Uhr
Zeile 53:		Zeile 53:
	c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))		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:		Hierbei handelt es sich um eine [[Arithmetische-reihe\|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für [[Arithmetische-reihe\|arithmetische Reihen]], erhalten wir:

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

Thomas am 18. Februar 2026 um 13:32 Uhr

2026-02-18T13:32:39Z

← Nächstältere Version		Version vom 18. Februar 2026, 15:32 Uhr
Zeile 40:		Zeile 40:
	ende prozedur		ende prozedur
	</syntaxhighlight >		</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.