Sortieren und Suchen WS13-14
Inhaltsverzeichnis |
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.
Insertion Sort
Insertion Sort (Sortieren durch Einfügen) ist flexibler als Selection Sort.
Ablauf
Man betrachtet ein Element nach dem anderen und fügt jedes Element zwischen den bereits betrachteten Elementen (links von ihm) ein. Das Einfügen wird durch Verschieben der größeren Elemente nach rechts realisiert.
Leistungsfähigkeit
Bubble Sort
(Sortieren durch Austauschen)
Ablauf
Man durchläuft das Feld immer wieder und tauscht benachbarte Elemente, wenn nötig. Das Feld ist sortiert, wenn in einem Felddurchlauf kein Austausch mehr nötig ist.
Leistungsfähigkeit
Bei diesem Verfahren ist die Laufzeit abhängig von den Eingabedaten.
- Im besten Fall beträgt sie 1, da nur ein Durchlauf benötigt wird um zu erkennen das die Daten bereits sortiert sind.
- Im schlechtesten Fall werden \frac{n^2}{2} Vergleiche und ebenso viele Austauschoperationen benötigt.
- Der durschnittliche Fall arbeitet nicht wirklich besser als der schlechteste, eine genaue Analyse ist jedoch schwierig.
Shellsort
Ablauf
Leistungsfähigkeit
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. Es sei hierbei auf das No-free-Lunch-Theoreme verwiesen, welches besagt, dass es kein universelles Optimierungsproblem angewandt auf alle Problemmengen gibt. Für die Suchalgorithmen bedeutet dies, dass die Suchverfahren für den speziellen Anwendungszweck besser sein können als andere, nicht aber für alle Anwendungsbereiche.
Lineare Suche
Die Lineare oder sequentielle Suche ist nur (effizient) anwendbar auf kleine Suchräume und selten stattfindenen Suchoperationen. Dafür ist sie sehr leicht zu implementieren und auf unsortierte Suchräume anwendbar. 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. Der Bestcase ist offensichtlich: Das erste Element ist das gesuchte, die Laufzeit liegt in \mathcal O(1). Umgekehrt der Worstcase, wobei keins oder das letzte Element den Suchschlüssel besitzen: \mathcal O(n). Der average-Case lässt sich ebenso leicht bestimmen: Sucherfolg bei der halben Feldlänge, also \frac{n}{2} = 0.5\cdot n=\mathcal O(n).
Binäre Suche
Die Binäre Suche stellt eine Erweiterung der Linearen Suche dar. Das Ziel war es, die nötigen Vergleichsschritte zu minimieren. Angewandt wird das Verfahren bei häufigen Suchoperationen mit statischem Suchraum, da für die Binäre Suche eine Vorsortierung notwendig ist. Bei der Binären Suche wird der Suchschlüssel des Elements in der Mitte des Suchraumes zum Vergleich herangezogen. Je nach Ergebnis des Vergleiches wurde entweder das gesuchte Objekt gefunden(Laufzeit \mathcal O(1)) oder es wird mit einem der Teilbereiche weitergearbeitet. Beim Worstcase muss solange geteilt werden, bis nur noch ein Element im Suchraum vorhanden ist.
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.