Kurs:Algorithmen und Datenstrukturen/Kapitel 2

Aus Wikiversity

< Kurs:Algorithmen und Datenstrukturen

Wechseln zu: Navigation, Suche

Dieses Kapitel gehoert zum Kurs Algorithmen und Datenstrukturen des Fachbereichs Informatik.

Inhaltsverzeichnis

1 Sortieren in Arrays
2 Einleitung
3 Definition des Problems
4 Worst-Case und Average-Case Analyse
5 Indirektes Sortieren
6 BubbleSort
7 Selection Sort
8 Insertion Sort
9 MergeSort
10 QuickSort
11 Quellen

[Bearbeiten] Sortieren in Arrays

Kurze Beschreibung dessen, was in diesem Kapitel alles vorkommen wird

[Bearbeiten] Einleitung

Wie kann man sortieren?

Der Begriff "sortieren" kann vereinfacht durch folgende Elementaroperationen dargestellt werden.

Man kann sortieren durch...

Auswählen und Einfügen
Vertauschen
Mischen ("Reißverschlussverfahren")
Streuen und Sammeln
Fachteilen

Sortieren in Anwendungen

Sortierung ist eine wichtige Operation in zahllosen Anwendungen. Es benötigt einen großen Anteil in Programmlaufzeiten bei großen Datenmengen. In folgenden "Anwendungen" kommen verschiedene Sortierverfahren zum Einsatz.

Wörter in Lexikon (geordnet nach der Buchstabenreihenfolge)
Kontoauszug (geordnet nach Datum der Kontobewegung)
Sortierung von Studenten (nach Namen, Notendurchschnitt, Semester, ...)
Sortierung von Adressen / Briefen (nach Postleitzahlen, Ort, Straße ...)

[Bearbeiten] Definition des Problems

Beim Wort "Sortieren" denkt man automatisch an Zahlen. Das Sortieren an sich ist aber nicht auf numerische Werte beschränkt.

Eine Reihe von Objekten $a i$ , $i = 1 \dots n$ nennen wir sortiert wenn für eine binäre, transitive Relation $\circ$ (auch Ordnungsrelation genannt) gilt

$a_i \circ a_j \quad \forall \, i < j$

Anders ausgedrückt: die Relation $\circ$ ist erfüllt für alle Paare $a i$ , $a j$ , wo $i < j$ .

Eine Menge von aufsteigenden Zahlen $a_1, a_2, \dots a_n$ ist somit nach der Relation " $\leq$ " sortiert, denn es gilt

$a_i \leq a_j \quad \forall \, i < j$ .

Diese etwas abstrakte Definition ist für Zahlen ziemlich kompliziert, erlaubt es uns aber, beliebige Objekte nach beliebigen Kriterien zu sortieren.

Wir betrachten zum Beispiel die Menge von Namen:

Andrea, Beatrice, Caroline, Daniela, Edith

Die Namen sind oben aufsteigend alphabetisch sortiert. Wir können sie aber auch

Beatrice, Caroline, Daniela, Andrea, Edith

absteigend nach der Laenge sortieren. Oder

Andrea, Daniela, Caroline, Beatrice, Edith

absteigend nach der Anzahl Vorkommen des Buchstaben "a" sortieren.

Um zu überprüfen, ob ein Array sortiert ist, können wir uns auch die Transitivität der Relation, die besagt

$a \circ b \quad \wedge \quad b \circ c \quad \rightarrow \quad a \circ c$

zu nutze machen und verlangen, dass

$a_i \circ a_{i+1}, \quad i=1\dots n-1$ .

Der Rang eines Elementes ( $\mathsf{rank}(a_i)$ ) bezeichnet die Position dieses Elementes im sortierten Array. Ist das Array sortiert, so gilt

$\mathsf{rank}(a_i) = i, \quad i=1\dots n$ .

Wir suchen nun nach Algorithmen, welche eine Folge von Elementen sortieren.

Beliebige Elemente $a_1, a_2, \dots a_n$ sind nach einer gegebenen transitiven, binären Relation $\circ$ sortiert wenn gilt:

$a_i \circ a_{i+1}, \quad i=1\dots n-1$ .

[Bearbeiten] Worst-Case und Average-Case Analyse

Um die verschiedenen Sortieralgorithmen sinnvoll vergleichen zu können, brauchen wir eine Operation -- oder ein Satz von Operationen -- anhand derer wir das asymptotische Verhalten der Algorithmen bestimmen können.

Im Folgenden verwenden wir die Operationen

Vergleiche: zwei Elemente werden auf die Relation, nach der sortiert wird, geprüft.
Vertausche: zwei Elemente werden in ihrer Reihenfolge vertauscht.

Die Laufzeit wird als Funktion der Anzahl der notwendigen obigen Operationen in der Länge $n$ des zu sortierenden Arrays angegeben.

Obwohl ein Vergleich gegenüber einer Vertauschung relativ harmlos aussehen mag -- es werden nur Daten vom Speicher gelesen und nicht geschrieben -- können sie unter Umständen viel stärker ins Gewicht fallen. Sortieren wir zum Beispiel Zeichenketten, so müssen diese Zeichen für Zeichen verglichen werden, bis sie sich in einem Zeichen unterscheiden. Auch ist das Laden der Elemente in den Cache keinesfalls gratis und fällt für große Arrays sehr stark ins Gewicht.

Ob die Anzahl Vergleiche oder Vertauschungen für die Wahl eines Sortieralgorithmus maßgebend ist, entscheidet meist die Menge und die Art der Daten.

Wir unterscheiden dabei zwischen der durchschnittlichen und der maximalen Anzahl Operationen.

Bei der Berechnung der durchschnittlichen Anzahl Operationen gehen wir davon aus, dass die Elemente im unsortierten Array uniform (gleich) verteilt sind. Dies bedeutet, dass in einem Array der Länge $n$ das Element mit dem Rang $j$ mit gleicher Wahrscheinlichkeit an jeder Stelle $i$ stehen kann:

$P\left(\mathsf{rank}(a_i)=j\right) = \frac{1}{n}$

Anders gesagt tritt jede Permutation der $n$ Elemente mit gleicher Wahrscheinlichkeit auf.

Bei der Berechnung der maximalen Anzahl Operationen betrachten wir nur diejenige Permutation oder Permutationen, die das schlechtmögligste Resultat ergeben.

Wir beurteilen die Sortieralgorithmen nach der maximalen oder durchschnittlichen Anzahl Vergleiche und Vertauschungen die notwendig sind, um ein Array mit $n$ Elementen zu sortieren.

Für die durchschnittliche Anzahl Operationen gehen wir von einem unsortierten Array aus, bei dem die Elemente uniform verteilt sind.

[Bearbeiten] Indirektes Sortieren

Die benötigte Zeit für das Vertauschen von Daten kann unter Umständen drastisch reduziert werden, in dem nicht die Daten selbst sondern zwei Indexwerte in einen Array vertauscht werden.

Nach dem Sortiervorgang sind nicht die Daten selbst, sondern nur das Array sortiert. Möchte man nun die Daten in eine sortierte Reihenfolge bringen müssen diese anhand des Arrays umgestellt werden. Dies erfolgt aber in linearer Zeit ( $\mathcal O(n)$ ).

Indirektes Sortieren ist also immer dann angezeigt, wenn einerseits die Kosten für das Vertauschen von Daten hoch ist und andererseits die zusätzlichen Speicher Resourcen (i.d.Regel 4 Bytes pro Element) ertragbar sind.

[Bearbeiten] BubbleSort

Ausgehend von der Definition eines sortierten Arrays

$a_i \leq a_{i+1}, \quad i = 1 \dots n-1$

(wir verwenden hier das " $\leq$ " für eine allgemeine Ordnungsrelation), können wir einen ersten, naiven Algorithmus zum Sortieren eines Arrays konstruieren:

Wir durchlaufen das Array und vergleichen dabei jedes Element $a i$ mit dem darauffolgenden Element $a i + 1$ . Sind die zwei Elemente nicht sortiert, so werden sie vertauscht. Wir wiederholen diesen Vorgang bis das Array sortiert ist.

BubbleSort ist in für die Anzahl von Vergleichen und Vertauschungen sowohl im worst-case als auch im average-case in der Größenordnung $\mathcal O(n^2)$ .

Das Kapitel zu BubbleSort wurde hierher ausgelagert!

[Bearbeiten] Selection Sort

SelectionSort sucht das kleinste Element in einem Array und vertauscht es mit der ersten Stelle. Danach wird das zweitkleinste Element gesucht und mit der zweiten Stelle vertauscht usw...

Die dazu notwendige Anzahl Vergleiche und Vertauschungen sind, sowohl im Worst-Case als auch im Average-Case in der Größenordnung $\mathcal O(n^2)$ bzw. $\mathcal O(n)$ .

Das Kapitel zu SelectionSort wurde hierher ausgelagert!

[Bearbeiten] Insertion Sort

Ein Array mit $n$ Elementen wird sortiert, indem für jedes $i$ -te Element dessen richtige Position im Teilarray von $1 \dots (i-1)$ gesucht wird und das Element durch paarweise Vertauschungen dorthin verschoben wird. Im Schnitt werden dafür $\mathcal O(n^2)$ Vergleiche und $\mathcal O(n^2)$ Vertauschungen benötigt.

Die Varianten Binary InsertionSort und ShellSort kommen mit $\mathcal O(n\log n)$ Vergleichen bzw. $\mathcal O(n^{3/2})$ Vertauschungen aus.

Das Kapitel zu InsertionSort wurde hierher ausgelagert!

[Bearbeiten] MergeSort

MergeSort funktioniert nach dem divide and conquer-Prinzip. Die Liste wird in zwei Hälften aufgeteilt, welche rekursiv sortiert werden. Die zwei sortierte Hälften werden dann in einer neuen Liste zusammengesetzt, womit MergeSort kein in-place Algorithmus ist. Die Anzahl dazu nötigen Vergleiche und Kopiervorgänge liegt in $\mathcal O(n\log_2n)$ .

Das Kapitel zu MergeSort wurde hierher ausgelagert!

[Bearbeiten] QuickSort

Man sucht sich ein sogenanntes Pivotelement heraus. Dieses teilt die bestehende unsortierte Liste in zwei Bereiche ein. Das Pivotelement sollte, je nach Verteilung der Elemente in der Liste, in der Mitte gesetzt werden.

Der linke Bereich enthält alle Elemente die kleiner sind als das Pivotelement.
Der rechte Bereich enthält alle Element die größer sind als das Pivotelement.

(Die Länge der aufgeführten Teillisten ergeben sich aus der Art (Position) des Pivotelements)

Die Listen sind nun zueinander sortiert. Man muss nun jede Teiliste wieder auf die gleiche Art sortieren, bis man nur noch Teilisten der Länge eins oder null hat.

Herleitung des Algorithmus
Maximierung der Information
Worst-Case Analyse
Average-Case Analyse

[Bearbeiten] Quellen

Algorithmen und Datenstrukturen 1 - 4. Vorlesung - Peter F. Stadler Universität Leipzig (Ifi)
Übersicht verschiedener Sortieralgorithmen