Allgemeines
Der Insertionsort ("Sortieren durch direktes Einfügen") ist ein einfaches Sortierverfahren. Der Array A besteht aus zwei Teilen, dem bereits sortierten Teil und dem noch unsortierten Teil. Beim Insertionsort wird das erste Arrayelement als bereits sortiert angesehen, der sortierte Tei 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.
Ein einfaches selbst erstelltes Video demonstriert den Insertionsort.
Ü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 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?
- Analysieren Sie die paint()-Methode der Klasse Liste und erläutern Sie, wie sie funktioniert.
- Java-Anwendungen kennen Sie bereits aus Folge 5. Was ist an dieser speziellen Java-Anwendung neu, und wie funktioniert das eigentlich, diese neue Sache?
Falls Sie das Programm nicht zum Laufen bekommen, hier ist ein kleines Quicktime-Video, welches das ablaufende Programm zeigt.