====== 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: {{ :faecher:informatik:oberstufe:algorithmen:sorting:insertionsort:drawing_2023-02-08_20.49.58.excalidraw.png |}} ---- {{:aufgabe.png?nolink |}} === (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. ---- {{:aufgabe.png?nolink |}} === (A2) === Wenn alle Elemente der zu sortierenden Liste denselben Sortier-Schlüssel haben (die zu sortierende Liste also z. B. nur aus "aaaaaaa" besteht), 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. {{ :faecher:informatik:oberstufe:algorithmen:sorting:insertionsort:insertion_aaa.png?400 |}} {{ :faecher:informatik:oberstufe:algorithmen:sorting:insertionsort:slelection_aaa.png?400 |}} ++++