Wie können Objekte selbst definierter Klassen sortiert werden?

Eine Sortierung selbst definierter Objekte in Arrays oder Listen kann in Java nach zwei verschiedenen Anforderungsprofilen erfolgen. In beiden Fällen müssen hierfür jedoch zunächst Vergleichskriterien festgelegt werden.

Die Methoden sort()

Zur Sortierung von Arrays bieten die Java-Bibliotheken die vielfach überladenen statischen Methoden java.util.Arrays.sort(). Hiermit können Arrays mit primitiven Datentypen, Referenztypen und generischen Typen sortiert werden. Zum Sortieren von Listen existiert die Klasse java.util.Collections mit zwei Methoden sort(). Zur Sortierung generischer Typen kann jeweils zusätzlich eine Comparator-Instanz als Parameter übergeben werden. Darüber hinaus besteht für Arrays die Möglichkeit, die Sortierbereiche zu beschränken.

Der Vergleich als Basis einer Sortierung

Die Sortierung von Objekten basiert auf der Vergleichbarkeit von Objekteigenschaften. So werden Zahlen bspw. hinsichtlich ihres Wertes auf- oder absteigend und Strings üblicherweise nach der Position der Buchstaben im Alphabet sortiert.
Bei selbst definierten Klassen müssen die Kriterien für einen Objektvergleich erst bestimmt werden.
Bei der darauf aufbauenden Sortierung unterscheidet man dann zwischen der sog. natürlichen Sortierung mittels Comparable.compareTo(T o) und der anforderungsabhängigen Sortierung nach einzelnen Eigenschaften durch Comparator.compare(T o1, T o2).

Natürliche Sortierung durch Comparable.compareTo(T o)

Unter einer natürliche Sortierung (natural ordering) versteht man die 'Standard-Sortierung' von Objekten, wie sie z.B. für Zahlen, Datumsangaben oder auch die alphabetische Reihenfolge von Strings bekannt ist. Diese Sortierweisen beruhen auf gängigen Konventionen oder Systemen, wie sie für selbst erstellt Datentypen nicht existieren. Deren Vergleichsbasis und die hierfür herangezogenen Eigenschaften müssen im Rahmen des Klassendesigns erst festgelegt werden.
Die natürliche Sortierung von Objekten einer Klasse wird einmalig festgelegt. Sollen, je nach Anwendungsfall, darüber hinaus weitere Sortierweisen eines Datentyps benötigt werden, so muss auf die zweite, weiter unten behandelte Methode mittels Comparator.compare(T o1, T o2) zurückgegriffen werden.

Die Methode int compareTo(T o) ist die einzige Methode des Interfaces Comparable<T>, das von der zu sortierenden Klasse implementert werden muss. Die Konkretisierung der Methode sollte einen int-Wert liefern, der negativ, 0 oder positiv ist, je nachdem, ob das aktuelle Objekt im Vergleich mit dem als Parameter übergebenen in der Sortierreihenfolge davor, auf gleicher Ebene oder danach steht.

compareTo(T o) und equals(Object o)

Die Durchführung eines Vergleiches zweier Objekte und deren Prüfung auf Gleichheit müssen zwangsläufig aufeinander abgestimmt werden. Auch wenn es nicht zwingend notwendig ist, so empfiehlt Oracle dringend, dass für zwei Objekte o1 und o2 einer Klasse die Ausdrücke o1.compareTo(o2) == 0 und o1.equals(o2) den gleichen boolschen Wert liefern. Auf die Konsistenz dieser Ordnung sollte unbedingt geachtet werden, da es ansonsten u.a. zu Problemen mit sortierten Sets und Maps kommen kann. Ist die Konsistenz nicht gegeben so empfiehlt Oracle die folgende Kommentierung: "Note: this class has a natural ordering that is inconsistent with equals."

Ein Beispiel

Das Beispiel zeigt eine Klasse Moped, die das Interface Comparable implementiert. Die Klasse definiert klassische Motorradtypen anhand des Namens, Modells und der Leistung. Die Eigenschaften werden in entsprechend benannten Instanzvariablen gespeichert. Neben den zugehörigen Getter-Methoden, einer toString()-Methode zur übersichtlichen Ausgabe und einem Konstruktor überschreibt die Klasse die Methode compareTo(Object m).
Die Klasse ObjektVergleich enthält main(). Hier werden sechs Moped-Objekte erzeugt und in einem Array abgelegt. Nach Sortierung des Arrays werden die Objekte ausgegeben.

Die Sortierung des Arrays durch die Methode Arrays.sort() greift auf den Objektvergleich durch compareTo(Object m) zu. Wird Comparable nicht implementiert, so wird an dieser Stelle eine ClassCastException geworfen.
Der Objektvergleich selbst geschieht so, dass hierzu nach einigen Sicherheitsabfragen stufenweise die Herstellerbezeichnung, der Typ und schließlich die Leistung herangezogen werden. Für die Leistung wird ein numerischer Wertevergleich und für die Strings der Hersteller- und Typangaben jeweils compareTo() der Klasse String verwendet.
Die Klasse String implementiert ihrerseits Comparable und führt Vergleiche durch complareTo() und equals() anhand von Character-Arrays durch. Die o.a. Konsistenz zwischen beiden Vergleichsmethoden ist somit von vorne herein gegeben und die Klasse Moped muss - zumindest für die Realisierung der natürlichen Sortierung - equals() nicht gesondert überschreiben.

import java.util.Arrays;

public class ObjectVergleich {

    public static void main(String[] args) {
        Moped m1 = new Moped("BMW", "RS 54", 58);
        Moped m2 = new Moped("Moto Guzzi", "Falcone Sport", 23);
        Moped m3 = new Moped("AJS", "7R", 45);
        Moped m4 = new Moped("Moto Guzzi", "V8", 72);
        Moped m5 = new Moped("B√∂hmerland", "Tourer", 16);
        Moped m6 = new Moped("Moto Guzzi", "Falcone Tourismo", 19);

        Moped[] moped = { m1, m2, m3, m4, m5, m6 };
        Arrays.sort(moped);
        for (Moped m : moped) {
            if (m != null) {
                System.out.println(m.toString());
            }
        }
    }
}

class Moped implements Comparable<Object> {
    String hersteller;
    String typ;
    int ps;

    public Moped(String hersteller, String typ, int ps) {
        this.hersteller = hersteller;
        this.typ = typ;
        this.ps = ps;
    }

    public int compareTo(Object m) {
        if (this == (Moped) m) {
            return 0;
        }
        if (m instanceof Moped) {
            Moped einMoped = (Moped) m;

            if (this.getHersteller() == null) {
                return 1;
            }
            if (einMoped.getHersteller() == null) {
                return -1;
            }
            if (this.getHersteller().equals(einMoped.getHersteller())) {
                if (this.getTyp() == null) {
                    return 1;
                }
                if (einMoped.getTyp() == null) {
                    return -1;
                }
                if (this.getTyp().equals(einMoped.getTyp())) {
                    return this.getPS() - einMoped.getPS();  // Vorsicht!
                }
                return this.getTyp().compareTo(einMoped.getTyp());
            }
            return this.getHersteller().compareTo(einMoped.getHersteller());
        }
        return -1;
    }

    public String getHersteller() {
        return hersteller;
    }

    public String getTyp() {
        return typ;
    }

    public int getPS() {
        return ps;
    }
    
    @Override
    public String toString() {
        return "Moped [ Hersteller:" + getHersteller() + " Typ:" + getTyp()
                + " PS:" + getPS() + " ]";
    }
}

Auf den arithmetischen Vergleich der numerischen PS-Werte muss an dieser Stelle gesondert hingewiesen werden. Im Beispiel wird der Rückgabewert für die Leisungsangaben durch eine einfache Subtraktion ermittelt. Bei diesem Verfahren ist in anderen Fällen Vorsicht geboten. Ein Unterschreiten des kleinstzulässigen Integer-Wertes (Integer.MIN_VALUE), etwa im Rahmen eines Vergleichs langer Seriennummern o.ä., ergäbe wiederum einen positiven Rückgabewert mit entsprechend falscher Sortierung. Eine Abfrage etwa in der folgenden Form bietet hier Abhilfe:

//...
return this.getPS() < einMoped.getPS() ? -1 : (this.getPS() == einMoped.getPS() ? 0 : 1);

Ergänzende Sortierung durch compare()

Sollen die Objekte einer Klasse auf andere Art als der natürlichen sortiert werden oder soll daneben noch eine zusätzliche Sortierweise Verwendung finden, so muss hierfür eine gesonderte Klasse deklariert werden. Sie muss das Interface Comparator<T> mit seiner Methode compare(T o1, T o2) implementieren.

public class PSComparator implements Comparator<Moped> {
    @Override
    public int compare(Moped m1, Moped m2) {
        return m1.getPS() - m2.getPS();
    } 
}

Comparator ist ein generisches Interface, das die zu sortierende Klasse als Typparameter übergeben bekommt. Die Methode compare(T o1, T o2) kann dann zwei Objekte der Klasse vergleichen und liefert wiederum einen negativen, oder positiven Rückgabewert oder 0 bei Gleichheit. Hierzu muss der Methode sort(), neben dem Array oder der Liste, zusätzlich eine Instanz des Comparators übergeben werden.

Arrays.sort(moped, new PSComparator());