Sortieren in Java [Tutorial]

Dieses Tutorial erklärt – Schritt für Schritt und mit vielen Code-Beispielen – wie man in Java primitive Datentypen (ints, longs, doubles, etc.) und Objekte beliebiger Klassen sortieren kann.

Im einzelnen beantwortet der Artikel folgende Fragen:

• Wie sortiert man in Java Arrays von primitiven Datentypen?
• Wie sortiert man in Java Arrays und Listen von Objekten?
• Wie sortiert man in Java parallel?
• Welche Sortieralgorithmen verwendet das JDK intern?

Der Artikel ist Teil des Ultimate Guides über Sortieralgorithmen, der einen Überblick über die gängigsten Sortierverfahren und deren Eigenschaften, wie z. B. deren Zeit- und Platzkomplexität, gibt.

Alle Quellcodes dieses Artikels findest du in meinem GitHub-Repository.

Was kann man in Java sortieren?

Die folgenden Datentypen lassen sich mit Java-Bordmitteln sortieren:

• Arrays von primitiven Datentypen (int[], long[], double[], usw.),
• Arrays und Listen von Objekten, die das Comparable-Interface implementieren,
• Arrays und Listen von Objekten beliebiger Klassen, mit Angabe eines Comparators, d. h. eines zusätzlichen Objekts, das das Comparator-Interface implementiert (oder eines entsprechenden Lambdas).

Den genauen Unterschied zwischen Comparable und Comparator erkläre ich in einem separaten Artikel. Dort zeige ich auch, wie man seit Java 8 mit Comparator.comparing() sehr elegant Comparatoren erstellen und aneinanderreihen kann.

Arrays.sort() – primitive Datentypen sortieren

Die Klasse java.util.Arrays stellt Sortiermethoden für alle primitiven Datentypen (außer boolean) bereit:

• static void sort(byte[] a)
• static void sort(char[] a)
• static void sort(double[] a)
• static void sort(float[] a)
• static void sort(int[] a)
• static void sort(long[] a)
• static void sort(short[] a)

Beispiel: Sortieren eines int-Arrays

Das folgenden Beispiel zeigt, wie ein int-Array sortiert und dann auf der Konsole ausgegeben wird:

int[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a);
System.out.println(Arrays.toString(a));Code-Sprache: Java (java)

Die Ausgabe dieses kurzen Programs lautet:

[1, 2, 3, 4, 5, 6, 7, 8, 9]Code-Sprache: Klartext (plaintext)

Teilbereiche eines Arrays sortieren

Für jeden der o. g. Datentypen (int, long, double, usw.) gibt es eine überladene Methode, die nur einen Teilbereich des Arrays sortiert, z. B.:

• static void sort(int[] a, int fromIndex, int toIndex)

Das folgende Beispiel sortiert nur die ersten fünf Elemente des Arrays:

int[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a, 0, 5);
System.out.println(Arrays.toString(a));Code-Sprache: Java (java)

Das Programm gibt folgendes aus:

[2, 4, 5, 8, 9, 3, 1, 7, 6]Code-Sprache: Klartext (plaintext)

Die ersten fünf Elemente 2, 4, 5, 8, 9 wurden sortiert, die restlichen vier Elemente 3, 1, 7, 6, sind unverändert.

Java-Objekte sortieren

Primitive Datentypen werden nach ihrer natürlichen Ordnung sortiert. Dementsprechend wird unser Beispiel-Array [4, 8, 5, 9, 2, 3, 1, 7, 6] nach dem Sortieren zu [1, 2, 3, 4, 5, 6, 7, 8, 9].

Doch in welcher Reihenfolge werden Objekte sortiert?

Integer- und String-Arrays sortieren

Wie ein Integer- oder String-Array sortiert wird, versteht jeder Java-Entwickler intuitiv:

Integer[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a);
System.out.println(Arrays.toString(a));Code-Sprache: Java (java)

Auch hier bekommen wir:

[1, 2, 3, 4, 5, 6, 7, 8, 9]Code-Sprache: Klartext (plaintext)

Sortieren wir ein paar Vornamen:

String[] names = {"Susan", "Thomas", "Judith", "Daniel", "Eva", "Ben",
      "Antonia", "Paul"};
Arrays.sort(names);
System.out.println(Arrays.toString(names));Code-Sprache: Java (java)

Das Ergebnis lautet – wie erwartet:

[Antonia, Ben, Daniel, Eva, Judith, Paul, Susan, Thomas]Code-Sprache: Klartext (plaintext)

Integer-Objekte werden also offensichtlich genau so wie int-Primitive sortiert. Und Strings alphabetisch.

Objekte eigener Klassen sortieren

Doch wie sortiert man seine selbstgebaute Customer-Klasse? Oder eine Invoice?

Probieren wir es aus! Hier zunächst unsere Customer-Klasse:

public class Customer {
  private int id;
  private String firstName;
  private String lastName;

  public Customer(int id, String firstName, String lastName) {
    this.id = id;
    this.firstName = firstName;
    this.lastName = lastName;
  }

  @Override
  public String toString() {
    return "Customer{" +
          "id=" + id +
          ", firstName='" + firstName + ''' +
          ", lastName='" + lastName + ''' +
          '}';
  }Code-Sprache: Java (java)

Wir versuchen diese mit Arrays.sort() zu sortieren:

Customer[] customers = {
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
};
Arrays.sort(customers);
System.out.println(Arrays.toString(customers));Code-Sprache: Java (java)

Diesen Versuch quittiert Java mit folgender Fehlermeldung:

Exception in thread "main" java.lang.ClassCastException:
class eu.happycoders.sorting.Customer cannot be cast to class java.lang.Comparable

Java weiß ohne zusätzliche Informationen nicht, wie Customer-Objekte sortiert werden sollen. Wie stellen wir diese Informationen bereit? Das erfährst du im nächsten Kapitel.

Sortieren mit Comparable und Comparator

Die Sortier-Instruktionen können wir auf zwei unterschiedliche Arten bereitstellen:

1. indem wir die Klasse Customer das Interface java.lang.Comparable implementieren lassen (so wie von der Fehlermeldung gefordert) oder
2. indem wir der Arrays.sort()-Methode eine Implementierung des Interfaces java.util.Comparator mitgeben.

Die beiden Varianten werden in den folgenden zwei Abschnitten beschrieben. Einen tieferen Einblick in die Interfaces Comparable und Comparator bietet der Artikel "Comparator, Comparable und compareTo – Vergleichen von Objekten in Java".

Sortieren mit Comparable

Das Interface java.lang.Comparable definiert eine einzige Methode:

• public int compareTo(T o)

Diese wird vom Sortieralgorithmus aufgerufen, um zu prüfen, ob ein Objekt kleiner, gleich oder größer als ein anderes Objekt ist. Je nachdem muss die Methode eine negative Zahl, 0 oder eine positive Zahl zurückliefern.

(Wenn du dir die Quellcodes von Integer und String anschaust, wirst du feststellen, dass beide das Comparable-Interface und die compareTo()-Methode implementieren.)

Wir wollen unsere Kunden nach Kundennummer sortieren. Dazu müssen wir die Customer-Klasse wie folgt erweitern (den Konstruktor und die toString()-Methode lasse ich hier der Übersicht halber weg):

public class Customer implements Comparable<Customer> {
  private int id;
  private String firstName;
  private String lastName;

  // Constructor and toString method omitted

  @Override
  public int compareTo(Customer o) {
    return this.id < o.id ? -1 : (this.id == o.id ? 0 : 1);
  }
}Code-Sprache: Java (java)

Die Funktionsweise aus Perspektive der compareTo()-Methode:

• Wenn meine Kundennummer kleiner ist als deine, dann gib -1 zurück;
• wenn unsere Kundennummern gleich sind, gib 0 zurück;
• ansonsten gib 1 zurück.

Etwas kürzer wird es, wenn man die Methode Integer.compare() verwendet. Diese vergleicht die zwei IDs auf genau die gleiche Art und Weise:

@Override
public int compareTo(Customer o) {
  return Integer.compare(this.id, o.id);
}Code-Sprache: Java (java)

Unsere so erweiterte Customer-Klasse können wir nun problemlos sortieren lassen (hier noch mal, damit du nicht scrollen musst, das Customer-Sortier-Beispiel von oben):

Customer[] customers = {
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
};
Arrays.sort(customers);
System.out.println(Arrays.toString(customers));Code-Sprache: Java (java)

Dieses mal läuft das Programm ohne Fehler durch und gibt folgendes aus (die Zeilenumbrüche habe ich der Übersicht halber manuell eingefügt):

[Customer{id=10503, firstName='Phil', lastName='Gruber'},
 Customer{id=28378, firstName='Marina', lastName='Metz'},
 Customer{id=43423, firstName='Elizabeth', lastName='Mann'},
 Customer{id=57299, firstName='Caroline', lastName='Albers'},
 Customer{id=61157, firstName='Patrick', lastName='Sonnenberg'}]Code-Sprache: Klartext (plaintext)

Unsere Kunden sind nun, wie gewünscht, nach Kundernnummer sortiert.

Was aber, wenn wir die Kunden für einen anderen Use Case nicht nach Nummern, sondern nach Namen sortieren wollen? Wir können ja compareTo() nur einmal implementieren. Müssen wir uns für immer und ewig auf eine Reihenfolge festlegen?

Hier kommt das Interface Comparator ins Spiel, das ich im nächsten Abschnitt beschreiben werde.

Sortieren mit einem Comparator

Mit der Customer.compareTo()-Methode haben wir die sogenannte "natürliche Ordnung" der Kunden definiert. Mit dem Interface Comparator können wir beliebig viele weitere Sortierreihenfolgen für eine Klasse definieren.

Analog zur compareTo()-Methode definiert das Comparator-Interface die folgende Methode:

• int compare(T o1, T o2)

Diese wird aufgerufen, um zu prüfen, ob das Objekt o1 kleiner, gleich oder größer als das Objekt o2 ist. Entsprechend muss auch diese Methode eine negative Zahl, 0 oder eine positive Zahl als Rückgabewert liefern.

Seit Java 8 können wir einen Comparator sehr elegant mit Comparator.comparing() erstellen. Mit folgendem Code können wir die Kunden zunächst nach Nachnamen und dann nach Vornamen sortieren:

Arrays.sort(customers,
      Comparator.comparing(Customer::getLastName)
            .thenComparing(Customer::getFirstName));Code-Sprache: Java (java)

Wie du siehst, kann man hier beinahe in natürlicher Sprache aufschreiben, wie die Kunden sortiert werden sollen.

Den Comparator können wir auch in einer Konstanten in der Customer-Klasse speichern, um ihn an verschiedenen Stellen wiederzuverwenden:

public static final Comparator<Customer> NAME_COMPARATOR = Comparator
    .comparing(Customer::getLastName)
    .thenComparing(Customer::getFirstName);Code-Sprache: Java (java)

Sortieren würden wir die Kunden dann so:

Arrays.sort(customers, Customer.NAME_COMPARATOR);Code-Sprache: Java (java)

Weitere Möglichkeiten, um Comparatoren zu erstellen, findest Du in diesem Artikel. Probier es einfach mal aus!

Sortieren einer Liste in Java

Bis jetzt haben wir ausschließlich die folgenden zwei Methoden der Klasse java.util.Arrays verwendet, um Objekte zu sortieren:

• static void sort(Object[] a) – zum Sortieren von Objekten entsprechend ihrer natürlichen Ordnung,
• static void sort(T[] a, Comparator<? super T> c) – zum Sortieren von Objekten anhand des übergebenenen Comparators.

Oft haben wir Objekte nicht in einem Array vorliegen, sondern in einer Liste. Um diese zu sortieren, gibt es (seit Java 8) zwei Möglichkeiten:

Liste sortieren mit Collections.sort()

Bis einschließlich Java 7 musste die Methode Collections.sort() zu Hilfe genommen werden, um eine Liste zu sortieren.

Im folgenden Beispiel sollen wieder unsere Kunden sortiert werden, zunächst nach Kundennummer (also entsprechend ihrer "natürlichen Ordnung"):

ArrayList<Customer> customers = new ArrayList<>(List.of(
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
));
Collections.sort(customers);
System.out.println(customers);Code-Sprache: Java (java)

Das Programm gibt, wie im vorherigen Beispiel auch, die Kunden sortiert nach ihrer Kundennummer aus.

Warum werden im Beispiel zwei Listen erstellt? Eine mit List.of() und dann eine weitere mit new ArrayList<>()?

List.of() ist die eleganteste Art eine Liste zu erstellen. Die ist allerdings unveränderlich (was in den meisten Anwendungsfällen von List.of() auch sinnvoll ist) und kann dementsprechend nicht sortiert werden. Daher übergebe ich diese dann an den Konstruktor von ArrayList, der daraus eine veränderliche Liste macht. Zugegeben: nicht die performanteste Lösung, sie macht den Code aber schön kurz.

Collections.sort() prüft übrigens (im Gegensatz zu Arrays.sort()) schon zur Compile-Zeit, ob die übergebene Liste aus Objekten besteht, die Comparable implementieren.

Liste sortieren mit Collections.sort() und einem Comparator

Auch einen Comparator kann man Collections.sort() mitgeben. Folgende Code-Zeile sortiert die Kunden nach Namen:

Collections.sort(customers, Customer.NAME_COMPARATOR);Code-Sprache: Java (java)

Liste sortieren mit List.sort()

Seit Java 8 gibt es (dank der Default-Methoden in Interfaces) die Möglichkeit eine Liste direkt mit List.sort() zu sortieren. Dabei muss immer ein Comparator angegeben werden:

customers.sort(Customer.NAME_COMPARATOR);Code-Sprache: Java (java)

Der Comparator darf allerdings auch null sein, um die Liste entsprechend ihrer natürlichen Ordnung zu sortieren:

customers.sort(null);Code-Sprache: Java (java)

Auch hier bekommen wir eine ClassCastException, wenn die übergebene Liste Objekte enthält, die nicht Comparable implementieren.

Arrays parallel sortieren

Seit Java 8 steht jede der Sortiermethoden aus der java.util.Arrays-Klasse auch in einer parallelen Variante zur Verfügung. Diese verteilt den Sortieraufwand ab einer festgelegten Array-Größe (8.192 Elemente von Java 8 bis Java 13; 4.097 Elemente seit Java 14) auf mehrere CPU Cores. Ein Beispiel:

• static void parallelSort(double[] a)

Das folgende Beispiel misst die benötigte Zeit für das Sortieren von 100 Millionen double-Werten einmal mit Arrays.sort() und einmal mit Arrays.parallelSort():

public class DoubleArrayParallelSortDemo {
  private static final int NUMBER_OF_ELEMENTS = 100_000_000;

  public static void main(String[] args) {
    for (int i = 0; i < 5; i++) {
      sortTest("sort", Arrays::sort);
      sortTest("parallelSort", Arrays::parallelSort);
    }
  }

  private static void sortTest(String methodName, Consumer<double[]> sortMethod) {
    double[] a = createRandomArray(NUMBER_OF_ELEMENTS);
    long time = System.currentTimeMillis();
    sortMethod.accept(a);
    time = System.currentTimeMillis() - time;
    System.out.println(methodName + "() took " + time + " ms");
  }

  private static double[] createRandomArray(int n) {
    ThreadLocalRandom current = ThreadLocalRandom.current();
    double[] a = new double[n];
    for (int i = 0; i < n; i++) {
      a[i] = current.nextDouble();
    }
    return a;
  }
}Code-Sprache: Java (java)

Mein System (DELL XPS 15 mit Core i7-8750H) gibt folgende Messwerte aus:

sort() took 9596 ms
parallelSort() took 2186 ms
sort() took 9232 ms
parallelSort() took 1835 ms
sort() took 8994 ms
parallelSort() took 1917 ms
sort() took 9152 ms
parallelSort() took 1746 ms
sort() took 8899 ms
parallelSort() took 1757 msCode-Sprache: Klartext (plaintext)

Die jeweils ersten Aufrufe dauern etwas länger, da der HotSpot-Compiler etwas Zeit braucht, um den Code zu optimieren.

Danach ist gut zu sehen, wie das parallele Sortieren etwa fünf mal schneller ist als das sequentielle. Für sechs Cores ist das ein sehr gutes Ergebnis, da die Parallelisierung natürlich auch einen gewissen Overhead mit sich bringt.

Sortieralgorithmen im Java Development Kit (JDK)

Im JDK werden je nach Aufgabenstellung verschiedene Sortieralgorithmen angewendet:

• Counting Sort für byte[], short[] und char[], wenn mehr als 64 Bytes bzw. mehr als 1750 Shorts oder Characters sortiert werden.
• Dual-Pivot Quicksort für das Sortieren primitiver Datentypen mit Arrays.sort(). Hierbei handelt es sich um eine optimierte Variante von Quicksort, kombiniert mit Insertion Sort und Counting Sort. Der Algorithmus erreicht eine Zeitkomplexität von O(n log n) bei vielen Eingabedaten, für die andere Quicksort-Implementierungen in der Regel auf O(n²) zurückfallen.
• Timsort (ein optimiertes Natural Mergesort kombiniert mit Insertion Sort) für alle anderen Objekte.

Beim parallelen Sortieren werden folgende Algorithmen angewendet:

• Bytes, Shorts, Characters werden niemals parallel sortiert.
• Für andere primitive Datentypen wird eine Kombination aus Quicksort, Mergesort, Insertion Sort und Heapsort eingesetzt.
• Für Objekte wird ebenfalls Timsort eingesetzt - die parallele Variante allerdings erst bei einer Listengröße von mehr als 8.192 Elementen; darunter wird die Single-Threaded Variante verwendet, da ansonsten der Overhead größer ist als der Gewinn.

Zusamenfassung

Du hast in diesem Artikel gelernt (oder aufgefrischt), wie du in Java primitive Datentypen und Objekte sortieren kannst und welche Sortierverfahren das JDK intern anwendet.

Wenn dir der Artikel gefallen hat, teile ihn gerne über einen der Share-Buttons am Ende. Möchtest du per E-Mail informiert werden, wenn ich einen neuen Artikel veröffentliche? Dann klicke hier, um dich in den HappyCoders-E-Mail-Verteiler einzutragen.