Vergleichen und Sortieren 🍱

Sortieralgorithmen

Ein Sortieralgorithmus ist ein 👉 Algorithmus, dessen Aufgabe es ist, Daten bzw. Objekte zu sortieren. Es sollen hier keine konkreten Sortier-Algorithmen im Detail besprochen werden, denn dazu findet man im Internet ausreichend viel Material (siehe auch die Links unten!).

Es lohnt sich aber zu wissen, dass es unterschiedliche Sortieralgorithmen mit unterschiedlichen Vor- und Nachteilen gibt. Manche sind sehr langsam, dafür aber leicht zu verstehen; manche sind unglaublich effektiv und sehr kompliziert, stellen sich aber in ganz bestimmten Szenarien doch als langsam heraus. Ein Besuch auf den folgenden Seiten ist zur Vertiefung des Themas empfehlenswert:

🔗 Einige sehr gute Erläuterungen zu einzelnen Sortieralgorithmen findest du hier.

🔗 Hier findest du eine Seite mit sehr schönen Visualisierungen verschiedener Sortier-Algorithmen

Sortieren mit Mitteln des Collections Framework

Das Collections Framework bietet eine einfache Möglichkeit, Listen zu sortieren. Listen sind die einzige Art von Collection, die unabhängig von der Implementation immer eine Ordnung haben (sollten) - somit bietet sich eine Liste für eine Sortierung natürlich an:

//Liste erstellen, Lieblingswörter hinzufügen
List<String> myFavoriteWords = new ArrayList<String>();
myFavoriteWords.add("Faszinationstoleranz");
myFavoriteWords.add("Kein-Erlebnis-Urlub");
myFavoriteWords.add("merkwürdig");
myFavoriteWords.add("abwegig");
myFavoriteWords.add("Rauschgift");
myFavoriteWords.add("Sachverhalt");

//Liste sortieren
Collections.sort(myFavoriteWords);

//Liste ausgeben
System.out.println(myFavoriteWords);

Das Beispiel oben erzeugt folgende Ausgabe:

[Faszinationstoleranz, Kein-Erlebnis-Urlub, Rauschgift, Sachverhalt, abwegig, merkwürdig]

Also die Liste im sortierten Zustand - und zwar alphabetisch (wobei hier Großbuchstaben vor allen Kleinbuchstaben einsortiert werden). Aber wer entscheidet das? Was ist, wenn ich meine Strings nach Länge sortieren möchte? Und was passiert, wenn ich keine List<String> sondern eine List<User>oder List<Animal> habe?
Diese Fragen klären die folgenden Abschnitte…

💬 In Java wurden in den Methoden Arrays.sort() und Collections.sort() lange die Algorithmen Mergesort und Quicksort genutzt. In neueren Versionen (ab Java 7) nutzen beide Methoden stattdessen Timsort.

Das Interface Comparable

Damit überhaupt an eine Sortierung* gedacht werden kann, muss zunächst ein verlässlicher Vergleich** zwischen den zu sortierenden Elementen gemacht werden können:

* Sortierung: [4, 1, 7, 2] wird zu [1, 2, 4, 7]

… funktioniert nur, wenn folgendes klar ist:

** Vergleich: 4 ist größer als 1

Bei primitiven Datentypen ergibt sich meist eine natürliche Sortierung. So gilt eben etwa 1 < 4, aber auch 'a' < 'd' (denn ein char ist nur ein Mapping auf einen numerischen Wert). Und wie ist es bei boolean? false scheint wohl kleiner zu sein als true, denn

List<Boolean> b = new ArrayList<Boolean>();
b.addAll(Arrays.asList(new Boolean[]{true,false,true,false}));
Collections.sort(b);
System.out.println(b);

ergibt [false, false, true, true] (nicht unbedingt überraschend).

Auch bei Strings ergibt sich durch die alphabetische Reihenfolge eine natürliche Sortierung, die in Java bereits berücksichtigt ist. Aber spätestens beim Vergleichen von komplexeren Objekten ist es vorbei mit natürlicher Sortierung: Ist das eine Objekt vom Typ User nun kleiner oder größer als das andere?

Beispiel: Model-Klasse User:

public class User {
	
	private String mail;
	private long lastLoginTimestamp;
	
	public User(String mail, long lastLoginTimestamp) {
		super();
		this.mail = mail;
		this.lastLoginTimestamp = lastLoginTimestamp;
	}
	
	/*
	 * Es folgen Getter und Setter
	 * für die Felder "mail" und "lastLoginTimestamp"
	 * sowie etwaige weitere Methoden...
	 */

}

Um das Problem zu lösen, dass es keine natürliche Sortierung für solche Objekte gibt, kann die entsprechende Klasse das Interface Comparable implementieren. Es schreibt nur eine Methode compareTo() vor, die einen int-Wert zurückgibt. Ist dieser Wert kleiner/gleich/größer als 0, dann ist das Objekt, dessen compareTo()-Methode aufgerufen wurde, kleiner/gleich/größer als das Objekt, mit dem verglichen wurde. Mit Generics wird festgelegt, mit Objekten welchen Typs die Instanzen der Klasse (hier: mit anderen User-Objekten) verglichen werden können:

public class User implements Comparable<User> {
	
	private String mail;
	private long lastLoginTimestamp;
	
	public User(String mail, long lastLoginTimestamp) {
		super();
		this.mail = mail;
		this.lastLoginTimestamp = lastLoginTimestamp;
	}

	@Override
	public int compareTo(User o) {
		return this.mail.compareTo(o.getMail());
	}
	
	/*
	 * Es folgen Getter und Setter
	 * für die Felder "mail" und "lastLoginTimestamp"
	 * sowie etwaige weitere Methoden...
	 */

}

Das obige Beispiel implementiert compareTo() so, dass bei einer Sortierung von User-Objekten alphabetisch nach der EMail-Adresse sortiert würde. Dafür wird ganz einfach die compareTo()-Methode der Klasse String genutzt **.
Eine andere Implementation von compareTo(), bei der nach dem Timestamp des letzten Logins verglichen wird (hier ein long-Wert), könnte etwa so aussehen:

@Override
public int compareTo(User o) {
	return this.lastLoginTimestamp - o.getLastLoginTimestamp();
}

Dadurch würden in einer Sortierung kleinere Werte (also ältere Timestamps) weiter vorne einsortiert. Um dies umzukehren, kehrt man einfach die Rückgabe um: o.getLastLoginTimestamp() - this.lastLoginTimestamp.

Natürlich sind auch alle anderen Sortier-Kriterien denkbar!

Das Interface Comparator

Dieser Abschnitt schließt inhaltlich direkt an Comparable an: Denn das Comparable-Interface ist zwar eine nützliche Schnittstelle zum Vergleichbarmachen von Objekten, aber eben nur für den einen “Standardfall”. In komplexeren Anwendungen ist es durchaus üblich etwa eine Tabelle mit Daten (in deren Zeilen jeweils die Daten eines Daten-Objektes dargestellt sind) mit einem Klick auf den Kopf einer der Spalten nach dem entsprechenden Kriterium zu sortieren.

Für solch eine Funktionalität ist die Implementierung verschiedener Vergleiche notwendig. Mit einer compareTo(...)-Methode kommt man in diesem Fall also nicht weiter. Genau dafür gibt es das Interface Comparator. Es lagert die Logik für den Vergleich zweier Objekte aus der entsprechenden Klasse aus, sodass dann die Instanzen von Comparator (also die Comparators) dort, wo sie gebraucht werden, einfach benutzt und nach Belieben ausgetauscht werden können. Dafür erstellt man eine Klasse und implementiert Comparator. Die einzige Methode dieses Interfaces ist compare(T o1, T o2), wobei T dem Datentyp entspricht, der mit den Generics festgelegt wurde:

public class StringLengthComparator implements Comparator<String> {
	@Override
	public int compare(String o1, String o2) {
		return o1.length() - o2.length();
	}
}

Und fertig ist ein Comparator, der Strings nach ihrer Länge vergleicht. Genau so ist es natürlich ein Comparator denkbar, der User-Objekte (aus dem vorigen Kapitel) z.B. nach der Domain der Mail-Adressen sortiert:

public class UserMailDomainComparator implements Comparator<User> {
	@Override
	public int compare(User o1, User o2) {
		// Domains aus den Mail-Adressen der beiden User extrahieren,
		// indem das "@" und alles davor entfernt wird...
		String mail1 = o1.getMail().replaceAll("^.*?@", "");
		String mail2 = o2.getMail().replaceAll("^.*?@", "");

		// die Domains einfach mit `compareTo()` vergleichen **
		return mail1.compareTo(mail2);
	}
}

Eingesetzt werden kann solch ein Comparator dann in z.B. in einer anderen Variante von Collections.sort():

List<User> users = new ArrayList<User>();
users.add(new User("maxi.musterfrau@art3abs1gg.de"));
// ...usw ...

// sortieren
Collections.sort(users, new UserMailDomainComparator());

Natürlich sollte man lieber die Referenz auf einen vorher erzeugten Comparator übergeben, wenn man diesen mehrmals einsetzen möchte.

💬 Beim programmieren hilft Faulheit sehr oft dabei, den richtigen Weg zu finden!