====== Problemstellung: Sortieren ====== ===== Beispiel: Eine Liste mit Personen ===== {{ :faecher:informatik:oberstufe:algorithmen:sorting:problemstellung:liste.png?500 |}} Die Liste beinhaltet **Elemente** (Items), ein Element entspricht einer Zeile, sie soll sortiert werden nach einem (Sortier-)**Schlüssel** (Key). In diesem Fall soll der Sortierschlüssel der Nachname sein. Die Liste ist dann sortiert, wenn die Elemente anhand des Sortierschlüssels in eine **Reihenfolge** gebracht worden sind. {{ :faecher:informatik:oberstufe:algorithmen:sorting:problemstellung:sorted.png?500 |}} Für verschiedene Schlüssel ergeben sich andere Reihenfolgen der Elemente: {{ :faecher:informatik:oberstufe:algorithmen:sorting:problemstellung:sort_orders.png |}} ===== Ziel: Wir wollen alles mögliche Sortieren ===== ==== Beispiel 1: ==== Eine Liste zufälliger reeller Zahlen soll sortiert werden((Hört sich erst mal sinnlos an, eine Anwendung kommt später...)): {{ :faecher:informatik:oberstufe:algorithmen:sorting:problemstellung:real.png?500 |}} ==== Beispiel 2: ==== Eine Wort-Liste soll sortiert werden: {{ :faecher:informatik:oberstufe:algorithmen:sorting:problemstellung:worte.png?400 |}} ==== Beispiel 3: ==== Die Dateien in einem Verzeichnis sollen nach ihrem Namen sortiert werden: {{ :faecher:informatik:oberstufe:algorithmen:sorting:problemstellung:dateien.png?500 |}} ==== Gemeinsamkeiten ==== 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:


public class Time implements Comparable // 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;
    }
}

Der Vergleich zweier Objekte des Typs ''Time'' findet dann folgendermaßen statt:


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"); 
}

---- {{: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:


private boolean less(Comparable v, Comparable w)
{ 
    return v.compareTo(w) < 0; 
}

==== Platztausch ==== Die Hilfsfunktion ''exch'' vertauscht zwei Elemente eines Arrays:


private void exch(Comparable[] a, int i, int j)
{
    Comparable swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

==== Sortiert? ==== Die letzte Hilfsfunktion gibt ''true'' zurück, wenn das Array sortiert ist:


private boolean isSorted(Comparable[] a)
{
    for (int i = 1; i < a.length; i++) {
        if (less(a[i], a[i-1])) return false;
        }
    return true;
}

==== Material ==== {{simplefilelist>:faecher:informatik:oberstufe:algorithmen:sorting:problemstellung:*}}