Suchen und Sortieren

Das einfachste Verfahren, in einem Datenbestand einen Datensatz mit einem bestimmten Merkmal zu suchen, besteht darin, nacheinander bei jedem Datensatz zu prüfen, ob er dieses Merkmal besitzt. Der Vorgang wird beendet, wenn der Datensatz gefunden wurde. Das Verfahren heißt "lineare Suche". In diesem Kapitel wird ein Java-Programm zur linearen Suche in einem Array entwickelt.

Das Sortieren gehört – neben dem Suchen – zu den am häufigsten anfallenden Aufgaben, die ein Computer zu erledigen hat.

Für den Menschen sichtbar wird das Sortieren vor allem bei der Ausgabe von Informationen auf dem Bildschirm. Egal, ob im Dateibrowser, einem Mediaplayer oder in einer Tabellenkalkulation – sortierte Daten sind für den Menschen leichter zu erfassen und zu überblicken. Deshalb kann in der Regel auch nach unterschiedlichsten Kriterien sortiert werden. Bei Dateien ist in der Regel u.a. eine Sortierung nach dem Namen, der Dateigröße oder das Änderungsdatum möglich, bei Liedern kann z.B. nach Interpret, Titel oder Laufzeit sortiert werden.

Liegen die Daten in sortierter Form vor, führt auch die Suche nach einem bestimmten Datensatz deutlich schneller zum Erfolg – das gilt auch für Computer (s. Kapitel „Binäre Suche“). Aus diesem Grund wird auch bei der internen Datenhaltung von Programmen häufig eine sortierte Anordnung bevorzugt.

Im Laufe der Jahre haben Informatiker eine Vielzahl von Sortieralgorithmen entwickelt, die unterschiedliche Vor- und Nachteile mit sich bringen. In diesem Kapitel werden Sie einige grundlegende Sortierverfahren sowie ihre Besonderheiten hinsichtlich Zeitaufwand und Speicherbedarf kennenlernen.

Ein Telefonbuch ist alphabetisch nach den Hausnamen und dann nach den Vornamen sortiert. Daher kann man die Telefonnummern einer bestimmten Person sehr viel schneller finden als mit linearer Suche. In diesem Kapitel wird das Verfahren der binären Suche erarbeitet und in Java implementiert.