Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:insertionsort:start [04.02.2024 11:21] – [Beispiel] Marco Kuemmel
+++ faecher:informatik:oberstufe:algorithmen:sorting:insertionsort:start [06.02.2025 08:06] (aktuell) – [Beispiel] Frank Schiebel
@@ Zeile 24: / Zeile 24: @@
 === (A2) ===
-Wenn alle Elemente der zu sortierenden Liste denselben Sortier-Schlüssel haben (also z. B. nur aus einer Zeichenkette derselben Buchstaben bestehen), welches Verfahren ist dann effizienter: Insertion-Sort oder Selection-Sort? Begründe deine Antwort!
+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 |
@@ Zeile 34: / Zeile 34: @@
 ++++
+----
+{{: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.