Problemstellung: Sortieren

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.

Für verschiedene Schlüssel ergeben sich andere Reihenfolgen der Elemente:

Eine Liste zufälliger reeller Zahlen soll sortiert werden¹⁾:

Eine Wort-Liste soll sortiert werden:

Die Dateien in einem Verzeichnis sollen nach ihrem Namen sortiert werden:

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.

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.

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

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

• 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.

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:

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

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

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