Insertionsort: Unterschied zwischen den Versionen
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> |
Aktuelle Version vom 23. Januar 2022, 16:51 Uhr
Diese Seite entspricht dem Abi 17 (und folgenden)
Fachbegriffe
Insertionsort, Liste, Array
Erläuterung des Verfahrens
Insertionsort -> Sortieren durch Einfügen (des ersten Elements des unsortierten Teils an die richtige Stelle des sortierten Teils)
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.
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.
Laufzeit
O(n2), d.h. der Aufwand wächst quadratisch mit der Zahl der zu sortierenden Elemente.
Implementierung
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.
public List<Person> sortierenDurchEinfuegen(List<Person> pList){
List<Person> ergebnis = new List<>();
pList.toFirst();
while(pList.hasAccess()){
Person aktuell = pList.getContent();
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);
}
Insertionsort auf Arrays in Java
Wir gehen davon aus, dass es ein Array mit dem Namen zahlenFeld
gibt, das mit ganzen Zahlen befüllt ist.
// 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;
}