AuK/Sortieren und Suchen WS13-14

Wiki-Quelltext dieser Seite.

<language>Java</language>
=Einleitung=

=Sortieren=

==Einführung==
<!-- + Kenngrößen / wichtige Begriffe -->
==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 Worstcase und im Average-Case 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 Average-Case 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.<!-- besonders geeignet für große Datenmengen mit kleinen Schlüsseln-->

===Insertion Sort===
<!-- Kann man vergleichen mit Kartensortierung -->
Insertion Sort (Sortieren durch Einfügen) ist flexibler als Selection Sort.

'''Ablauf'''
Man betrachtet ein Element nach dem anderen und fügt jedes Element an seinem Platz zwischen den bereits betrachteten Elementen (links von ihm) ein. Das Einfügen wird durch Verschieben der größeren Elemente nach rechts realisiert. Das Feld ist vollständig sortiert, wenn das rechte Ende des Feldes erreicht wurde.

'''Leistungsfähigkeit'''
Die Laufzeit des Insertion Sort ist Abhängig von Inversionen. Inversionen beschreiben den Abstand eines Elementes von dessen Postion nach der Sortierung. Um diesen Abstand zu bestimmen zählt man die Anzahl der Elemente links von betrachteten Element, welche größer sind. Im Bestcase besitzt das Verfahren eine Laufzeit von $\mathcal O(1)$, da das Feld nur einmal durchgegangen werden muss um festzustellen, dass es bereits sortiert ist. Im Average-Case benötigt das Verfahren ca. $\frac{n^2}{4}$ Vergleiche und $\frac{n^2}{8}$ Austausche. Im WorstCase verdoppeln sich diese Anzahlen im Vergleich zum Average-Case.

===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 Bestcase beträgt sie $1$, da nur ein Durchlauf benötigt wird um zu erkennen das die Daten bereits sortiert sind.
* Im Worstcase Fall werden $\frac{n^2}{2}$ Vergleiche und ebenso viele Austauschoperationen benötigt.
* Der Average-Case arbeitet nicht wirklich besser als der schlechteste, eine genaue Analyse ist jedoch schwierig.

===Shellsort===
Shellsort ist eine Art Erweiterung von Insertion Sort, wobei auch der Tausch von weit entfernten Elementen ermöglicht wird. Die Elemente werden so umsortiert, dass wenn man jedes h-te Element entnimmt ein sortiertes Feld vorliegt, man nennt dies ''h-sortiert''. Das so entstandene Feld besteht aus $h$ unabhängig sortierten Teilfeldern, welche sich überlagern. Durch das Sortieren von großen $h$ wird das sortieren für kleine $h$ erleichtert.
Diese Prozedur wird mit einer beliebigen Zahlenliste ausgeführt, wobei die Liste mit 1 enden muss.

<!-- Veranschaulichung erstellen!!!! -->
 
'''Ablauf'''

'''Leistungsfähigkeit'''

===Distribution Counting===
Für sehr spezielle Situationen:
* "Sortiere eine Datei von $n$ Datensätzen, die nur Schlüssel enthält, deren Werte voneinander verschiedene Zahlen zwischen $1$ und $n$ sind." Für dieses Problem kann man sehr leicht einen Algorithmus angeben:
<code id="5298d3ab0f8ac">
	public int[] distribution1(int[] feld) {
		int[] hilfe = new int[feld.length];
		for (int i = 0; i < feld.length; i++) {
			hilfe[feld[i] - 1] = feld[i];
		}
		return hilfe;
	}
</code>
<run id="5298d3ab0f970">
int[] eingabe = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
int[] ergebnis =distribution1(eingabe);
for(int i = 0; i < ergebnis.length; i++){
System.out.println(ergebnis[i]);
}
</run>

*"Sortiere eine Datei der Größe $n$, deren Schlüssel ganze Zahlen zwischen $0$ und $m−1$ sind" Falls $m$ nicht zu groß ist, kann die Sortierung mittels Verteilungszählen realisiert werden. Dabei sind mehrere Schleifendurchgänge notwendig: 
# Ein Feld ''count[]'' wird mit $0$ initialisiert. (Da in Java primitive Typen mit $0$ vorbelegt sind, würde dies wegfallen)
# Dem Wert des Feldes in ''count[]'' wird die Anzahl der jeweiligen ganzen Zahlen zugeordnet.
# Die Zahlen der einzelnen Werte werden aufaddiert. 
:Diese aufaddierten Werte können nun genutzt werden um das Eingabefeld zu sortieren. Man untersucht das Feld beginnend von hinten (wieder mittels einer Schleife) und setzt den untersuchten Wert jeweils an die Stelle im Feld dessen Index durch ''count[untersuchter Wert]'' besitzt. Danach wird der Wert von ''count[untersuchter Wert]'' dekrementiert und mit dem nächsten Wert des Eingabefeldes fortgefahren. 

==Quicksort==

<!-- ===Name===
'''Ablauf'''
'''Leistungsfähigkeit'''

Immer:
Name, Ablauf, Effizienz
Eventuell: Ordnung nach intern / extern
Eventuell: Für einige Beispiele Quellcode - Übungsaufgaben
Eventuell: Veranschaulichung der Verfahren mittels Animation / Tafel...
 -->

==Digitales Sortieren==

Die Schlüssel eines Datensatzes zur Sortierung können mitunter sehr komplex sein (z.B. im Telefonbuch oder einem Bibliothekskatalog). Aus diesem Grund ist es sinnvoll sich die Schlüssel als Zahlen aus einem bestimmten Zahlenbereich vorzustellen.
Methoden bei denen diese Eigenschaft genutzt wird nennt man '''digitale Sortierverfahren''' (radix sorts), diese vergleichen und vertauschen nicht die kompletten Schlüssel sondern sie verarbeiten und vergleichen nur bestimmte Teile von Schlüsseln.
Digitale Sortierverfahren behandeln die Schlüssel von Datensätzen als Zahlen in einem bestimmten Zahlensystem $M$ (für verschiedene $M$) und bearbeiten die einzelnen Ziffern der Zahlen.
<!-- Beispiel Mann mit 3stelligen Zahlen auf Karteikarten -->
Da in Computern alles als Binärcode darstellbar ist, verwendet das digitale Sortieren häufig die Zahlenbasis $2$ oder eine Potenz von $2$, denn wenn dem Nutzer die Schlüsseldaten binär vorliegen so ist die Anwendung vieler digitale Sortierverfahren möglich.
<!-- viele PS machen es schwer mit binärdargestellten Zahlen zu arbeiten, arithmetrische Operationen können jedoch Grundoperationen simulieren (uneffizient) -> solche Programme sind leicht in Programmiersprachen mit Bitoperationen übersetzbar -->

=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.
<!--
In den No-Free-Lunch-Theoremen wurde gezeigt, dass – gemittelt über alle mathematisch formulierbaren Probleme – alle Suchverfahren gleich gut sind. Einen Leistungsvorsprung zeigt ein Suchverfahren jeweils nur auf einer speziellen Klasse von Problemen.
heuristiken!
-->
==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.

<code id="529635662528e">static int lineareSuche(int[] suchraum, int key){
		for(int i=0;i<suchraum.length;i++){
			if(suchraum[i]==key){
				return i;
			}
		}
		return -1;//Fehlercode
	}</code>

<run id="52963566253df">
int[] suchraum = { 6, 2, 9, 7, 8, 1, 3, 5, 4 };
lineareSuche(suchraum, 4);
</run>

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)$. Geht man davon aus, dass jeder Datensatz gleichwahrscheinlich gesucht wird, ergibt sich für den Average-Case ebenfalls die Formel $\frac{1}{n}\cdot \sum_{i=1}^{n} i = \frac{n+1}{2}$. Das entspricht $\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.

 '''Übung: Wie viele Teilungen müssen durchgeführt werden?'''
 '''Suchraum = {1,2,3,4,5,6,7,8,9,10}, Suchschlüssel = 4'''

<code id="5296356625327" hidden>static int binäresSuchen(int[] Feld, int key) {
		int von = 0;
		int bis = Feld.length - 1;
		int mitte;
		int counter = 0;
		while (true) {

			mitte = (von + bis) / 2;
			if (key < Feld[mitte]) {
				bis = mitte - 1;
				counter++;
			} else if (key > Feld[mitte]) {
				von = mitte + 1;
				counter++;
			} else {
				System.out.println("Anzahl Teilungen: " + counter);
				return mitte;
			}

			if (von > bis) {
				return -1;
			}

		}
	}</code>
<run id="529635662547b">
int[] suchraum = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
System.out.println("Position: "+binäresSuchen(suchraum, 4))</run>

Beim Worstcase muss solange geteilt werden, bis nur noch ein Element im Suchraum vorhanden ist. Wichtigster Teil der Binären Suche ist das Halbieren des Suchraumes,
was auch rekursiv definiert werden kann. Mit Hilfe der rekurrenten Beziehung $C_N=C_{N/2}+1$ mit $C_1=0$ ist ungefähr $\lg N$ ergibt sich für das Binäre Suchen eine
Laufzeit in $\mathcal O(\lg n)$. Da für das Löschen oder Einfügen eines Elementes jedoch das Feld neu sortiert werden muss, d.h. die Zahl der Vertauschungen linear ist (Laufzeit in $\mathcal O(n)$), ist auch die Binäre Suche noch nicht optimal.

==Fibonacci Suche==
Dieses Verfahren stellt eine Variation der Binären Suche da und arbeitet nach einer ähnlichen Vorgehensweise. Da die Laufzeit aber nicht besser ist wird es nur in Grundzügen dargestellt. Der Suchraum wird dabei nicht symetrisch geteilt, sondern asymetrisch. Da die Teilbereiche den Suchraum überdecken müssen, muss zumindest der zweite Teil des Suchbereiches berechnet werden. Dies geschieht durch Subtraktion, es ist keine Division mehr notwendig. Die Bildung der Teilbereiche geschieht dabei ebenso wie bei der Binären Suche solange, bis das Element bei der Teilung gefunden wurde beziehungsweise nur noch ein Element in einem Teilbereich vorhanden ist. Durch die Berechnung der Fibonacci-Zahlen wird der Algorithmus nicht nur komplizierter
(Stichwort kognitive Effizienz), sondern die Berechnung fließt auch in die Laufzeit mit ein. Der Bestcase ist wie beim Binären Suchen in $\mathcal O(1)$, der Average-Case ergibt sich aus der Berechnung der Fibonacci-Zahlen $\mathcal O(\log_{1.618}(n+1))=O(\log_2 n)$.
<!--
nicht besser als binäre suche->beweis!
deshalb nur kurze vorstellung 
-->

==Binäre Suchbäume==
Die genutzte Datenstruktur wird nun vom Feld in einen Baum geändert. In den Knoten des Baumes werden die Datensätze beziehungsweise die Suchschlüssel abgespeichert. Damit ein Binärbaum ein binärer Suchbaum ist, muss jeder seiner Knoten die Suchbaum-Eigenschaft erfüllen. Diese besagt, dass der Suchschlüssel eines jeden Knotens im linken Teilbaum des betrachteten Knotens kleiner sein muss als der Suchschlüssel des betrachteten Knotens. Ebenso ist der Suchschlüssel des betrachteten Knotens kleiner als alle Suchschlüssel der Knoten im rechten Teilbaum.
Die folgenden Abbildungen veranschaulichen die Suchbaum-Eigenschaft.<br />
[[Bild:S3rostri_Baum.png]]  [[Bild:S3rostri_Baum2.png]]
<br />
Ebenfalls wird deutlich, dass eine Reihe von Werten durch mehrere binäre Suchbäume dargestellt werden können, der Unterschied liegt in der Höhe $h$ der Bäume.
Ein binärer Suchbaum kann als verkettete Liste implementiert werden, wobei jeder Knoten Verweise auf andere Knoten als Attribute erhält. Nötig sind die Verweise auf die zwei direkten Kinder sowie den Vaterknoten oder Parentnode. Gibt es keinen Kind- oder Vaterknoten, erhält das zugehörige Attribut den Wert ''NIL''. Die Wurzel eines Binärbaumes ist also der Knoten, bei dem das Attribut Vaterknoten den Wert ''NIL'' besitzt. Die Laufzeit aller Operationen auf dem Baum ist immer abhängig von seiner Höhe. Für die Suche eines Elements benötigt man maximal $\mathcal O(h)$ Schritte. Besonders gut deutlich wird dies bei der Suche nach dem Maximum oder dem Minimum: Es wird immer am linken Teilbaum entlanggegangen, die Höhe $h$ legt die Schritte fest.
Auch Operationen wie das Einfügen oder das Löschen von Datensätzen findet in Abhängigkeit der Baumhöhe statt. 

 '''Übung:'''
 '''Fügen Sie in dem linken der obigen Bäume einen Knoten mit dem Schlüssel 7 ein. Wie viele Schritte sind notwendig?'''

Interessant zu wissen wäre natürlich die Abhängigkeit der Laufzeit von $n$.
Dies ist aber schwierig zu sagen, da, wie bereits erwähnt, verschiedene Bäume für die gleiche Eingabe möglich sind. So kann im Worstcase (Baum erstellt nach sortierter Eingabe beginnend beim kleinsten Element) die Laufzeit durchaus in $\mathcal O(n)$ liegen (degenerierter Baum). Ziel muss es also sein, möglichst ausbalancierte Bäume zu bekommen. Diese werden in den folgenden Abschnitten vorgestellt.

==AVL-Bäume==
höhenbalancierte
==Rot-Schwarz-Bäume==
Um den Worstcase der Binärbäume zu verhinden, entwickelte R. Bayer 1972 die Rot-Schwarz-Bäume. Jeder Knoten besitzt dabei ein zusätzliches Attribut (Bit), durch das seine Farbe beschrieben wird. Diese kann Rot oder Schwarz sein. Die näherungsweise Ausbalancierung wird nun dadurch erreicht, dass ein Pfad von der Wurzel bis zu einem Blatt nur eine festgelegte Färbung besitzen darf. Damit ein Binärbaum ein Rot-Schwarz-Baum ist, muss er folgende Eigenschaften erfüllen.
# Jeder Knoten ist entweder rot oder schwarz
# Die Wurzel und jedes Blatt sind schwarz
# Ist ein Knoten rot, sind seine beiden Kinder schwarz
# Für jeden Knoten $k$ gilt: Alle Pfade, die an $k$ starten und in einem Blatt des Teilbaums von $k$ enden, besitzen die gleiche Anzahl schwarzer Knoten
<br />
[[Bild:Baumsr.png]]
<br />
Entlang des Pfades von einem Knoten $x$ zu einem Blatt bezeichnet man die Anzahl der schwarzen Knoten als die '''Schwarzhöhe''' $bh(x)$. $x$ wird dabei nicht mitgezählt. Die Schwarzhöhe eines ganzen Baumes bezeichnet man als Schwarzhöhe seiner Wurzel. Desweiteren werden Blätter in den Betrachtungen weggelassen, da nur die inneren Knoten die Suchschlüssel enthalten.

 Lemma:
 Die maximale Höhe für einen Rot-Schwarz-Baum mit $n$ Knoten beträgt $2\cdot \lg(n+1)$

<popup name="Beweis">
Beweis Teil 1:<br />
Es gilt für einen beliebigen Knoten $x$: Jeder Teilbaum von $x$ hat mindestens $2^{bh(x)}-1$ innere Knoten.<br />
Beweis durch Induktion:<br />
'''Induktionsanfang:'''<br />
Wenn $bh(x)=0$, dann ist $x$ ein Blatt. Der Teilbaum hat $2^0-1=0$ innere Knoten.<br />
'''Induktionsschritt:''' <br />
$x$ sei ein innerer Knoten mit positiver Höhe und 2 Kindern.<br />
Für die Kinder gilt: $bh(Kind)=bh(x)$, wenn die Farbe des Kindes Rot ist, $bh(Kind)=bh(x)-1$, sonst.<br />
Außerdem gilt: $h(Kind) < h(x)$. Daraus folgt für die Anzahl der Knoten der Kinder direkt: 
\begin{equation}
2^{bh(x)-1}-1
\end{equation}
Daraus ergibt sich für den Teilbaum von $x$ eine minimale Knotenzahl von
\begin{equation}
(2^{bh(x)-1}-1) + (2^{bh(x)-1}-1) +1
\end{equation}
Durch die Umformung 
\begin{equation}
 (2^{bh(x)-1}-1) + (2^{bh(x)-1}-1) +1
\end{equation}
\begin{equation}
= 2\cdot (2^{bh(x)-1}-1) + 1
\end{equation}
\begin{equation}
= (2^{bh(x)}-2) +1
\end{equation} 
\begin{equation}
= 2^{bh(x)}-1
\end{equation}
ist der Beweis für die minimale innere Knotenzahl erbracht.
</popup>
==Hashing==
<!--
wo angewandt: datenbanken, wichtig!
-->
===Extern===
===Intern===
==String-Matching==
<!--
knuth-morris-prat algo, suchen in texten, boyer moore
-->
==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.
:[mailto://s3damuel@stud.hszg.de Dana Müller]
:[mailto://s3rostri@stud.hszg.de Robert Stricker]