Allgemeines
Der Insertionsort ("Sortieren durch direktes Einfügen") ist ein weiteres einfaches Sortierverfahren. Ähnlich wie beim Selectionsort besteht das 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 das 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 8.5-1
- Erstellen Sie ein neues BlueJ-Projekt mit zwei neuen Klassen. Entfernen Sie die vorgegebenen Quelltexte dieser Klassen und kopieren Sie dann über die Zwischenablage (Copy / Paste) die beiden Quelltexte Liste und SortAnw-neu in Ihr Projekt. Bringen Sie das Projekt zum Laufen, indem sie die main()-Methode der Klasse SortAnw mit der rechten Maustaste auswählen. Betrachten Sie das Geschehen, das automatisch abläuft.
- Analysieren Sie nun den Quelltext der Klasse Liste und begründen Sie, warum die Java-Anwendung nicht die Methode insertionSort() einbindet, sondern die Methode insertionSortNextStep(). Was ist der Unterschied zwischen diesen beiden Methoden?
Anmerkung
Die alte Version der Java-Anwendung, die ich im Jahre 2017 geschrieben habe, können Sie sich gerne hier herunterladen. Sie funktioniert zwar noch, ist aber nicht mehr zeitgemäß. Ich habe diese Version nun von ChatGPT überarbeiten und modernisieren lassen; die neue Version läuft wesentlich glatter als die alte, allerdings ist der Quelltext jetzt nicht mehr so übersichtlich wie mein alter, ChatGPT hat sogar einen Lambda-Ausdruck mit eingebaut, den ich selbst noch nicht so ganz verstehe. Das ist auch für das Verständnis des Insertionsort überhaupt nicht nötig.
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu