Insertion Sort

Während Selection Sort jeweils alle noch nicht bearbeiteten Elemente betrachtet hat, um das kleinste zu finden, orientiert sich Insertion Sort nach links: Es betrachtet jeweils ein Element und rückt dieses dann so weit nach links, bis es an seiner korrekten Position innerhalb der bislang betrachteten Elemente gelandet ist.

Beispiel

Für die Zeichenkette „ZEBRASSINDGELB“ sieht das dann folgendermaßen aus:

(A1)

Implementiere im Bluej-Projekt https://codeberg.org/qg-info-unterricht/algs4-sort-bluej Selectionsort.

Erzeuge mithilfe der draw-Methode eine Veranschaulichung des Sortiervorgangs wie im Bild oben. Du musst dazu die etwas angepasste Methode drawInsertion nutzen, um die Färbung für Insertionsort korrekt zu erzeugen.

(A2)

Wenn alle Elemente der zu sortierenden Liste denselben Sortier-Schlüssel haben, welches Verfahren ist dann effizienter: Insertion-Sort oder Selection-Sort? Begründe deine Antwort!

Tipp

Veranschauliche in beiden Verfahren das Sortieren einer Zeichenkette aus gleichen Buchstaben und überlege dir, welches Verfahren effizienter ist.