© GreenFlash/Shutterstock.com
Teil 2: Sortier- und Suchalgorithmen - ein Überblick

Algorithmen in der Java-Praxis


Sortier- und Suchalgorithmen gehören zu den Basisalgorithmen und sind in vielen Klassenbibliotheken implementiert. Muss man sehr umfassende Datenbestände sortieren oder in diesen suchen, spielt die Vorgehensweise aus Gründen der Performance eine wichtige Rolle. Parallel Computing kann das Sortieren beschleunigen. Auch diese Verfahren basieren auf den Basisverfahren. Es gibt also genügend Gründe, diesen auf den Grund zu gehen.

In diesem Teil der Artikelserie beschäftigen wir uns mit Sortier- und Suchverfahren in Theorie und Praxis. Die theoretischen Erkenntnisse befähigen uns zum einen, die Verfahren zu verstehen, und zum anderen, deren Leistungsfähigkeit, insbesondere mit Blick auf die Verarbeitungsgeschwindigkeit, zu beurteilen. Man sollte zunächst das Chaos sortieren, bevor man sich an die Suche macht. Was im Alltag gilt, hat auch seine Berechtigung in der Informatik. Starten wir mit den Sortieralgorithmen und gehen dann über zum Suchen in den Daten.

Grundlagen des Sortierens

Mit Hilfe eines Algorithmus möchte man eine Menge von Objekten in eine definierte Reihenfolge bringen. Um welche Art von Objekten es sich handelt, spielt dabei keine Rolle. Im einfachsten Fall handelt es sich um eine Menge (Liste) von Zahlen, die zum Beispiel in eine aufsteigende Reihenfolge gebracht werden sollen. Grundsätzlich können wir jedoch beliebige Objekte sortieren. Voraussetzung dafür ist, dass es ein Sortierkriterium gibt, nach dem das Sortieren erfolgt. Dieses Sortierkriterium (Key) muss es erlauben, dass man die Objekte miteinander vergleichen kann. Es müssen also Vorgänger- und Nachfolgerbeziehungen zwischen zwei zu vergleichenden Elementen bezüglich des Sortierkriteriums herstellbar sein. Typische Beispiele sind die lexikographische Ordnung von Zeichenketten oder die numerische Ordnung von Zahlen. Diese Forderung wird als Trichotomie bezeichnet und besagt, dass für alle Elemente einer Menge bezüglich deren Schlüssel a und b gilt:

  • a < b oder

  • a = b oder

  • a > b

Die Transitiviät gewährleistet, dass die Sortierung widerspruchsfrei durchgeführt wird: Ist das Element a vor dem Element b und das Element b vor dem Element c in der Liste einzusortieren, so folgt unweigerlich, dass das Element a vor dem Element c anzuordnen ist. Eine andere Reihenfolge wäre unlogisch. Für den Datentyp Zahl muss man diese Vergleichsoperationen nicht explizit implementieren, da sie implizit in jeder Programmiersprache vorhanden sind. Mit anderen Worten: Dass der Zusammenhang 2 ist kleiner als 3 gilt, ist offensichtlich und führt in der Logik der Programmiersprache (2 < 3) zu einer wahren Aussage. Möchte man andere (beliebige) Objekte miteinander vergleichen, muss man die Vergleichsoperationen explizit programmieren. In Java würde man das zum Beispiel tun, indem man die Klassen Comparable und Comparator nutzt. Dabei bedeuten:

  • Comparable: Implementiert eine Klasse Comparable, so können sich die Objekte selbst mit anderen Objekten vergleichen.

  • Comparator: Eine implementierende Klasse, die sich Comparator nennt, nimmt zwei Objekte an und vergleicht sie.

Im ersten Fall ist die Vergleichsfunktion Bestandteil der Funktionalität der Klasse des Objekts, im zweiten Fall ist der Vergleich nicht in der Klasse, sondern extern im Comparator implementiert. Mit Comparable kann man nur ein Vergleichskriterium pro Datenklasse implementieren, da es nur eine Methode compareTo(…) gibt. Mittels Comparator kann man dagegen mehrere Vergleichskriterien integrieren, sofern das notwendig ist. Das Interface Comparable hat folgende Syntax:

public interface Comparable { public int compareTo(Object o); }

Die Klasse Comparator ist wie folgt definiert:

public interface Comparator { int compare(Object o1, Object o2); boolean equals(Object o); }

Betrachten Sie dazu Listing 1. Wir implementieren eine Datenklasse namens Person, die das Interface Comparable implementiert. Diese muss nun die Methode compareTo(…) beinhalten. Diese Methode nimmt den Vergleich der Werte des Objekts mit den Werten eines anderen Objektes der gleichen Datenklasse, hier der Klasse Person vor. Die Vergleichsoperation ist damit also Bestandteil der Datenklasse. In Listing 2 haben wir dagegen eine eigene Klasse ComparatorForPerson definiert. Diese übernimmt das Vergleichen von zwei Objekten der Klasse Person. Das Ergebnis des Vergleichs wird bei beiden Varianten über den ganzzahligen Rückgabewert (-1; 0; 1) mit der Bedeutung (kleiner als, gleich, größer als) angegeben.

Listing 1: Datenklasse, die das Interface Comparable implementiert

public class Person implements Comparable<Person> { private String name; public Person(String name) { this.name = name; } public String getName() { return name; } @Override public int compareTo(Person o) { if(o == null) return -1; else if(o.getName() == null && name == null) return 0; else if(o.getName() != null && name == null) return -1; else if(o.getName() == null && name != null) return 1; else return name.compareTo(o.getName()); } }

Listing 2: Klasse ComparatorForPerson zum Vergleichen der Objekte der Klasse Person

public class ComparatorForPerson implements java.util.Comparator<Person> { @Override public int compare(Person o1, Person o2) { if(o1 == null && o2 == null) return 0; else if(o1 == null && o2 != null) return -1; else if(o1 != null && o2 == null) return 1; else return o1.getName().compareTo(o2.getName()); } }

Wichtige Gütemerkmale eines Sortieralgorithmus sind die Zahl der durchschnittlich benötigten Iterationen, bis die gewünschte Reihenfolge der Elemente vorliegt, und der benötigte Speicherplatzbedarf. Die Zahl der Iterationen gibt die Komplexität des Algorithmus an. In diesem Zusammenhang spricht man auch von den Kosten des Sortierens. Sortierverfahren können in interne und externe Verfahren unterteilt werden. Ist es möglich, die zu sortierenden Daten komplett im Hauptspeicher, d. h. innerhalb einer Datenstruktur, zum Beispiel einem Array, zu sortieren, so liegt ein internes Verfahren vor. Bei größeren Datenbeständen ist es nicht handhabbar, sämtliche Daten innerhalb des Arbeitsspeichers zu halten. Zum Einsatz kommen dann externe Speichermedien. Bei externen Algorithmen ist die Effizienz besonders wichtig, da die Lese- und Schreibzugriffe dann einen relativ hohen Zeitbedarf beanspruchen. Ein Sortieralgorithmus wird als stabil bezeichnet, wenn er die relative Reihenfolge von Elementen beibehält, die den gleichen Wert bezüglich des Sortierschlüssels aufweisen. Ein Beispiel: Es liegt eine Liste mit Namen und Alter der Personen vor, die alphabetisch sortiert ist. Diese soll nach dem Alter sortiert werden. Ein stabiler Algorithmus gewährleistet, dass nach dem Sortiervorgang Personen mit dem gleichen Alter weiterhin alphabetisch sortiert sind. Ist ein Sortieralgorithmus zunächst nicht stabil, kann man diesen über Modifikationen i. d. R. als stabile Variante implementieren. Typische und bekannte Sortieralgorithmen sind:

  • Selection Sort

  • Insertion Sort

  • Bubble Sort

  • Mergesort

  • Q...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Teams

Für Firmen haben wir individuelle Teamlizenzen. Wir erstellen Ihnen gerne ein passendes Angebot.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang