D) Objekte sortieren – Comparator und Comparable

Oftmals kommt es vor, dass Sie verschiedene Objekte einer Klasse sortieren müssen. Natürlich können Sie hierzu einen geeigneten Sortieralgorithmus wie den Quicksort oder den Mergesort selbst implementieren. Aber warum sich die Mühe machen? Java bietet Ihnen die Möglichkeit eine java.util.List oder ein Array zu sortieren. Wie das funktioniert erfahren Sie in diesem Kapitel.

Collections.sort bzw. Arrays.sort

Um diese Sortierfunktionen zu verwenden (es wird ein modifizierter Mergesort verwendet), bieten die Klassen java.util.Collections (Sortierung einer List) und java.util.Arrays (Sortierung von Arrays) jeweils die Methode sort mit unterschiedlichen Parametern an. Mit der Klasse Arrays können Sie ein Array eines primitiven Datentyps, ein Array von Objekten einer beliebigen Klasse, oder einen generischen Typen sortieren lassen (jeweils optional mit der Angabe von wo bis wann sortiert werden soll). Beim Array des generischen Typs kann als weitere Möglichkeit noch ein java.util.Comparator übergeben werden. Was das ist, erfahren Sie später in diesem Kapitel. Collections.sort sortiert eine generische java.util.List – ebenfalls optional mit einem geeigneten java.util.Comparator.

Sehen Sie sich ein Beispiel an:

package de.jbb.cuc;

import java.util.Arrays;

public class ArraysAndCollectionsTest {

  public static void main(String[] args) {

    int[] unsorted = { 5, 6, 1, 123, 543, 32, 53, 75, 8 };
    System.out.println("Unsortiert:");
    System.out.println("-----------");
    for (int i : unsorted) {
      System.out.println(i);
    }
    Arrays.sort(unsorted);
    System.out.println("Sortiert:");
    System.out.println("-----------");
    for (int i : unsorted) {
      System.out.println(i);
    }
  }
}

package de.jbb.cuc;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ArraysAndCollectionsTest {

  public static void main(String[] args) {

    List<String> list = new ArrayList<String>(8);
    list.add("Sebastian Würkner");
    list.add("Stefan Kiesel");
    list.add("Andreas Pries");
    list.add("Byte-Welt.de");
    list.add("Erich Gamma");
    list.add("Richard Helm");
    list.add("Ralph Johnson");
    list.add("John Vlissides");
    System.out.println("Unsortiert:");
    System.out.println("-----------");
    for (String str : list) {
      System.out.println(str);
    }
    Collections.sort(list);
    System.out.println("Sortiert:");
    System.out.println("-----------");
    for (String str : list) {
      System.out.println(str);
    }
  }
}

Sie werden feststellen, dass die Sortierung in Java denkbar einfach ist – bis jetzt.

Eigene Objekte sortieren

Komplizierter wird es allerdings, wenn Sie eigene Objekte sortieren wollen. Denn woher soll Java wissen, anhand welcher Eigenschaft Ihre Objekte sortiert werden sollen? Ein Beispiel:

Sie möchten Objekte der (sehr einfach gehaltenen) Klasse Bier sortieren:

package de.jbb.cuc;

public class Bier {

  private String name;
  private String herkunft;
  private float inhalt;

  public Bier() {}

  public Bier(String name, String herkunft, float inhalt) {

    this.name = name;
    this.herkunft = herkunft;
    this.inhalt = inhalt;
  }

  public String getName() {
    return this.name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public String getHerkunft() {
    return this.herkunft;
  }

  public void setHerkunft(String herkunft) {
    this.herkunft = herkunft;
  }

  public float getInhalt() {
    return this.inhalt;
  }

  public void setInhalt(float inhalt) {
    this.inhalt = inhalt;
  }

  public String toString() {
    return this.name + " aus " + this.herkunft + " mit " + this.inhalt + " Litern";
  }
}

Lassen Sie sich nun zu Testzwecken ein Array oder eine Liste von Objekten dieser Klasse sortieren:

package de.jbb.cuc;

import java.util.Arrays;

public class ArraysAndCollectionsTest {

  public static void main(String[] args) {

    Bier[] biere = { 
        new Bier("Würzburger Hofbräu", "Würzburg", 0.5F), 
        new Bier("Becks", "Bremen", 0.33F), 
        new Bier("Paulaner", "München", 0.5F), 
        new Bier("Distelhäuser", "Distelhausen", 0.33F) 
    };
    System.out.println("Unsortiert:");
    System.out.println("-----------");
    for (Bier bier : biere) {
      System.out.println(bier);
    }
    Arrays.sort(biere);
    System.out.println("Sortiert:");
    System.out.println("-----------");
    for (Bier bier : biere) {
      System.out.println(bier);
    }
  }
}

Sie werden beim Ausführen (oder bei der Verwendung einer java.util.List bei der Kompilierung) feststellen, dass es zu einem Fehler kommt.

Exception in thread "main" java.lang.ClassCastException: de.jbb.cuc.Bier cannot be cast to java.lang.Comparable
	at java.util.Arrays.mergeSort(Unknown Source)
	at java.util.Arrays.sort(Unknown Source)

Diese Exception resultiert daraus, dass Java nicht weiß, nach was es die Klasse Bier sortieren soll. Um das festzulegen, können Sie bspw. das Interface Comparable verwenden.

Comparable

Um der sort-Methode zu sagen, nach was sortiert werden soll, lassen Sie die zu sortierende Klasse das Interface Comparable implementieren. Dieses Interface schreibt vor, dass die Methode public int compareTo(T o) überschrieben wird. Es ist Ihre Aufgabe in der Methode das aktuelle Objekt mit dem übergebenen Objekt zu vergleichen. Sollte das übergebene Objekt untergeordnet werden, geben Sie einen negativen Wert zurück, sollten die Objekte gleichwertig sein, geben Sie 0 zurück, ansonsten einen positiven Wert. Eine Beispielimplementation in unserer Bier-Klasse um nach dem Namen des Bieres zu sortieren könnte so aussehen (String implementiert auch Comparable, so dass wir uns einfach dessen compareTo-Methode bedienen können):

...
public class Bier implements Comparable<Bier> {

  ...

  @Override
  public int compareTo(Bier b) {
    if (b.getName() == null && this.getName() == null) {
      return 0;
    }
    if (this.getName() == null) {
      return 1;
    }
    if (b.getName() == null) {
      return -1;
    }
    return this.getName().compareTo(b.getName());
  }
}

Für den Fall, dass b gleich null ist, sollte eine NullPointerException geworfen werden. Jetzt können Sie das Array oder die Liste sortieren lassen.

Comparator

Eine Alternative zu Comparable ist der java.util.Comparator. Der Aufbau eines Comparators ist dem von Comparable sehr ähnlich. Der Unterschied besteht darin, dass ein Comparator nicht von der zu vergleichenden Klasse implementiert werden muss. Dadurch können Sie auch einfach Objekte von Klassen vergleichen, die Sie nicht selbst geschrieben haben oder verändern dürfen. Als Konsequenz werden der compare-Methode (der Comparator verwendet zum Sortieren die Methode compare anstelle von compareTo) gleich beide zu vergleichenden Objekte übergeben.

Als Konsequenz kann eine ClassCastException geworfen werden, falls keine generischen Typen festgelegt werden und beide Klassen nicht kompatibel zueinander sind. Bzgl. der Reihenfolge nimmt das zuerst übergebene Argument die Position von this bei der Verwendung von Comparable ein. Im Klartext bedeutet dies:

negativer Rückgabewert: Der erste Parameter ist untergeordnet
0 als Rückgabewert: Beide Parameter werden gleich eingeordnet
positiver Rückgabewert: Der erste Parameter ist übergeordnet

Sehen Sie sich nun das obige Beispiel als Comparator an.

package de.jbb.cuc;

import java.util.Comparator;

public class BierNameComparator implements Comparator<Bier> {

  @Override
  public int compare(Bier b1, Bier b2) {
    if (b1.getName() == null && b2.getName() == null) {
      return 0;
    }
    if (b1.getName() == null) {
      return 1;
    }
    if (b2.getName() == null) {
      return -1;
    }
    return b1.getName().compareTo(b2.getName());
  }
}

package de.jbb.cuc;

import java.util.Arrays;
import java.util.Comparator;

public class ArraysAndCollectionsTest {

  public static void main(String[] args) {

    Comparator<Bier> comp = new BierNameComparator();
    Bier[] biere = { 

        new Bier("Würzburger Hofbräu", "Würzburg", 0.5F), 
        new Bier("Becks", "Bremen", 0.33F), 
        new Bier("Paulaner", "München", 0.5F), 
        new Bier("Distelhäuser", "Distelhausen", 0.33F) };
    System.out.println("Unsortiert:");
    System.out.println("-----------");
    for (Bier bier : biere) {
      System.out.println(bier);
    }
    Arrays.sort(biere, comp);
    System.out.println("Sortiert:");
    System.out.println("-----------");
    for (Bier bier : biere) {
      System.out.println(bier);
    }
  }
}

Der Vorteil eines Comparators liegt darin, dass das Kriterium, nach welchem sortiert werden soll, einfach ausgetauscht werden kann. Schreiben Sie sich einfach einen weiteren Comparator, der bspw. zuerst nach Inhalt, dann nach Herkunft und letztendlich nach Namen sortiert (auf die Überprüfung, ob der Name oder die Herkunft gleich null ist, wird an dieser Stelle verzichtet):

package de.jbb.cuc;

import java.util.Comparator;

public class BierComparator implements Comparator<Bier> {

  @Override
  public int compare(Bier b1, Bier b2) {

    if (b1.getInhalt() == b2.getInhalt()) {
      if (b1.getHerkunft().compareTo(b2.getHerkunft()) == 0) {
        return b1.getName().compareTo(b2.getName());
      }
      else {
        return b1.getHerkunft().compareTo(b2.getHerkunft());
      }
    }
    else if (b1.getInhalt() > b2.getInhalt()) {
      return -1;
    }
    else {
      return 1;
    }
  }
}

Jetzt genügt es in Ihrer Main-Methode den BierNameComparator durch einen BierComparator auszutauschen und schon wird nach den neuen Kriterien geordnet.

package de.jbb.cuc;

import java.util.Arrays;
import java.util.Comparator;

public class ArraysAndCollectionsTest {

  public static void main(String[] args) {

    Comparator<Bier> comp = new BierComparator();
    Bier[] biere = { 
        new Bier("Würzburger Hofbräu", "Würzburg", 0.5F), 
        new Bier("Becks", "Bremen", 0.33F), 
        new Bier("Paulaner", "München", 0.5F), 
        new Bier("Distelhäuser", "Distelhausen", 0.33F) };
    System.out.println("Unsortiert:");
    System.out.println("-----------");
    for (Bier bier : biere) {
      System.out.println(bier);
    }
    Arrays.sort(biere, comp);
    System.out.println("Sortiert:");
    System.out.println("-----------");
    for (Bier bier : biere) {
      System.out.println(bier);
    }
  }
}