Allgemeines
Der Insertionsort ("Sortieren durch direktes Einfügen") ist ein weiteres einfaches Sortierverfahren. Ähnlich wie beim Selectionsort besteht der zu sortierende Array aus zwei Teilen, dem bereits sortierten Teil und dem noch unsortierten Teil.
Beim Insertionsort wird das erste Arrayelement als bereits sortiert angesehen, der sortierte Teil besteht also aus einem Element, der unsortierte aus dem Rest des Arrays.
Nun wird die erste Zahl des unsortierten Teils genommen (nicht gesucht!) und an der richtigen Position in den bereits sortierten Teil eingefügt. Danach besteht der sortierte Teil aus zwei Zahlen und der unsortierte Teil ist um ein Element geschrumpft.
Im zweiten Durchgang wird das Gleiche gemacht: Nimm die erste Zahl des unsortierten Teils und füge an der richtigen Stelle in den sortierten Teil ein. Danach wächst dieser um 1 und der unsortierte Teil schrumpft um 1.
Das Ganze wird solange wiederholt, bis der gesamte Array sortiert ist.
Im Grunde ist der Insertionsort das Sortierverfahren, das man auch bei vielen Kartenspielen benutzt. Man nimmt zunächst alle Karten in die Hand und breitet sie fächerartig aus. Dann sortiert man die Karten, indem man die jeweils nächste Karte an die richtige Stelle im bereits sortierten Teil steckt.
Übungen
Übung 5.4-1
Erstellen Sie eine kleine Präsentation, die in mehreren Schritten zeigt, wie der Insertionsort funktioniert.
Übung 5.4-2
Betrachten Sie den folgenden Quelltext für einen Insertionsort:
public void insertionSort()
{
for (int i = 1; i < numbers.length; i++)
{
int value = numbers[i];
int pos = i;
while (pos > 0 && numbers[pos - 1] > value)
{
numbers[pos] = numbers[pos - 1];
pos--;
}
numbers[pos] = value;
}
}
Erläutern Sie das genaue Vorgehen dieser Methode unter besonderer Berücksichtigung der while-Schleife.
⇒ Kopieren Sie sich den obigen Quelltext in Ihr Java-Projekt, bringen Sie ihn zum Laufen und ermitteln Sie dann die Sortierzeiten für 1000, 2000, 5000, ... Zahlen und vergleichen Sie die Laufzeit des Insertionsort mit der des Selection- und Bubblesort.
Hinweise zur Zeiterfassung von Algorithmus finden Sie in der Abteilung "Begriffe und Konzepte" im Artikel "Zeiterfassung".
Übung 5.4-3
Laden Sie sich die Klasse ArrayTools herunter und implementieren Sie dann den Insertionsort mithilfe der Methoden dieser Klasse.
Weitere Übungen zur Klasse ArrayTools
Die Klasse ArrayTools soll um weitere Methoden erweitert werden, die man beim Umgang mit int-Arrays immer wieder gebrauchen kann.
Übung 5.4-4
Erweitern Sie die Klasse ArrayTools um folgende Methode:
public static void delete(int[] numbers, int position)
Mit dieser Methode können Sie in einem vorhandenen Array ein Element an der übergebenen Position löschen.
Die Elemente, die sich rechts von dieser Position befinden, rücken dann alle um je eine Position weiter nach links, so dass sich die entstandene Lücke wieder schließt.
Das letzte Arrayelement wird dann mit dem Wert 0 überschrieben. Die Länge des Arrays bleibt bei dieser Aktion bestehen.
Vorher:
4 - 7 - 5 - 9 - 3 // length = 5
Nach Löschen von Position 2
4 - 7 - 9 - 3 - 0 // length = 5
Übung 5.4-5
Erweitern Sie die Klasse ArrayTools um folgende Methode:
public static int[] deleteAndCut(int[] numbers, int position)
Mit dieser Methode können Sie in einem vorhandenen Array ein Element an der übergebenen Position löschen.
Die Elemente, die sich rechts von dieser Position befinden, rücken dann alle um je eine Position weiter nach links, so dass sich die entstandene Lücke wieder schließt.
Der Array wird bei dieser Aktion um ein Element verkürzt, der gekürzte Array wird als Rückgabewert int[] zurückgegeben.
Vorher:
4 - 7 - 5 - 9 - 3 // length = 5
Nach Löschen von Position 2
4 - 7 - 9 - 3 // length = 4
Übung 5.4-6
Erweitern Sie die Klasse ArrayTools um folgende Methode:
public static int[] insertAndGrow(int[] numbers, int value, int position)
Mit dieser Methode können Sie in einem vorhandenen Array ein Element an der übergebenen Position einfügen.
Die Elemente, die sich rechts von dieser Position befinden, rücken dann alle um je eine Position weiter nach rechts.
Der Array wird bei dieser Aktion um ein Element verlängert, der längere Array wird als Rückgabewert int[] zurückgegeben.
Vorher:
4 - 7 - 5 - 9 - 3 // length = 5
Nach Einfügen vo 11 an Position 2
4 - 7 - 11- 5 - 9 - 3 // length = 6
Sie können die drei letzten Übungen mit folgender Testklasse überprüfen:
public class ArrayTest
{
public ArrayTest()
{
int[] zahlen = ArrayTools.create(15,100);
ArrayTools.show(zahlen);
System.out.println("Array wird sortiert");
ArrayTools.sort(zahlen);
ArrayTools.show(zahlen);
System.out.println("Element an Index 0 wird gelöscht");
int[] kurzArray = ArrayTools.deleteAndCut(zahlen,0);
ArrayTools.show(kurzArray);
System.out.println("Element 200 an Index 3 wird eingefügt");
int[] langArray = ArrayTools.insertAndGrow(kurzArray,200, 3);
ArrayTools.show(langArray);
System.out.println("Element 210 an Index 0 wird eingefügt");
langArray = ArrayTools.insertAndGrow(langArray,210, 0);
ArrayTools.show(langArray);
System.out.println("Element 310 wird am Ende eingefügt");
langArray = ArrayTools.insertAndGrow(langArray,310, langArray.length);
ArrayTools.show(langArray);
}
}
Übung 5.4-7
Schreiben Sie nun eine Insertionsort-Methode, die die neuen Methoden von ArrayTools ausnutzt.
Seitenanfang
Weiter mit Suchverfahren ...