Ordnen und Sortieren

Geordnet vs. sortiert

Wir müssen unterscheiden

  • geordnet (ordered) → Die Reihenfolge der Elemente hat eine bestimmte Bedeutung und wird von der Collection erhalten
  • sortiert (sorted) → Die Reihenfolge der Elemente folgt einem Sortierkriterium
  • Eine sortierte Liste ist immer geordnet
  • Eine geordnete Liste kann (muss aber nicht) sortiert sein

Für das weitere Verständnis ist es wichtig, dass man sauber zwischen den Begriffen geordnet und sortiert unterscheidet. Man kann eine Collection nur dann sortieren, wenn sie geordnet ist, d. h. die Reihenfolge der Elemente über die Zeit erhält.

Für eine Sortierung benötigt man zwingend ein Sortierkriterium, d. h. es muss eine Funktion geben, die angibt, ob ein Element A vor oder nach einem Element B einsortiert werden soll. Diese Funktion wird in Java über die Interfaces Comparator und Comparable realisiert (s. u.).

Für eine Ordnung ist es nur nötig, dass man den Elementen einen Index zuordnen kann, der das Element stabil bezeichnet – zumindest solange man keine neuen Elemente einfügt.

Comparable und Comparator

  • Klassen können das Comparable<T>-Interface implementieren, um ihre natürliche (Sortier-)Reihenfolge (natural ordering) festzulegen
    int compareTo(T object)
  • Mit Comparator<T> kann man explizit eine Klasse schreiben, die Reihenfolge bzw. Sortierung von Objekten einer anderen Klasse bestimmt
    int compare(T o1, T o2)
  • Rückgabewerte der Methoden: < 0, 0, > 0
  • Zusammenhang mit equals()
    (x.compareTo(y) == 0) == (x.equals(y))

Java realisiert die Sortierung von Elementen über zwei Interfaces:

  • Comparable kann von einer Klasse implementiert werden, um die natürliche Sortierreihenfolge anzugeben. Jede Klasse kann nur genau eine solche besitzen. Sie gibt an, wie die Objekte im Normalfall sortiert werden sollen. Für Strings wäre dies die übliche alphanumerische Sortierung „Albert“, Alfons„, “Alfred„, “Beate" …
  • Comparator erlaubt es, zusätzlich zu der natürlichen Reihenfolge, noch beliebig viele andere externe Reihenfolgen anzugeben. Das Interface wird nicht von der zu sortierenden Klasse selbst, sondern von einer anderen Klasse implementiert. Für jede Reihenfolge wird hier eine eigene Klasse geschrieben, die das Interface implementiert.

Beide Interfaces implementieren Methoden, um zwei Objekte miteinander zu vergleichen. Im Falle von Comparable über compareTo wird this mit einem übergebenen Objekt verglichen. Bei Comparator bekommt compare zwei übergebene Objekte. Der Rückgabewert der Methode gibt an, wie die Reihenfolge der beiden Objekte sein soll:

  • < 0 das erste Objekt (bzw. this) ist „kleiner“, also vor dem zweiten einzusortieren. Häufig gibt man an dieser Stelle einfach ein -1 zurück, es sind aber alle Werte < 0 zulässig.
  • 0 die beiden Objekte sind „gleich“
  • > 0 das erste Objekt ist „größer“, also nach dem zweiten einzusortieren. Hier wird ebenfalls häufig einfach ein 1 zurückgegeben. Es sind aber größere Werte möglich.

Der Grund warum man beliebige positive und negative Werte zurückgeben darf liegt darin, dass sich damit viele Vergleiche einfacher durchführen lassen. So kann man z. B. das absteigende Sortieren von ganzen Zahlen einfach dadurch erreichen, dass man die eine von der anderen abzieht.

Beispiel: Comparable 

public class Student implements Comparable<Student> {
    private int matrikelNummer;
    private String name;

    public Student(int matrikelNummer, String name) {
        this.matrikelNummer = matrikelNummer;
        this.name = name;
    }

    public String toString() {
        return matrikelNummer + " - " + name;
    }
}
compareTo-Methode für Student
    public int compareTo(Student o) {
        if (o.matrikelNummer == matrikelNummer) {
            return 0;
        }
        else if (o.matrikelNummer > matrikelNummer) {
            return -1;
        }
        else {
            return 1;
        }
    }
}

Der Source-Code ist unvollständig, da noch die hashCode() und equals()-Methode angegeben werden müssen. Aus Platzgründen wurden sie hier weggelassen.

Da es bei der compareTo-Methode nur darauf ankommt, ob der Rückgabewert <, > oder = Null ist, kann man die obige Methode noch deutlich kürzer schreiben:

compareTo-Methode für Student
    public int compareTo(Student o) {
        return matrikelNummer - o.matrikelNummer;
    }
}

Beispiel: Comparable (mit ArrayList) 

List<Student> studenten = new ArrayList<>();

studenten.add(new Student(4411, "Franz Müller"));
studenten.add(new Student(5711, "Albert Meier"));
studenten.add(new Student(4711, "Xaver Meier"));

Collections.sort(studenten);

for (Student student : studenten) {
    System.out.println(student);
}

4411 - Franz Müller
4711 - Xaver Meier
5711 - Albert Meier

Beispiel: Comparable (mit TreeSet) 

Set<Student> studenten = new TreeSet<>();

studenten.add(new Student(4411, "Franz Müller"));
studenten.add(new Student(5711, "Albert Meier"));
studenten.add(new Student(4711, "Xaver Meier"));

for (Student student : studenten) {
    System.out.println(student);
}

4411 - Franz Müller
4711 - Xaver Meier
5711 - Albert Meier

Beispiel: Comparator 

public class Student {

    int matrikelNummer;
    String name;

    public Student(int matrikelNummer, String name) {
        this.matrikelNummer = matrikelNummer;
        this.name = name;
    }

    public String toString() {
        return matrikelNummer + " - " + name;
    }
}

public class StudentComparator implements Comparator<Student> {

    public int compare(Student o1, Student o2) {
        if (o2.matrikelNummer == o1.matrikelNummer) {
            return 0;
        }
        else if (o2.matrikelNummer > o1.matrikelNummer) {
            return -1;
        }
        else {
            return 1;
        }
    }
}

Beispiel: Comparator (mit ArrayList) 

List<Student> studenten = new ArrayList<>();

studenten.add(new Student(4411, "Franz Müller"));
studenten.add(new Student(5711, "Albert Meier"));
studenten.add(new Student(4711, "Xaver Meier"));

Collections.sort(studenten, new StudentComparator());

for (Student student : studenten) {
    System.out.println(student);
}

4411 - Franz Müller
4711 - Xaver Meier
5711 - Albert Meier

Beispiel: Comparator (mit TreeSet) 

Set<Student> studenten = new TreeSet<>(new StudentComparator());

studenten.add(new Student(4411, "Franz Müller"));
studenten.add(new Student(5711, "Albert Meier"));
studenten.add(new Student(4711, "Xaver Meier"));

for (Student student : studenten) {
    System.out.println(student);
}

4411 - Franz Müller
4711 - Xaver Meier
5711 - Albert Meier

Methoden von SortedSet

  • Comparator<? super E> comparator() – Gibt den Comparator zurück, mit dem die Elemente sortiert werden oder null wenn die natürliche Ordnung verwendet wird
  • SortedSet<E> subSet(E fromElement, E toElement) – Erzeugt eine Teilmenge von fromElement (inklusive) bis toElement (exklusiv)
  • SortedSet<E> headSet(E toElement) – Erzeugte eine Teilmenge vom Anfang bis toElement (exklusiv)
  • SortedSet<E> tailSet(E fromElement) – Erzeugt eine Teilmenge von fromElement (inklusive) bis zum Ende
  • E first() – Gibt das erste Element zurück
  • E last() – Gibt das letzte Element zurück

Das Interface SortedSet beschreibt ein spezielles Set, bei dem die Objekte bereits beim Einfügen sortiert werden.

Existiert eine Sortierung, kann man Operationen der Form „von Element C, bis Element G“ durchführen, da durch die Sortierung festgelegt ist, welche Elemente zwischen diesen beiden Grenzen liegen können. Deswegen sind hier dann die Methoden subSet, headSet und tailSet möglich.

Beispiel: SortedSet 

SortedSet<String> set = new TreeSet<>();

set.add("Seeler");
set.add("Mueller");
set.add("Zander");
set.add("Beckenbauer");
set.add("Schumacher");

System.out.printf("Elemente: %s%n", set);
System.out.printf("Erstes Element: %s%n", set.first());
System.out.printf("Letztes Element: %s%n", set.last());

Elemente: [Beckenbauer, Mueller, Schumacher, Seeler, Zander]
Erstes Element: Beckenbauer
Letztes Element: Zander

Da das TreeSet die Elemente bereits beim Einfügen sortiert, entfällt in diesem Beispiel eine explizite Sortieroperation: die Daten liegen im SortedSet immer sortiert vor.

Beispiel: Sortieren mit Collections.sort 

List<String> list = new ArrayList<>();
list.add("Seeler");
list.add("Mueller");
list.add("Zander");
list.add("Beckenbauer");
list.add("Schumacher");

Collections.sort(list);
System.out.println(list);

Collections.sort(list, new ReverseComparator());

System.out.println(list);

[Beckenbauer, Mueller, Schumacher, Seeler, Zander]
[Zander, Seeler, Schumacher, Mueller, Beckenbauer]

class ReverseComparator implements Comparator<String> {

    public int compare(String o1, String o2) {
        return o1.compareTo(o2) * -1;
    }
}

Der ReverseComparator dreht einfach die Sortierreihenfolge der normalen compaerTo()-Methode von String um, sodass alle Elemente rückwärts sortiert werden.

Copyright © 2025 Thomas Smits