Insertionsort - Versionsgeschichte

Akaibel am 23. Januar 2022 um 16:51 Uhr

2022-01-23T16:51:09Z

← Nächstältere Version		Version vom 23. Januar 2022, 16:51 Uhr
Zeile 32:		Zeile 32:
	Hier als Beispiel das Sortieren einer Liste, die Personen enthält. Die Personen werden nach dem Alphabet des Namens sortiert.		Hier als Beispiel das Sortieren einer Liste, die Personen enthält. Die Personen werden nach dem Alphabet des Namens sortiert.

	<code>		<code>
	'''public List<Person> sortierenDurchEinfuegen(List<Person> pList){'''		'''public List<Person> sortierenDurchEinfuegen(List<Person> pList){'''
	List<Person> ergebnis = new List<>();		List<Person> ergebnis = new List<>();
Zeile 58:		Zeile 58:
	pList.append(pPerson);		pList.append(pPerson);
	}		}
	</code>		</code>

	== Insertionsort auf Arrays in Java==		== Insertionsort auf Arrays in Java==
	Wir gehen davon aus, dass es ein Array mit dem Namen <code>zahlenFeld</code> gibt, das mit ganzen Zahlen befüllt ist.		Wir gehen davon aus, dass es ein Array mit dem Namen <code>zahlenFeld</code> gibt, das mit ganzen Zahlen befüllt ist.

	<code>		<code>
	// Aeussere Methode, die das Sortieren durchführt.		// Aeussere Methode, die das Sortieren durchführt.
	// Sie nutzt die Hilfsmethode verschiebeNachVorne(int pVonWoAus)		// Sie nutzt die Hilfsmethode verschiebeNachVorne(int pVonWoAus)
Zeile 96:		Zeile 96:
	zahlenFeld[pIndex2] = hilf;		zahlenFeld[pIndex2] = hilf;
	}		}
	</code>		</code>

Akaibel: /* Insertionsort auf Listen in Java */

2019-12-02T11:53:34Z

Insertionsort auf Listen in Java

← Nächstältere Version		Version vom 2. Dezember 2019, 11:53 Uhr
Zeile 33:		Zeile 33:

	<code>		<code>
	public List<Person> sortierenDurchEinfuegen(List<Person> pList){		'''public List<Person> sortierenDurchEinfuegen(List<Person> pList){'''
	List<Person> ergebnis = new List<>();		List<Person> ergebnis = new List<>();
	pList.toFirst();		pList.toFirst();
	while(pList.hasAccess()){		while(pList.hasAccess()){
	Person aktuell = pList.getContent();		Person aktuell = pList.getContent();
	~~this.~~anRichtigerStelleEinfugen(ergebnis, aktuell);		anRichtigerStelleEinfugen(ergebnis, aktuell);
	pList.next();		pList.next();
	}		}
	return ergebnis;		return ergebnis;
	}		}

	public void anRichtigerStelleEinfugen(List<Person> pList, Person pPerson){		'''public void anRichtigerStelleEinfugen(List<Person> pList, Person pPerson){'''
	pList.toFirst();		pList.toFirst();
	while(pList.hasAccess()){		while(pList.hasAccess()){

Akaibel: /* Erläuterung des Verfahrens */

2019-06-23T13:34:24Z

Erläuterung des Verfahrens

← Nächstältere Version		Version vom 23. Juni 2019, 13:34 Uhr
Zeile 5:		Zeile 5:
	[[Kategorie:Sortierverfahren]]		[[Kategorie:Sortierverfahren]]
	<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>		<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>

			=Fachbegriffe=

			Insertionsort, Liste, Array

	=Erläuterung des Verfahrens=		=Erläuterung des Verfahrens=

	'''Insertionsort -> Sortieren durch Einfügen''' (des ersten Elements des unsortierten Teils an die richtige Stelle des sortierten Teils)		'''Insertionsort -> Sortieren durch Einfügen''' (des ersten Elements des unsortierten Teils an die richtige Stelle des sortierten Teils)

Akaibel: Akaibel verschob Seite Insertionsort ab Abi 2017 nach Insertionsort

2016-09-12T14:15:53Z

Akaibel verschob Seite Insertionsort ab Abi 2017 nach Insertionsort

← Nächstältere Version	Version vom 12. September 2016, 14:15 Uhr
(kein Unterschied)

Akaibel am 12. September 2016 um 14:15 Uhr

2016-09-12T14:15:24Z

@@ Zeile 4: / Zeile 4: @@
 [[Kategorie:Informatik-Abitur]]
 [[Kategorie:Sortierverfahren]]
 =Erläuterung des Verfahrens=
 '''Insertionsort -> Sortieren durch Einfügen''' (des ersten Elements des unsortierten Teils an die richtige Stelle des sortierten Teils)
 == Insertionsort auf Arrays ==
@@ Zeile 12: / Zeile 18: @@
 Das Verfahren läuft also ''in place'', d.h. man braucht (anders als bei einfach verketteten Listen) keine Hilfsstruktur.
 =Laufzeit=
@@ Zeile 22: / Zeile 23: @@
 =Implementierung=
 == Insertionsort auf Arrays in Java==
 Wir gehen davon aus, dass es ein Array mit dem Namen <code>zahlenFeld</code> gibt, das mit ganzen Zahlen befüllt ist.
@@ Zeile 58: / Zeile 91: @@
        zahlenFeld[pIndex2] = hilf;
+    }
 </code>

Mgrifka: /* Insertionsort auf Listen in Java */

2016-08-09T08:18:15Z

Insertionsort auf Listen in Java

← Nächstältere Version		Version vom 9. August 2016, 08:18 Uhr
Zeile 64:		Zeile 64:

	<code>		<code>
	public List sortierenDurchEinfuegen(List<Person> pList){		public List<Person> sortierenDurchEinfuegen(List<Person> pList){
	List<Person> ergebnis = new List<>();		List<Person> ergebnis = new List<>();
	pList.toFirst();		pList.toFirst();

Mgrifka: Die Seite wurde neu angelegt: „Kategorie:Informatik Kategorie:Informatik-EF Kategorie:Informatik-Q1 Kategorie:Informatik-Abitur Kategorie:Sortierverfahren =Erläuterung …“

2016-08-09T08:16:04Z

Die Seite wurde neu angelegt: „Kategorie:Informatik Kategorie:Informatik-EF Kategorie:Informatik-Q1 Kategorie:Informatik-Abitur Kategorie:Sortierverfahren =Erläuterung …“

Neue Seite

[[Kategorie:Informatik]]
[[Kategorie:Informatik-EF]]
[[Kategorie:Informatik-Q1]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Sortierverfahren]]

=Erläuterung des Verfahrens=
'''Insertionsort -> Sortieren durch Einfügen''' (des ersten Elements des unsortierten Teils an die richtige Stelle des sortierten Teils)

== Insertionsort auf Arrays ==
Das Array wird von vorne nach hinten durchlaufen. In jedem Schritt wird das aktuell betrachtete Element so weit im bereits sortierten vorderen Teil des Arrays nach vorne geschoben, bis es an der richtigen Stelle steht. Danach wird der nächste Eintrag betrachtet. Auf diese Weise wächst der bereits sortierte vordere Teil des Arrays in jedem Schritt um eins, bis am Ende das ganze Array sortiert ist.

Das Verfahren läuft also ''in place'', d.h. man braucht (anders als bei einfach verketteten Listen) keine Hilfsstruktur.

== Insertionsort auf Listen ==
Bei Insertionsort wird die Ergebnisliste nach und nach aufgebaut.

Dazu wird jeweils das erste Element aus der ursprünglichen Liste genommen und gelöscht. Dann wird die Ergebnisliste von vorne bis zu der Stelle durchlaufen, an der das Element eingefügt werden muss; da wird es dann eingefügt.

=Laufzeit=
O(n<sup>2</sup>), d.h. der Aufwand wächst quadratisch mit der Zahl der zu sortierenden Elemente.

=Implementierung=
== Insertionsort auf Arrays in Java==
Wir gehen davon aus, dass es ein Array mit dem Namen <code>zahlenFeld</code> gibt, das mit ganzen Zahlen befüllt ist.

<code>
// Aeussere Methode, die das Sortieren durchführt.
// Sie nutzt die Hilfsmethode verschiebeNachVorne(int pVonWoAus)
public void insertionSort()
{
for(int i = 0; i < zahlenFeld.length; i++)
{
verschiebeNachVorne(i);
}
}

// Hilfsmethode, die eine Zahl ab der Stelle pVonWoAus so weit nach vorne im Array tauscht, bis
// sie an der richtigen Stelle steht.
// Sie nutzt die Hilfsmethode vertauschen(int pIndex1, int pIndex2), die
// zwei Arrayeinträge vertauscht.
private void verschiebeNachVorne(int pVonWoAus)
{
for(int j = pVonWoAus; j > 0; j--)
{
if( zahlenFeld[j] < zahlenFeld[j-1] )
{
vertauschen(j,j-1);
}
}
}

// Die Hilfsmethode vertauscht die beiden Arrayeinträge mit den Indices pIndex1 und pIndex2
private void vertauschen(int pIndex1, int pIndex2)
{
int hilf = zahlenFeld[pIndex1];
zahlenFeld[pIndex1] = zahlenFeld[pIndex2];
zahlenFeld[pIndex2] = hilf;
}
</code>

== Insertionsort auf Listen in Java==
Hier als Beispiel das Sortieren einer Liste, die Personen enthält. Die Personen werden nach dem Alphabet des Namens sortiert.

<code>
public List sortierenDurchEinfuegen(List<Person> pList){
List<Person> ergebnis = new List<>();
pList.toFirst();
while(pList.hasAccess()){
Person aktuell = pList.getContent();
this.anRichtigerStelleEinfugen(ergebnis, aktuell);
pList.next();
}
return ergebnis;
}

public void anRichtigerStelleEinfugen(List<Person> pList, Person pPerson){
pList.toFirst();
while(pList.hasAccess()){
Person aktuell = pList.getContent();
// pPerson mit der aktuellen person vergleichen
if(pPerson.getName().compareTo(aktuell.getName()) < 0){
pList.insert(pPerson);
return;
}
pList.next();
}
// pPerson wurde noch nicht eingefuegt!
pList.append(pPerson);
}
</code>