In vielen Bereichen der Programmierung ist es wichtig, eine gemeinsame Festlegung von Begrifflichkeiten zu etablieren, um klare Definitionen zu entwickeln und damit ein gegenseitiger Austausch über bestehende Problematiken möglich wird.

In diesem Fall möchten wir uns mit den im Alltag vielschichtig belegten Begriffen Reihenfolge, Ordnung und Sortierung beschäftigen und sie in Java, insbesondere in Hinsicht auf Collections, einleuchtend definieren.

Hinweis: Die in diesem Beitrag verwendeten Definitionen können mit denen in der Literatur kollidieren. Dies liegt in der erwähnten Vielschichtigkeit der Begriffe in ihrer Alltagsverwendung und auch mit der Vermischung mit englischen Übersetzungen, so dass sie andere Autoren auf andere Art und Weise verstehen. Trotzdem sollte die hier getroffene Wahl des Autors direkt einleuchtend erscheinen. Im Allgemeinen ist es – wie erwähnt – hauptsächlich wichtig, sich auf gemeinsame Begrifflichkeiten zu einigen.

(Feste) Reihenfolge

Mit einer (festen) Reihenfolge einer Collection ist eine geordnete, reproduzierbare Iterationsreihenfolge gemeint. Dies bedeutet, dass eine Iteration über eine Collection immer zu einem gleichen Ergebnis mit der gleichen Reihenfolge führt.

Würden beispielsweise die Strings „Collections“, „sind“ und „toll!“ in einer Collection gespeichert, so gibt ein Collectiontyp mit (fester) Reihenfolge jedes Mal

Collections sind toll!

beim vollständigen Iterieren aus, während ohne (feste) Reihenfolge auch

toll! Collections sind	toll! sind Collections	sind toll! Collections
sind Collections toll!	Collections toll! sind

möglich wären.

Ursache für eine vorhandene oder nicht vorhandene Reihenfolge ist natürlich der unterschiedliche, strukturelle Aufbau der verschiedenen Collectionstypen. Dieser soll im Folgenden, anhand verschiedener Verkettung von LEGO-Steinen, illustriert werden.

Hinweis: Die Darstellungen dienen lediglich der Illustration der Datenstruktur und sagen wenig über andere grundlegende Eigenschaften aus

Wie an der Illustration zu erahnen, verfügen alle Lists (über den Index), Linked-Collections (Verkettung mit letztem und nächstem Element), Queues / Deques (Stack-Struktur) und Tree-Collections (Baum-Struktur) über einen Aufbau, der eine feste, reproduzierbare Iteraration erlaubt und besitzen folglich eine (feste) Reihenfolge.

Sets und Maps hingegen können lediglich garantieren, dass alle Elemente ausgelesen werden, die Iteration erfolgt jedoch zufällig. Wie beim Greifen in einen nicht-einsehbaren Beutel ist der Zugriff nicht festgelegt. Maps und Sets verfügen also, im oben definierten Sinne, über keine (feste) Reihenfolge!

Sortierung / Ordnung

Sortierung kann nur etabliert beziehungsweise Ordnung kann nur hergestellt werden, wenn die Elemente einer Collection vergleichbar sind. Sortierung und Ordnung bezieht sich also nicht auf die Iterationsreihenfolge einer Collection, sondern auf sich unterscheidende Eigenschaften ihrer Elemente. Sortierung innerhalb einer Collection ist das In-Sortierabfolge-Bringen vergleichbarer Elemente.

Hinweis: Im Weiteren wird lediglich der Begriff „Sortierung“ verwendet werden. „Ordnung“ enthält im Deutschen zu viele Sub-Bedeutungen und kann daher zu Verwirrung führen.

In Java unterscheidet man zwei Sortierungs-Arten:

Natürliche Sortierung

Ein Element einer Collection enthält seine natürliche Sortierung über die compareTo() Methode im Interface Comparable. Die Implementierung des Interfaces muss dabei innerhalb der Element-Klasse erfolgen. Beispiele für bekannte natürliche Sortierungen sind Integer (numerisch sortiert) und Strings („alphabetisch“ sortiert), was sich aber natürlich auch für jedes beliebige Objekt festlegen lässt:

public class Car implements Comparable<Car> {

       public String modelName;

       public LocalDate productionYear;

       public Integer powerInHp;

       @Override

       public int compareTo(Car car) {

             return this.modelName.compareTo(car.modelName);

       }

}

Die Klasse Car hat hier also seine natürliche Sortierung über den Vergleich der Automodell-Namen erhalten. Verwendet wurde dabei die compareTo- Methode der Strings-Klasse.

Sortierungsmethoden wie Collections.sort() (ohne Parameter) greifen automatisch auf die natürliche Sortierung ihrer Elemente zurück, was sich dadurch sehr einfach implementieren lässt.

ArrayList<Car> carList = new ArrayList<Car>();

             // carList füllen….

             Collections.sort(carList);

Es gibt jedoch nur eine einzige Möglichkeit, die natürliche Art der Sortierung festzulegen. Zudem ist es ohne den Zugriff auf das Element (hier Car), also für alle extern definierte Objekte, nicht möglich, eine natürliche Sortierung zu definieren. Möchte man also auf viele verschiedene Weisen sortieren oder hat keinen direkten Zugriff, greift man auf den Comparator zurück:

Individuelle Sortierung

Um eine Collection nach eigenen Kriterien (nicht natürlich) sortieren zu können, braucht man eine Klasse, die  das Interface Comparator implementiert und über die Methode compare(obj1, obj2) eine Vergleichs- und damit eine Sortiervariante definiert. Um im obigen Beispiel eine Sortierung nach Produktionsjahr zu erreichen, benötigt man den folgenden Comparator:

public class ProductionYearCompare implements Comparator<Car> {

@Override

       public int compare(Car car1, Car car2) {

             if (car1.produtionYear.isBefore(car2.produtionYear)) {

                    return -1;

             } else if (car1.produtionYear.isAfter(car2.produtionYear)) {

                    return 1;

             } else

                    return 0;

       }

}

Sortiert werden kann nun über

Comparator<Car> yearCompare = new ProductionYearCompare();

Collections.sort(carList, yearCompare);

In der sort()-Methode wurde dabei der neue Comparator übergeben. Eleganter beziehungsweise kürzer lässt sich dies seit Java 8 mit den Lambda Expressions realisieren, die hier nach PS-Zahl der Cars sortiert.

Collections.sort(carList, (car1, car2) -> car2.powerInHp – car1.powerInHp);

Welche Collections lassen sich sortieren?

Wie schon erwähnt, ist eine Sortierung von Collections nur möglich, wenn ihr Elemente vergleichbar sind. Als elementare Voraussetzung gilt dies nur für die Trees und die PriorityQueue, die zu jedem Zeitpunkt sortiert sind:

Hinweis: Die Vergleichbarkeit der Elemente ist hier mit unterschiedlichem Rot-Anteil gekennzeichnet.

Andere Collections müssen erst einen Vergleich definieren, um sortierbar zu sein:

Wie auch bei der Reihenfolge, spielen Sets und Maps eine Sonderrolle. Eine Vergleichbarkeit kann (ohne dass beide in eine Linked- oder Tree-Struktur eingebettet werden) nicht hergestellt werden. Ohnehin wäre so ein Vorgehen nicht sinnvoll, denn auch mit vorhandener Vergleichbarkeit hätten die Strukturen keine feste Reihenfolge und könnten nicht in sortierter Reihenfolge ausgegeben werden.

Eine Sortierung ist ohne (feste) Reihenfolge nicht möglich!

Dies führt uns zu der Frage, ob es eine (feste) Reihenfolge ohne Sortierung gibt. Dies ist leicht zu beantworten: Alle Collections mit (fester) Reihenfolge, ohne die Definition eines Vergleichs (siehe Abbildung 1) erfüllen diese Bedingung.

Eine (feste) Reihenfolge ohne Sortierung ist möglich!

Fazit

• Die Begriffe Reihenfolge, Ordnung und Sortierung konnten auf sinnvolle Weise festgelegt werden. Eine (feste) Reihenfolge ist dabei eine geordnete, reproduzierbare Iterationsreihenfolge, während Sortierung (beziehungsweise Ordnung) als das In-Sortierabfolge-Bringen vergleichbarer Elemente bedeutet
• Bezogen auf Collections hat die Reihenfolge zu tun mit der zugrundeliegenden Datenstruktur und ist somit gegeben für alle Lists, alle Queues/Deques, alle Linked-Strukturen und alle Tree-Strukturen. Keine Reihenfolge besitzen Sets und Maps (ohne Einbettung in andere Strukturen).
• Sortierung hat mit der Festlegung einer Vergleichbarkeit der Elemente zu tun und ist damit auf natürliche Weise gegeben für Trees und Priority Queue. Andere Strukturen können durch Definition eines Vergleichs eine Sortierung etablieren, für Maps und Sets ist dies (ohne externe Strukturierung) nicht möglich.
• Vergleichbarkeit lässt sich  entweder natürlich – Element-bezogen über die compareTo-Methode – oder individuell – über einen externen Comparator und der compare(obj1, obj2)-Methode – etablieren
• Eine (feste) Reihenfolge ist Bedingung für eine Sortierung, andersherum gilt dies jedoch nicht