AuK/Sortieren und Suchen WS13-14

Wiki-Quelltext dieser Seite.

=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 $m$, 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 Eingabefelder fortgefahren.
<!-- ===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...
 -->