Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:insertionsort:start [08.02.2023 18:40] – Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:sorting:insertionsort:start [06.02.2025 08:06] (aktuell) – [Beispiel] Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
 ====== Insertion Sort ======
-Während Selection Sort jeweils alle noich 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 soweit nach links, bis es an seiner korrekten Position innerhalb der bislang betrachteten Elemente gelandet ist.
+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 |}}
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A3) ===
+<callout  type="info" icon="true">
+Ein Sortieralgorithmus ist **stabil**, wenn er die ursprüngliche Reihenfolge von Elementen mit gleichem Schlüsselwert beibehält.
+Das bedeutet, wenn zwei Elemente den gleichen Sortierschlüssel haben, bleibt ihre relative Position zueinander nach dem Sortieren unverändert.
+Diese Eigenschaft ist besonders wichtig, wenn:
+   * Datensätze nach mehreren Kriterien sortiert werden sollen
+   * Die ursprüngliche Reihenfolge eine semantische Bedeutung hat
+Als Beispiel: Wenn wir eine Liste von Personen erst nach Alter und dann nach Namen sortieren, ist es oft wichtig, dass die ursprüngliche Reihenfolge bei gleichaltrigen Personen erhalten bleibt.
+Der Selectionsort-Algorithmus ist in seiner Grundform nicht stabil, da beim Vertauschen von Elementen im unsortierten Bereich die ursprüngliche Reihenfolge von Elementen mit gleichem Wert verändert werden kann - man kann Selectionsort jedoch auch stabil implementieren.
+</callout>
+(a) Überprüfe, ob deine Implementation von Selectionsort stabil ist.
+(b) Ändere in der Klasse "Sorting" die Methode ''less'' so, dass diese auch dann 0 zurückgibt, wenn die zu vergleichenden Elemente gleich sind:
+<code java>
+protected boolean less(String v, String w) {
+    return v.compareTo(w) <= 0; // Kleiner gleich, nicht nur echt kleiner!
+}
+</code>
+Überprüfe erneut, ob sein Selectionsort Algorithmus jetzt stabil ist.