Sortieren und Suchen WS13-14
Inhaltsverzeichnis |
Einleitung
Sortieren
Elementare Sortierverfahren
Selection Sort
Bubble Sort
Suchen
Einführung
Das Suchen nach Daten ist eine der wichtigsten Aufgaben eines Computers, da es weitere grundlegende Operationen wie das Ersetzen, Löschen oder Ändern von Daten erst ermöglicht. Aufgrund dieser hohen Priorität sind Suchverfahren sehr gut hinsichtlich ihres Aufwandes erforscht. Suchen ist dabei das Finden von Mustern oder Objekten mit bestimmten Eigenschaften in einem Suchraum. Beispiele sind Zeichenketten aus einem Text oder Zahlen aus einer Liste von Zahlen. Betrachtet werden auch die Datenstrukturen, auf welche die Verfahren angewendet werden können (elementare oder effizientere, wie Bäume). Außerdem ist zu prüfen, ob eine Vorsortierung des Suchraumes notwendig, effizienzverbessernd oder unnötig ist. In diesem Kapitel werden verschiedene Suchverfahren mit ihren Aufwänden vorgestellt, von einfachen schrittweisen Suchen und deren Verbesserungen hin zu komplexen Suchvorgängen in Bäumen.
Lineare Suche
Die Lineare oder sequentielle Suche ist nur (effizient) anwendbar auf kleine Suchräume und selten stattfindenen Suchoperationen. Nötig ist ein Element e, welches mit dem Suchschlüssel s verknüpft ist. Dieser kann als Attribut des Elements gewertet werden. Es wird immer nach dem Suchschlüssel gesucht! Bei Zahlen wird der Suchschlüssel meist dem Zahlenwert entsprechen, doch kann beispielsweise einem Buchstabe eine Zahl zugeordnet werden und durch Suche nach einer bestimmten Zahl erhält man den Buchstaben. Bei der Linearen Suche wird nun der Suchraum sequentiell, d.h. Element für Element, betrachtet und der Suchschlüssel mit dem Suchschlüssel des zu suchenden Elements verglichen.
Binäre Suche
Fibonacci Suche
Binäre Suchbäume
Rot-Schwarz-Bäume
Hashing
Extern
Intern
String-Matching
Interpolationssuche
Übungen
Literaturverzeichnis
- Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung,Oldenbourg Verlag, 2007
- Sedgewick, Robert: Algorithmen, Addison-Wesley, 1992
- Heun, Volker: Grundlegende Algorithmen, Vieweg, 2000
- Mehlhorn, Volker: Datenstrukturen und effiziente Algorithmen Band 1 Sortieren und Suchen, B. G. Teubner Stuttgart, 1988
Kontakt
Sollten während der Nacharbeitung der Vorlesung Fragen auftreten, können diese gern gestellt werden.