faecher:informatik:oberstufe:algorithmen:sorting:problemstellung: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.
====== 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:


<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:*}}