© 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ä...

Neugierig geworden?

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