Einleitung

Sortieren

Einführung

Elementare Sortierverfahren

Selection Sort

Selection Sort (Sortieren durch Auswählen) wählt wiederholt das kleinste Element im Feld aus.

Ablauf

Man sucht das kleinste Element im Feld und tauscht es mit dem an der ersten Stelle befindlichen Element. Im nächsten Schritt wählt an das zweitkleinste Element und tauscht es mit dem Element an der zweiten Stelle aus. Dieser Vorgang wird sooft wiederholt bis das komplette Feld sortiert ist, also bis das komplette Feld einmal durchlaufen wurde.

Leistungsfähigkeit

Selection Sort besitzt im schlechteste und im durchschnittlichen Fall einen quadratischen Aufwand \mathcal O(n^2). Die Ausführung dieses Verfahrens benötigt keinen zusätzlichen Speicherplatz. Der Durchlauf benötigt ca. \frac{n^2}{2} Vergleiche und n Austauschoperationen, da für jedes Feld von 1 bis n-1 jeweils 1 Austausch und insgesamt (n-1)+(n-2)+...+2+1 Vergleiche notwendig sind. Dies ist jedoch unabhängig von den Eingabedaten, abhängig ist nur die Anzahl der Wertwechsel von Minimum. Im Durchschnitt liegt die Laufzeit dieser Anzahl in \mathcal O(n \log n), so dass man sagen kann, dass die Laufzeit von Selektion Sort relativ unempfindlich gegenüber der Eingabedaten ist.

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.

Dana Müller

Robert Stricker