© Ozz Design/Shutterstock.com
Teil 1: Die Grundlagen der Sortier- und Suchalgorithmen

Wer aufgeräumt hat, muss nicht suchen


Sortier- und Suchalgorithmen gehören zu den Basiskonzepten der Informatik. In Datenstrukturen wie Arrays, Listen und davon abgeleiteten modernen Formen nach den richtigen Informationen zu suchen, ist für eine Vielzahl von Anwendungen notwendig.

Man könnte hier einwenden: das macht doch meine Bibliothek von allein, ein Aufruf der passenden Funktion und fertig. So kann man mit Hilfe von sort(array, sorttype) eine einfache Datenstruktur in PHP sortieren. Das ist grundsätzlich richtig, aber es gibt zum Thema Suchen und Sortieren natürlich eine Menge mehr zu wissen. Spätestens dann, wenn man in umfassenden Datenbeständen suchen muss oder eine große Anzahl von Elementen zu sortieren hat, muss man sich damit intensiver beschäftigen. Wir wollen uns in einer zweiteiligen Artikelserie mit dem Thema vertraut machen.

In diesem Artikel geht es um die Grundlagen des Sortierens und Suchens. Das ist wichtig, um zum Beispiel bei umfassenden Suchaufgaben zu entscheiden, ob man ein leistungsfähigeres Suchverfahren benötigt. Das eingesetzte Suchverfahren entscheidet darüber, wie lange (im Durchschnitt) eine Suche dauert. Das kann bei sehr umfassenden Datenbeständen entscheidend sein. Sind Such- und Sortiervorgänge in der Praxis umzusetzen, dann muss man mit Blick auf Webapplikationen u. a. die folgenden Fragen beantworten:

  • Wie umfassend ist der Suchraum, welche Menge an Objekten muss durchsucht werden?

  • Welche Anforderungen an die Performance werden gestellt, wie viel Zeit ist vorhanden, um den Suchvorgang im Durchschnitt erfolgreich zu beenden?

  • Genügt es, die Standardsuche der Programmiersprache (PHP, JavaScript) anzuwenden, oder sollte man eine spezielle Library mit ausgewählten Suchalgorithmen einbinden?

  • Kommt man mit einem einfachen Suchverfahren zum Ziel, oder ist der Suchraum so komplex, dass man ein heuristisches Verfahren einsetzen muss?

  • Wo soll die Suche nach den relevanten Objekten durchgeführt werden? Bei Webapplikationen haben wir die Wahl zwischen einer Suche auf dem Server (PHP) und/oder dem Client (JavaScript). Suchen wir auf dem Server, ermitteln wir zunächst die relevanten Objekte und liefern sie an den Client aus. Suchen wir auf dem Client, müssen wir alle Objekte bereitstellen und dann das gewünschte Objekt suchen.

Sortier- und Suchverfahren bedingen einander, daher werden sie in der Regel gemeinsam betrachtet. Mit anderen Worten: „Wer sortiert hat, muss nicht suchen“, oder es geht zumindest viel schneller.

Suchverfahren im Überblick

Suchverfahren sind Algorithmen, die einen Suchraum nach einem bestimmten Muster oder dem Vorhandensein eines Objekts durchsuchen. Man unterscheidet einfache und heuristische Suchalgorithmen. Einfache Suchalgorithmen durchsuchen den Suchraum mit einem intuitiven Vorgehen. Diese systematische Vorgehensweise führt zwar theoretisch immer zum Ziel, es kann jedoch bei einem sehr großen Suchraum zu lange dauern. Dazu ein simples Beispiel: Stellen Sie sich vor, alle Bücher einer großen Bibliothek würden vollständig unsortiert in den Regalen stehen, weder nach Namen der Autoren noch nach Titel sortiert. Suchen Sie ein Buch mit einem bestimmten Titel, bleibt Ihnen nichts anders übrig, als alle Bücher der Reihe nach zu betrachten. Im Idealfall ist gleich das erste Buch ein Treffer; im schlechtesten Fall das letzte. Im Durchschnitt werden Sie (n/2) Bücher prüfen müssen, wenn n die Gesamtzahl der Bücher in der Bibliothek ist. Zur Lösung einer solchen Aufgabe braucht es einen Algorithmus. Zu den einfachen Suchalgorithmen gehören:

  • lineare Suche (sequenzielle Suche)

  • binäre Suche

  • Suche in Bäumen

  • Suche in Graphen

Gegenüber einfachen Suchverfahren nutzen heuristische Suchalgorithmen das Wissen über den Suchraum (beispielsweise die Datenverteilung), um die benötigte Suchzeit zu reduzieren. Kommen wir als Erstes zu den einfachen Suchverfahren.

Lineare (sequenzielle) und binäre Suche

Die sequenzielle Suche beruht auf dem Ansatz, einen Datenbestand vollständig zu durchsuchen, bis das passende Element gefunden wird. Man prüft also jedes einzelne Element darauf, ob es dem Suchkriterium entspricht. Der Algorithmus hat demzufolge den folgenden Ablauf:

  1. Lege des Suchschlüssel fest.

  2. Vergleiche jedes Element mit dem Suchschlüssel.

  3. Führe folgende Prüfung durch. Im Erfolgsfall: Liefere die Indexposition beim ersten Auffinden des Objekts und beende das Suchen. Kein Erfolg: Gehe zum nächsten Objekt und vergleiche es.

  4. Gib eine Meldung über das erfolglose Suchen zurück, wenn das Ende des Datenbestands erreicht wurde, ohne dass das Objekt gefunden wird.

Der Aufwand für diesen Algorithmus ist linear, also O(n). Die Anzahl der nötigen Vergleichsoperationen hängt direkt von der Anzahl der Elemente (n) im Datenbestand ab. Im Durchschnitt sind dies (n/2) Vergleiche.

Sind die zu durchsuchenden Elemente geordnet, kann man die binäre Suche anwenden. Das ist im Vorfeld ggf. über einen Sortieralgorithmus sicherzustellen. Die binäre Suche erfolgt nach dem Prinzip „Teile und herrsche“, dazu teilt man die zu durchsuchenden Daten in zwei Hälften und ermittelt dann, in welcher Hälfte das zu suchende Element vorkommt. Die andere Hälfte kann ignoriert werden. So wird bereits in dem ersten Suchschritt die Menge der zu durchsuchenden Daten um 50 Prozent reduziert. Bei der binären Suche ist der Zeitaufwand nur noch O(N) = log2 n, also erheblich geringer als bei der linearen Suche.

Suche in Bäumen

Bei binären Suchbäumen (engl. Binary Search Tree) handelt es sich um eine spezielle Datenstruktur (Kasten: „Begriffe rund um den Baum in der Informatik“).

Dabei sind die Elemente im linken Teilbaum stets kleiner als die Wurzel. Im Gegensatz dazu sind alle Elemente im rechten Unterbaum stets größer als die Wurzel. Jeder Knoten besitzt höchstens zwei Kinder. Das Ziel ist es, die Suchvorgänge zu verkürzen. Besonders wichtig ist das bei umfangreichen Datenbeständen. Das Durchlaufen eines Baums wird auch als Traversierung bezeichnet. Folgende Durchlaufordnungen von Binärbäumen sind üblich:

  • Preorder-Reihenfolge

  • Postorder-Reihenfolge

  • Inorder-Reihenfolge

Bei der Preorder-Reihenfolge wird zuerst die Wurzel des Baums besucht. Danach werden rekursiv der linke und dann der rechte Teilbaum durchlaufen. Der Ablauf:

Besuche den...

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