faecher:informatik:oberstufe:algorithmen:sorting:insertionsort:start []

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.

====== 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.

<html>
<iframe title="Veranschaulichung von Insertion Sort" src="https://tube.schule.social/videos/embed/f6a19d90-0ade-4933-ba83-af380a604341" allowfullscreen="" sandbox="allow-same-origin allow-scripts allow-popups" width="560" height="315" frameborder="0"></iframe>
</html>

===== 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 |}}

++++