Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:problemstellung:start [06.02.2023 09:40] – [Gemeinsamkeiten] Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:sorting:problemstellung:start [08.02.2023 16:06] (aktuell) – [Sortiert?] Frank Schiebel
@@ Zeile 38: / Zeile 38: @@
 ==== Gemeinsamkeiten ====
-In allen Beispielen wurde ein Array  mit der (noch zu implementierenden) Methode ''Insertion.sort(array)'' sortiert. Dabei hatten die Array-Elemente verschiedenste Typen -- was für den Aufruf der Methode jedoch unerheblich war. Der Vorgang des Sortierens war vom Datentyp, der zu sortieren ist vollkommen abstrahiert -- **wie geht das**?
+In allen Beispielen wurde ein Array  mit der (noch zu implementierenden) Methode ''Insertion.sort(array)'' sortiert. Dabei hatten sowohl Array-Elemente als auch die Sortierschlüssel verschiedenste Typen -- was für den Aufruf der Methode jedoch unerheblich war: Die Methode erhält als Argument das Array und sortiert es. Der Vorgang des Sortierens war vom Typ des Schlüssels, nach dem sortiert werden sollte ist vollkommen abstrahiert -- die ''sort()'' Methode hat immer funktioniert.
+===== Callbacks und Interfaces =====
+Ein Callback ist eine Referenz auf ausführbaren Code - bei den Sortierbeispielen oben geschieht stets folgendes:
+  * Das Programm ruft die ''sort()''-Methode mit einem Array von Objekten auf.
+  * Die ''sort()''-Methode ruft ihrerseits die ''compareTo()'' Methode der Objekte auf, um zu ermitteln, in welcher Reihenfolge diese angeordnet werden müssen.
+In Java werden solche Callbacks als **Interfaces** implementiert. Datentypen, die man sortieren kann, müssen in Java das **Comparable-Interface** implementieren. Zahlreiche Datentypen machen das "von sich aus", z.B. Integer, Double, String, Date, und File.
+==== Eigene sortierbare Objekte ====
+Wenn man eigene Objekte implementiert, die sortiert werden sollen, müssen diese eine Methode ''compareTo()'' implementieren, die entweder -1, +1 oder 0 zurückgibt, je nachdem wie der Vergleich ausfällt. Am besten sieht man das an einem Beispiel:
+<code java>
+public class Time implements Comparable<Time> // Hier wird angegeben, dass das Comparable Interface implementiert wird.
+{
+    private int hour, minute;
+    public Time(int h, int m)
+    {
+        hour = h;
+        minute = m;
+    }
+    public int compareTo(Time that)
+    {
+       if (this.hour < that.hour ) return -1;
+       if (this.hour > that.hour ) return +1;
+       if (this.minute > that.minute ) return +1;
+       if (this.minute < that.minute ) return -1;
+       return 0;
+    }
+}
+</code>
+Der Vergleich zweier Objekte des Typs ''Time'' findet dann folgendermaßen statt:
+<code java>
+Time t1 = new Time(15,5);
+Time t2 = new Time(15,7);
+if (t1.compareTo(t2) < 0 ) {
+    System.out.println("t1 ist kleiner als t2");
+}
+if (t1.compareTo(t2) > 0 )
+    System.out.println("t2 ist kleiner als t1");
+}
+if (t1.compareTo(t2) == 0 )
+    System.out.println("t2 und t1 sind gleich");
+}
+</code>
+----
+{{:aufgabe.png?nolink  |}}
+=== (A1) ===
+{{ :faecher:informatik:oberstufe:algorithmen:sorting:problemstellung:ssp.png?200|}}
+  * Teste das Beispiel mit der Klasse ''Time'' in BlueJ
+  * Denke dir eine eigene Klasse aus, die das Comparable Interface implementiert, implementiere und teste sie.
+  * Kann man das Spiel Schere-Stein-Papier mit einer Klasse ''Spielzug'' implementieren, die das   Comparable Interface implementiert? Begründe deine Antwort.
+===== Hilfsfunktionen =====
+Da der Vergleich mittels ''etwas.compareTo(anderesEtwas) < 0'' ein wenig unhandlich ist, vereinbaren wir für diesen Wikibereich zwei **Hilfsfunktionen**, die uns die Implementation der Sortieralgorithmen erleichtern werden:
+==== Kleiner... ====
+Die Hilfsfunktion ''less'' nimmt zwei Elemete des Typs Comparable entgegen und liefert ''true'' zurück, wenn das erste kleiner ist als das zweite:
+<code java>
+private boolean less(Comparable v, Comparable w)
+{
+    return v.compareTo(w) < 0;
+}
+</code>
+==== Platztausch ====
+Die Hilfsfunktion ''exch'' vertauscht zwei Elemente eines Arrays:
+<code java>
+private void exch(Comparable[] a, int i, int j)
+{
+    Comparable swap = a[i];
+    a[i] = a[j];
+    a[j] = swap;
+}
+</code>
+==== Sortiert? ====
+Die letzte Hilfsfunktion gibt ''true'' zurück, wenn das Array sortiert ist:
+<code java>
+private boolean isSorted(Comparable[] a)
+{
+    for (int i = 1; i < a.length; i++) {
+        if (less(a[i], a[i-1])) return false;
+        }
+    return true;
+}
+</code>
+==== Material ====
+{{simplefilelist>:faecher:informatik:oberstufe:algorithmen:sorting:problemstellung:*}}