Teile und Herrsche
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
== <font color="green"> '''Teile und Herrsche (Divide and Conquer)''' </font> ==
=== Definition ===
<div style= "background-color:#D6D6C2; padding:10px">
*Das Entwurfsverfahren <font color="green"> '''Teile und Herrsche'''</font> dient dem Entwurf rekursiver Algorithmen.
*Die Idee ist es, ein Problem der Größen in mehrere gleichartige, aber kleinere Teilprobleme zu zerlegen (<font color="green"> '''divide'''</font>).
*Aus rekursiv gewonnenen Lösungen der Teilprobleme (<font color="green"> '''conquer'''</font>) gilt es dann, eine Gesamtlösung für das ursprüngliche Problem zusammenzusetzen .
* Ziel dieser Methode ist es eine Effizienzverbesserung zu erreichen.
</div>
<br>
[[Bild:S3anbrem_Anw.PNG]]
=== Entwurfsmethode für Algorithmen ===
1. <font color="green"> '''Teile''' </font> das Problem in kleinere Unterprobleme (Divide) <br>
2. <font color="green"> '''Löse''' </font> rekursiv die entstehenden Unterprobleme (Conquer) <br>
3. <font color="green"> '''Setze''' </font> die Lösungen zusammen.<br>
=== Eigenschaften ===
<ul>
<li>
kann bei konzeptionell schwierigen Problemen hilfreich sein
<li>
kann effiziente Lösungen realisieren
<li>
für Parallelverarbeitung geeignet
</ul>
=== Effizienzbetrachtung ===
Die folgende Rechnung dient als Beweis, dass eine Effizienzverbesserung auftritt:<br />
Wir nehmen an, dass ein bestimmter Algorithmus $\mathit{A}$ ein Problem mit $\mathcal{O}\left(n^{2}\right)$, also $\mathit{T}_{\mathcal{A}} \leq c \cdot n^{2} $ , löst. Für ein Algorithmus $\mathit{B}$, der drei dieser Probleme der Größe $\left( \frac{n}{2}\right)$ mit $\mathit{A}$ bearbeitet und mit $\mathcal{O}\left(n\right)$ zusammenfügt gilt:<br /><br />
\begin{align}
\begin{array}{rcl}
T_{B} \left( n \right) & = & 3 \cdot T_{A} \cdot\left( \left\lceil \frac{n}{2} \right\rceil \right) + d \cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n+1}{2}\right) ^{2} + d \cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n+1}{2}\right) \left( \frac{n+1}{2}\right) + d \cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n^{2} + 2n + 1}{4}\right) + d \cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n^{2}}{4} + \frac{2n}{4} + \frac{1}{4}\right) + d \cdot n\\\\
& \leq & \frac{3cn^{2}}{4} + \frac{6cn}{4} + \frac{3c}{4} + d \cdot n\\\\
& \leq & \frac{3}{4}cn^{2} + \frac{3}{2}cn + \frac{3}{4}c + d \cdot n\\\\
& \leq & \frac{3}{4}cn^{2} + \left(\frac{3}{2}c + d\right) \cdot n + \frac{3}{4} c\\\\
\end{array}
\end{align}
Man erkennt an den führenden Summanden, dass sich tatsächlich eine Effizienzsteigerung von ca. 25% ergibt. Allerdings liegt noch immer ein quadratischer Aufwand mit $\mathcal{O}\left(n^{2}\right)$ vor. Daher betrachten wir nun einen Algorithmus $\mathit{C}$ , welcher das Problem auf rekursive Art löst.
\begin{align}
\mathit{T}_{\mathcal{C}}\left(n\right) = \begin{cases} \mathit{T}_{\mathcal{A}}\left(n\right), \mbox{$wenn$}\ n\leq n_{0} \\
\mathit{3\ T}_{\mathcal{C}}\left(\dfrac{n}{2}\right), \mbox{$sonst$}\end{cases}
\\\\\
\mathit{T}_{\mathcal{C}}\left(n\right) = \mathit{3\ T}_{\mathcal{C}}\left(\dfrac{n}{2}\right) = \mathcal{O}\left(n^{log_{2}{3}}\right) = \mathcal{O}\left(n^{1.59}\right)
\end{align}
Nach dem Lösen dieser Formel kommen wir zu dem Ergebnis $\mathit{T}_{\mathcal{C}}\left(n\right)=\mathcal{O}\left(n^{1.59}\right)$.
=== Beispiel: Die Türme von Hanoi ===
<popup name="Die Spielregeln">
Es sind '''n''' Scheiben unterschiedlichen Durchmessers gegeben, welche geordnet zu einem Turm geschichtet sind, wobei die untere Scheibe ist die Größte. Der Turm steht auf einem '''Anfangsplatz'''. Unter Verwendung eines '''Hilfsplatzes''' soll dieser Turm nun zu einem '''Zielplatz ''' transportiert werden. Dabei darf pro Zug nur eine Scheibe bewegt werden und keine größere Scheibe auf eine Kleinere gelegt werden.
</popup>
Wenn die Anzahl der Scheiben '''1''' beträgt, ist die Lösung des Problems '''trivial'''. <br>
Bei mehr als einer Scheibe lässt sich das Gesamtproblem in drei Teilprobleme zerlegen:
* Transportiere <font color="green"> '''n-1'''</font> Scheiben vom <font color="green"> '''Anfangsplatz'''</font> auf den <font color="green"> '''Hilfsplatz'''</font>.
* Transportiere die letzte Scheibe vom <font color="green"> '''Anfangsplatz'''</font> auf den <font color="green"> '''Zielplatz'''</font>.
* Transportiere <font color="green"> '''n-1'''</font> Scheiben vom <font color="green"> '''Hilfsplatz'''</font> auf den <font color="green"> '''Zielplatz'''</font>.
[[Bild:S3anbrem_Azh.PNG]]
=== Übung: Die Türme von Hanoi ===
* Transportiere n Scheiben vom Anfangsplatz auf den Zielplatz, unter Verwendung eines Hilfsplatzes.
<br>
[[Bild:S3anbrem_U1.png]]
<popup name="Lösung">
[[Bild:S3anbrem_B4.PNG]]
</popup>
<b>Spiel</b>
http://www.gf-webdesign.de/tuerme-von-hanoi/tuerme-von-hanoi.htm
== Quicksort ==
===Das Verfahren===
<div style= "background-color:#D6D6C2; padding:10px">
Quicksort ist ein schneller Sortieralgorithmus auf der Basis rekursiver Vergleiche von Elementen, welcher von C.A.O Hoare im Jahre 1960 entwickelt wurde.<br><br>
Das Prinzip ist eine gegebene Gesamtliste $G$ so in zwei Teillisten $L$ und $R$ aufzuteilen <b>(divide)</b>, dass alle Elemente von $L$ kleiner (oder gleich) als ein Vergleichselement (Pivotelement) $v \in G$<br>
und alle Elemente von $R$ größer (oder gleich) als $v$ sind. <br><br></div><br>
Es existieren zwei Basisfälle:<br>
<b>1. : $G$ ist leer</b><br>
<b>2. : $G$ enthält nur ein einziges Element</b><br><br>
Wird nun der Quicksort-Algorithmus auf jede der enstandenen Teillisten angewandt, ergibt sich dadurch die rekursive Verarbeitung. Es wird dann, nach endlich vielen Zerlegungen, einer der beiden Basisfälle erreicht.<br> Das bedeutet die Teillisten liegen dann sortiert vor <b>(conquer).</b>
Letztlich setzt man die einzelnen Teillisten zu der sortierten Gesamtliste $G$<sub>$sortiert$</sub> zusammmen <b>(combine)</b> und zwar genau in der Form: $G$<sub>$sortiert$</sub> = $L$<sub>$sortiert$</sub> $v$ $R$<sub>$sortiert$</sub>
===Funktionaler Aufbau===
<br>
<code id="568e96584e87f">(define teillisten
(lambda (ls v)
(if (null? ls)
(values '() '())
(call-with-values
(lambda () (teillisten (cdr ls) v))
(lambda (l r)
(let ((x (car ls)))
(if (< x v)
(values (cons x l) r)
(values l (cons x r)))))))))</code>
<run id="5694d2e06e649">(teillisten '(9 2 7 12 4 1 24 77 3 1) 8)</run><br>
<div style= "background-color:#D6D6C2; padding:10px">
Durch diese Prozedur entstehen die zwei Teillisten $L$ und $R$, die für die Unterscheidung der Relation in Bezug auf das Pivotelement benötigt werden.<br><br>
Um nun den Algorithmus richtig anwenden zu können, bedarf es einer weiteren Prozedur, die die Vorhergehende immer wieder rekursiv aufruft und dabei jeweils auf $L$ und $R$
quicksort anwendet um diese zu sortieren.
</div><br>
<code id="568e96584e91f">(define quicksort
(lambda (ls)
(if (or (null? ls) (null? (cdr ls)))
ls
(let ((v (car ls)))
(call-with-values
(lambda () (teillisten (cdr ls) v))
(lambda (l r)
(append
(quicksort l)
(list v)
(quicksort r))))))))</code>
<run id="5694d2e06e78a">(quicksort '(3 8 5 14 19 17 10 13 18 20 16 22 7 6 9 4 15 21 23 11))</run><br>
===Interne Suchverfahren===
Quicksort kann in die Kategorie der internen Suchverfahren eingeordnet werden. Das sind Algorithmen die <b>in-place</b> arbeiten, was bedeutet sie benötigen <b>keinen zusätzlichen</b> Speicherplatz, da sie die Eingaben intern verarbeiten und diese dann mit den Ausgaben überschreiben.<br>
Bei der vorherigen Implementierung wurde dies zu Gunsten der Veranschaulichung vernachlässigt. So wurden die Elemente von $G$, die die jeweilige Relation (>= $v$ oder <= $v$) erfüllen, in eine der beiden <b>erzeugten</b> Listen eingetragen. Im Erzeugen von $L$ und $R$ liegt also hier das Problem.<br>
Um die Bedingung des Quicksort-Algorithmus ($l <= v <= r$) erfüllen zu können und den genannten Nachteil zu eliminieren, nutzt man die Idee, die die folgende Implementierung verfolgt.
Zunächst um der Speicherplatzbildung entgegenzuwirken muss die Bildung der Teillisten in $G$ erfolgen.
Um auf jedes Element zugreifen zu können, wird in der folgenden Implementierung ein Vektor $a$ verwendet. <br>
Das Pivot erhält die erste Poition, also $a[0]$. Zusätzlich werden zwei Zeiger $l$ und $r$ initiiert, wobei $l = a[1]$ und $r = a[n-1]$.<br><br>
<code id="569269ad15b7f">(define split
(lambda (a)
(let
((v (vector-ref a 0))
(swap
(lambda (pos1 pos2)
(let ((helper 'nothing))
(set! helper (vector-ref a pos1))
(vector-set! a pos1 (vector-ref a pos2))
(vector-set! a pos2 helper)))))
(letrec
((loop
(lambda (l r)
(cond
((> l r) (swap 0 r) a)
((< (vector-ref a l) v)(loop(+ l 1) r))
((not (< (vector-ref a r) v))(loop l (- r 1)))
(else
(swap l r)
(loop (+ l 1)(- r 1)))))))
(loop 1 (- (vector-length a) 1))))))
(define a (vector 34 65 23 6 32 7 43 765 2 1))</code>
<run id="5694d2e06e86f">(split a)</run>
In Einerschritten wird:<br>
1. $l$ solange nach rechts verschoben bis $a[l] > v$ und
$r$ solange nach links verschoben bis $a[r] < v$
2. wenn jeweils ein Element gefunden wurde, wird $a[l]$ mit $a[r]$ getauscht und die Zeigerbewegung fortgesetzt
3. ansonsten wird $a[r]$ mit $a[0]$ vertauscht und $a$ ausgegeben
4. insofern die Elemente links bzw. rechts vom Pivotelement aus noch unsortiert sind, wiederhole Schritt 1
===Visualisierung===
Die folgende Animation zeigt den verbildlichten Ablauf des Algorithmus:<br><br>
<font style= "color:red">roter </font> Balken = Pivotelement p der jeweiligen Teilliste<br>
<font style= "color:blue">blaue </font> Linie = Wert von p <br><br>
[[Bild:quicksort_animation.gif]]
===Beispiel===
<b>Sortieren von (natürlichen) Zahlen:</b> <br> <br>
In diesem Beispiel soll eine Liste $G$ =<b>[6,13,3,7,9,7,2,1,15,10,5,6]</b> mit Quicksort sortiert werden.<br>
Es folgt eine ausführliche Lösung zum Erhalt der sortierten Liste:
<br><br>
[[Bild:quicksort_beispiel1a.png]]<br>
[[Bild:quicksort_beispiel1_2.png]]<br>
Hinweis: Falls $j$ den Zeiger $i$ erreicht, kann dies schon zum Tausch von a[i] mit $v$ führen. Z.B. wenn a[0]>= $v$
===Effizienz von Quicksort===
Wegen Gründen der Vereinfachung zwecks Erklärung, wurde im Beispiel das letzte Element als Pivotelement gewählt, aber bei der Anwendung des Algorithmus sollte man auf die Wahl achten.<br>
Wie effizient der Quicksort-Algorithmus ist, hängt nämlich in erster Linie von der Wahl des Pivotelementes ab.<br>
====Best-Case====
Im besten Fall wird das Pivotelement so gewählt, dass dieses in der sortierten Liste genau in der Mitte liegt und somit die Gesamtliste $G$ aus (etwa) zwei gleich großen Listen besteht.<br>
<div style= "background-color:#D6D6C2; padding:10px">
\begin{align}
\mathit{T}\left(0\right) &= 0\notag\\
\mathit{T}\left(n\right) &= 2 \cdot \mathit{T}\left(\frac{n}{2}\right) + c \cdot n\notag
\end{align}
Nach Auflösung mit der Meistermethode ergibt das einen Aufwand $T(n) = \mathcal{O}(n \ \log_{2} \ n)$ .<br>
</div><br>
====Average-Case====
Im Durchnitt nimmt man an, dass die Wahrscheinlichkeit aller $n$ Teillistenlängen gleich ist. Somit ist die Wahl des Pivotelementes für jedes Element der Liste $G$ gleich wahrscheinlich.
<br>
<div style= "background-color:#D6D6C2; padding:10px">
\begin{align}
\begin{array}{rcl}
T(i) = T\left(n-i-1\right) = \frac {1}{n} \cdot \sum\limits_{j=0}^{n-1} T\left( j\right)\\\\
T(n) = \underbrace{T\left(i\right)}_{linke\ Teilliste} + \underbrace{T\left(n-i-1\right)}_{rechte\ Teilliste} + \underbrace{c \cdot n}_{Teillistenbildung}\\\\
\end{array}
\end{align}
Nach Einsetzen ergibt sich folgendes:
\begin{align}
\begin{array}{rcl}
T\left(n\right) &=& \frac {2}{n} \sum\limits_{j=0}^{n-1} \ T\ \left(j\right) + c \cdot n\\\\
\end{array}
\end{align}
Um die Summe zu beseitigen, werden folgende Differenzen gebildet:
\begin{align}
\begin{array}{rcl}
nT\left(n\right) &=& 2 \ \sum\limits_{j=0}^{n-1} \ T\ \left(j\right) + c \cdot n^{2} \\\\
\left(n-1\right)T\left(n-1\right) &=& 2 \sum\limits_{j=0}^{n-2}\ T\ \left(j\right) + c \cdot \left(n-1\right)^2 \mid \text{für} \ n:=n - 1; -\\\\
\\\\
nT\left(n\right) - \left(n-1\right)T\ \left(n-1\right) &=& 2T\ \left(n-1\right) + 2cn - c \mid -c\ \text{entfällt für}\ n \rightarrow \infty\\\\
\frac{T\left(n\right)}{n+1} &=& \frac{T\left(n-1\right)}{n} + \frac{2c}{n+1}\\\\
\frac {T\left(n-1\right)}{n} &=& \frac{T\left(n-2\right)}{n-1} + \frac{2c}{n}\\\\
\vdots & & \vdots\\\\
\frac{T\left(2\right)}{3} &=& \frac{T\left(1\right)}{2} + \frac{2c}{3}\\\\
\\\\
\frac{T\left(n\right)}{n+1} &=& \underbrace{\frac{T\left(1\right)}{2}}_{=0, da\ T\left(1\right) =0} + 2 \sum\limits_{i=3}^{n+1} \frac{1}{i}\\\\
\end{array}
\end{align}
Bei der Benutzung der bekannten Schranken $\frac {\lfloor log_{2} \ n \rfloor +1}{2} < \mathit{H}_{n} \leq \lfloor log_{2} \ n \rfloor +1$ für die harmonischen Zahlen $\mathit{H}_{n} = \sum\limits_{k=1}^{n} \frac{1}{k}$ ergibt sich:
\begin{align}
\frac {T\left(n\right)}{n+1} = \mathcal{O} \left(log_{2} \ n\right)\curvearrowright T\left(n\right) = \mathcal {O} \left(n \cdot log_{2} \ n\right)
\end{align}
</div><br>
====Worst-Case====
Im schlechtesten Fall wird das Pivotelement so gewählt, dass dieses in der sortierten Liste entweder am Anfang oder am Ende liegt und somit auf der einen Seite das Pivotelement $v$ und auf der anderen Seite der Rest von $G$ liegt.<br>
Dies ist z.B. der Fall, wenn $G$ vor der Anwendung von Quicksort bereits sortiert ist, das zu einem sehr langsamen Quicksort führt, was wiederrum zum einen aus Definitionssicht wiedersprüchlich erscheint und zum anderen aus Anwendersicht für Konfusion sorgt.<br>
<div style= "background-color:#D6D6C2; padding:10px">
\begin{align}
\mathit{T}\left(0\right) &= 0\notag\\
\mathit{T}\left(0\right) &= \underbrace{\mathit{T}\left(0\right)}_\text{= 0} + \mathit{T}\left(n - 1\right) + c \cdot n\notag
\end{align}
Das kann mit der Iterationsmethode gelöst werden:
\begin{align}
\mathit{T}\left(n - 1\right) &= \mathit{T}\left(n - 2\right) + c \left(n - 1\right)\notag\\
\mathit{T}\left(n - 2\right) &= \mathit{T}\left(n - 3\right) + c \left(n - 2\right)\notag\\\\
\vdots \\\\
\mathit{T}\underbrace{\left(\ n - k \ \right)}_{\text{ = 1 $\curvearrowright$ k = n - 1}} &= \mathit{T}\left(0\right) + c \left(n - k\right)\notag\\
\end{align}
Nach Einsetzten jedes Ausdrucks in die darüberliegende Zeile ergibt das:
\begin{align}
\begin{array}{rcl}
T(n) &=& c \cdot \sum\limits_{k=0}^{n-1} \left(n-k\right)\\\\
&=& c\cdot\left(\sum\limits_{k=0}^{n-1} n - \sum\limits_{k=0}^{n-1} k\right)\\\\
&=& c\cdot\left(n^2 - \frac {n-1}{2}\left(\left(n-1\right)+1\right)\right)\\\\
&=& c\cdot\left(n^2 - \frac {n^2 -n}{2}\right)\\\\
&=& c\cdot\left(\frac {n^2} {2} + \frac {n} {2}\right)
\\\\\\
T(n) &=& \mathcal{O}\left(n^2\right)\\\\
\end{array}\notag
\end{align}
</div><br><br>
Die Effizienz von Quicksort ist abhängig von der Anzahl der Elemente, da je länger die zu sortierende Liste wird, auch die Distanz steigt, aus der die Elemente miteinander vertauscht werden.
Je kürzer also die zu sortierende Liste wird, desto ineffizienter arbeitet Quicksort, da es sich der Komplexität $\mathcal{O}(n^2)$ annähert.
====Anpassung====
Die bereits erwähnte Abhängigkeit des Algorithmus von der Wahl des Pivotelementes führt zu den eben berechneten Laufzeiten.<br>
Dabei kann man die Wahl von $v$ durchaus beeinflussen, sodass z.B. die Wahrscheinlichkeit des Auftretens des Worst Cases verringert werden kann.<br>
Außer Acht wird hierbei die Wahl des ersten oder letzten Elementes der Liste gelassen, da dies aus praktischer Sicht unzuverlässig ist.<br><br>
<table style="border=1px solid black">
<tr><th>Möglichkeit 1: </th><td> $v$ als das mittlerste Element der Liste wählen</td></tr>
<tr><th>Möglichkeit 2: </th><td> $v$ als ein zufällig gewähltes Element setzen</td></tr>
<tr><th>Möglichkeit 3: </th><td> das erste, das mittlerste und das letzte Element der Liste nehmen und den Median dieser Drei als $v$ bestimmen.</td></tr>
</table>
Liste $L$ = [10,3,25,6,8,17,1,2,18,5]<br><br>
Median aus den drei: [10,8,5] -> [5,8,10] -><b>8</b>
== <font color="green">'''Mergesort''' </font> ==
=== Definition ===
<div style= "background-color:#D6D6C2; padding:10px">
* <font color="green">'''Das Sortierverfahren Mergesort'''</font> erzeugt eine sortierte Folge durch <font color="green">'''Verschmelzen'''</font> sortierter Teilstücke.
* Das Verfahren beruht auf dem <font color="green">''' Divide-and-Conquer-Prinzip''' </font>.
* Die zu sortierende Folge
:$L = \left(Le_{0}, Le_{1}, Le_{2}, \dots , Le_{n}, Re_{0}, Re_{1}, Re_{2}, \dots , Re_{m}\right)$
wird zunächst in zwei Hälften aufgeteilt (<font color="green">'''divide'''</font>), die jeweils für sich sortiert werden (<font color="green">'''conquer'''</font>).
:$TL = \left(Le_{0}, Le_{1}, Le_{2}, \dots , Le_{n}\right)$ und $TR= \left(Re_{0}, Re_{1}, Re_{2}, \dots , Re_{m}\right)$
* Dann werden die sortierten Hälften zu einer insgesamt sortierten Folge verschmolzen (<font color="green">'''combine'''</font>).
* Die jeweiligen führenden Teilelemente $Le_{i}$ und $Re_{j}$ gelangen an ein "Tor". Wenn $Le_{i} < Re_{j}$ gilt, wird $Le_{i}$ durchgelassen und nimmt die nächste freie Position in der Gesamtliste ein. $Re_{j}$ wird anschließend mit $Le_{i+1}$ verglichen. Ansonsten natürlich umgekehrt.
* Dieses Verfahren bietet die Möglichkeit einer iterativen Implementierung.
</div>
=== Vorteile ===
* Geschickter Einsatz der '''Teile-und-Herrsche''' Technik.
* Gutes '''Laufzeitverhalten''' für große Eingabegrößen <br>
* Die '''Stabilität'''
Die relative Ordnung zweier Elemente , welche gleich sind , wird beibehalten.
* '''sequenzielle''' Abarbeitung der Daten
=== Nachteile ===
* der zusätzlich benötigte '''Speicher'''
=== Anwendung ===
* Der Mergesort wird vor allem dann verwendet, wenn man eine große sortierte Datenmenge verwalten möchte.
=== Effizienzbetrachtung von Mergesort ===
* Im Gegensatz zur Effizienzanalyse von Quicksort, gibt es bei Mergesort keine Unterscheidung zwischen <font color="green">'''Worst-'''</font>, <font color="green">'''Best-'''</font> und <font color="green">'''Average-Case'''</font>, da hierbei nicht mit einem Pivot-Element gearbeitet wird, sondern die Listen immer in der Mitte geteilt werden.Der Algorithmus arbeitet immer gleich, egal ob eine Liste bereits sortiert ist oder nicht. <br>
* Je nach Implementierung erhält man für die Komplexität von Mergesort folgende Rekursionsgleichung: <br>
Sei <font color="green">'''$\mathit{T}\left(n\right)$''' </font> die Laufzeit von Mergesort.<br>
Das <font color="green">'''Aufteilen''' </font> braucht ''' $\mathcal{O}\left(1\right)$''' Schritte.<br>
Die <font color="green">'''rekursiven Aufrufe''' </font> brauchen $ 2\cdot \mathit{T}\left(\frac{n}{2}\right) $ Schritte.(ein Problem halbiert wird und man dadurch zwei halbe Probleme hat.)<br>
Das <font color="green">'''Mischen''' </font> braucht '''$\mathcal{O}\left(n\right)$''' Schritte. <br>
Um Mergesort zu analysieren, ist die Rekursionsgleichung : <font color="red">'''$\mathit{T}\left(n\right) = 2\cdot \mathit{T}\left(\frac{n}{2}\right) + \mathcal{O}\left(n\right)$'''</font>, wenn n > 1 ,
mit $\mathcal{T(0)=0}$ und $\mathcal{T(1)=0}$ zu lösen.
* Wir nehmen vereinfachend an, dass die Anzahl der Elemente $\mathit{n}$ eine Zweierpotenz ist.
\begin{align}
&\mathit{T}\left(n\right) \leq 2 \cdot \mathit{T} \frac{n}{2} + n \\\\
&\leq 2 \cdot ( 2 \cdot \mathit{T} \frac{n}{4} + \frac{n}{2} ) + n = 4 \cdot \mathit{T} (\frac{n}{4}) + 2 n \\\\
&\leq 2^{log( \mathit{n})} \cdot \mathit{T} (\frac{n}{2^{k}}) + k \cdot n\\\\
& \leq 2^{log( \mathit{n})} \cdot \mathit{T} (1) + n \cdot log(\mathit{n}) \\\\
& = 0 + n \cdot log(\mathit{n})\\\\
& = n \cdot log(\mathit{n}) \\\\
\end{align}
Durch Anwendung des zweiten Falles der Meistermethode ergibt sich folgende Lösung: <br>
<font color="green">'''Best-Case'''</font>: $\mathit{T}\left(n\right) = \mathcal{O}\left(n\log_{2} n\right)$ <br> <font color="green">'''Average-Case'''</font>: $\mathit{T}\left(n\right) = \mathcal{O}\left(n \log_{2} n\right)$ <br> <font color="green">'''Worst-Case'''</font>: $\mathit{T}\left(n\right) = \mathcal{O}\left(n \log_{2} n\right)$
=== Visualisierung , Simulation, Animation===
[[Bild:S3anbrem_Mergesort-o.gif]]<br>
[http://palash90.in/tools.html#/algorithms/mergeSort]
[http://www.ee.ryerson.ca/~courses/coe428/sorting/mergesort.html]
<language>Scheme</language>
=== Pseudocode ===
* Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus, wobei Liste die zu sortierenden Elemente enthält.
<code id="568ba6a3cd536">
funktion mergesort(Liste);
falls (Größe von Liste <= 1) dann antworte Liste
sonst
halbiere die Liste in linke Liste, rechte Liste
antworte merge(mergesort(linke Liste), mergesort(rechte Liste));
ende
funktion merge(linkeListe, rechteListe);
neueListe
solange (linkeListe und rechteListe nicht leer)
| falls (erstes Element der linkeListe <= erstes Element der rechteListe)
| dann füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe
| sonst füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe
solange_ende
solange (linkeListe nicht leer)
| füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe
solange_ende
solange (rechteListe nicht leer)
| füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe
solange_ende
antworte neueListe
</code>
=== Schemeumsetzung Mergesort ===
<code id="56955b8b18083">
#lang racket
(define split
(lambda (Liste)
(letrec ([split-h
(lambda (Liste linkeListe rechteListe)
(cond
[(or (null? Liste) (null? (cdr Liste)))
(cons (reverse rechteListe) linkeListe)]
[else (split-h (cddr Liste)
(cdr linkeListe) (cons (car linkeListe) rechteListe))]))])
(split-h Liste Liste '()))))
(define merge
(lambda (pred linkeListe rechteListe)
(cond
[(null? linkeListe) rechteListe]
[(null? rechteListe) linkeListe]
[(pred (car linkeListe) (car rechteListe))
(cons (car linkeListe) (merge pred (cdr linkeListe) rechteListe))]
[else (cons (car rechteListe) (merge pred linkeListe (cdr rechteListe)))])))
(define merge-sort
(lambda (pred Liste)
(cond
[(null? Liste) Liste]
[(null? (cdr Liste)) Liste]
[else (let ([splits (split Liste)])
(merge pred
(merge-sort pred (car splits))
(merge-sort pred (cdr splits))))])))
</code>
<code>
#lang racket
(define (mergesort Liste)
(if (= 0 (length Liste))
'()
(if (= (length Liste) 1)
Liste
(combine (mergesort (ersteListe Liste (/ (length Liste) 2))) (mergesort (zweiteListe Liste (/ (length Liste) 2)))
)
)
)
)
(define (combine linkeListe rechteListe)
(if (null? linkeListe ) rechteListe
;else
(if (null? rechteListe) linkeListe
;else
(if (<= (car linkeListe ) (car rechteListe))
;car of list 1 is second element of list 2
(cons (car linkeListe ) (combine (cdr linkeListe ) rechteListe))
;else
(cons (car rechteListe) (combine linkeListe (cdr rechteListe)))
)
)
)
)
(define (ersteListe L N)
(if (or (= N 1) (< N 2))
(list (car L))
;else
(cons (car L) (ersteListe (cdr L) (- N 1)))))
(define (zweiteListe L N)
(if (or (= N 1) (< N 2))
(cdr L)
;else
(zweiteListe (cdr L) (- N 1)))
)
</code>
=== Beispiele ===
==== Beispiel 1 ====
Im folgenden soll ein Array mit Mergesort sortiert werden: <br><br>
[[Bild:S3anbrem_Merge-sort-bsp1.PNG]] <br>
<popup name="1. Aufteilen der Eingabe">
[[Bild:S3anbrem_Merge-sort-bsp1b.PNG]] <br> <br>
[[Bild:S3anbrem_Merge-sort-bsp1c.PNG]] <br> <br>
[[Bild:S3anbrem_Merge-sort-bsp1d.PNG]] <br> <br>
</popup>
<popup name="2. Teilen, Sortieren und Mischen der Eingabe">
[[Bild:S3anbrem_Merge-sort-bsp1e.PNG]] <br> <br>
</popup>
<popup name="3. Mischen der Eingabe">
[[Bild:S3anbrem_Merge-sort-bsp1f.PNG]] <br> <br>
</popup>
<popup name="4. Ergebnis">
[[Bild:S3anbrem_Merge-sort-bsp1g.PNG]] <br> <br>
</popup>
==== Beispiel 2 ====
[[Bild:S3anbrem_Anexamplea.png]]
<popup name="1. Aufteilen der Eingabe 2. Rekursiv Sortieren 3. Zusammenfügen">
[[Bild:S3anbrem_Anexample1.png]]
</popup>
== Suchalgorithmen ==
===Sequenzielle Suche===
Die sequenzielle Suche oder auch als lineare Suche ist die Einfachste aller Suchmethoden. Bei dieser Methode wird von Anfang bis Ende jeder einzelne Eintrag nacheinander mit dem gesuchten Element $e$ verglichen. Sobald ein Listenelement mit $e$ übereinstimmt, endet der Algorithmus, sonst wird solange weitergesucht bis das Ende der Liste erreicht ist. <br>
$e=11$
[[Bild:Kerich_LineareSuche.JPG]]<br>
Im <b>Worst Case</b> hat der Algorithmus hierbei ein Aufwand $T(n)=\mathcal{O}(n)$, da er jedes Element der Liste durchgehen muss. <br><br>
Im <b>Best Case</b> beträgt der Aufwand $\mathcal{O}(1)$, da bereits das erste Element mit $e$ übereinstimmen kann.
=== Binäre Suche===
Das Binäre Suchen ist ein Teile-und-Herrsche-Verfahren. Dieses Verfahren ähnelt der linearen Suche, jedoch benötigt das binäre Suchen eine aufsteigend geordnete Liste. <br>
====Ablauf====
<br>
<div style="background-color:#D6D6C2">
1. Teile die Liste $G$ in der Mitte, sodass 2 gleichgroße Teillisten $L=[a_1,a_2,...,a_t]$ und $ R=[a_{t+1},...,a_n]$ entstehen.<br>
Für $t$ gilt $t=\frac{n}{2}$, wobei $t$ ganzzahlig ist. Wenn $t$ nicht ganzzahlig ist, wird der Wert abgerundet. <br>
2. Vergleiche das erste Element der Teilliste $R$ mit $e$.
<table style="margin-left:40px;background-color:#D6D6C2" >
<tr><td> Falls $e = a_{t+1}$, dann wurde das Element gefunden. </td></tr>
<tr><td> Falls $e < a_{t+1}$, dann prüfe ob $L = null$, wenn ja dann wurde das Element $e$ nicht gefunden, sonst gehe zu Schritt 1 und verwende $L$ als neue Liste $G$.</td> </tr>
<tr><td> Falls $e > a_{t+1}$, dann prüfe ob $R = null$, wenn ja dann wurde das Element $e$ nicht gefunden, sonst gehe zu Schritt 1 und verwende den Rest der Liste $R$ als neue Liste $G$.</td></tr>
</table>
</div><br>
Suchen des Elementes $e=11$:<br>
[[Bild:Kerich_BinarySearch.PNG]]<br>
====Effizienz====
=====Best-Case=====
Der Best-Case endet wie beim sequenziellen Suchen mit dem ersten verglichenen Eintrag in der Liste. Somit haben diese beide Algorithmen den gleichen Aufwand im Best-Case von $T(n)=\mathcal{O}(1)$.
=====Average-/Worst-Case=====
Die Listen werden immer in der Hälfte geteilt, somit können immer die Hälfte der Werte ausgeschlossen werden. Geht man dabei vereinfacht von einer Anzahl von $n^2$ Elementen aus, so ist der Aufwand durch die permanente Teilung der Listen $T(n)=\mathcal{O}(log_2 n)$. Dies gilt sowohl für den Worst-, als auch für den Average-Case.
====Implementierung in Scheme====
Die Funktion teillisten spaltet die Liste $G$ in 2 Teillisten. binSuche ist für die binäre Suche zuständig.
<code id="5693ba0a4725f">(define teillisten
(lambda (ls)
(let ((k (floor (/ (length ls) 2))))
(letrec
((helfer
(lambda (ls i)
(if (= i 0)
(values '() ls)
(call-with-values
(lambda () (helfer (cdr ls) (- i 1)))
(lambda (links rechts)
(values (cons (car ls) links) rechts)))))))
(helfer ls k)))))
(define binSuche
(lambda (element G)
(call-with-values
(lambda () (teillisten G))
(lambda (L R)
(cond
((null? R) "Element ist nicht in der Liste enthalten")
((= element (car R)) "Element ist in der Liste enthalten")
((< element (car R))
(binSuche element L))
(else
(if (null? (cdr R))
"Element ist nicht in der Liste enthalten"
(binSuche element R))))))))
</code>
<run id="56953593d64ee">(binSuche 3 '(1 2 3 4 5 6 7))</run>
== Zusammenfassung ==
<ul>
<li>'''Teile und Herrsche''' - Zerlegung größerer Aufgaben oder Probleme in kleinere Aufgaben oder Probleme, die einfacher zu bewältigen oder leichter gelöst werden können. <br><br>
<li>'''Quicksort''' - schneller und rekursiver '''Sortieralgorithmus'''.
* Es wird ein Pivotelement gewählt, sowie zwei Zeiger gesetzt, die sich aufeinander zubewegen. Dabei findet ein Austausch nach Überprüfung der Bedingung statt.
* Obwohl der Algorithmus einen schlechten Worst-Case hat, dessen Wahrscheinlichkeit verringert werden kann, nutzt man ihn aufgrund des relativ guten Durchschnitts häufiger in der Praxis als andere Algorithmen.<br><br>
<li> '''Mergesort''' - ein schnelles (und rekursives) '''Sortierverfahren'''.
* Ein Feld wird in zwei Teilfelder aufgeteilt, die dann rekursiv sortiert werden. Anschließend werden diese sortierten Teilfelder wieder zu einem Feld zusammengefügt. Dabei macht man sich zu Nutze, dass die beiden Teilfelder bereits sortiert sind.
* Mit einer Zeitkomplexität von Θ(n log(n)) ist das Verfahren immer '''optimal'''. <br><br>
<li> '''Binäres Suchen''' - schnelles, rekursives '''Suchverfahren'''
* Es muss eine sortierte Liste vorhanden sein, die immer wieder in der Mitte gespalten wird und mit dem ersten Element der rechten Liste verglichen.
* Im Gegensatz zur sequenziellen Suche, die einen Aufwand von \mathcal{O}(n) hat, besitzt die binäre Suche selbst im Worst-Case einen Aufwand von $\mathcal{O}(log_2 n)$
</ul>
[[Bild:S3anbrem_Sortierung-mqb.png]]
== Übungen ==
=== Übung 1 : Hanoi Java-Code ===
==== Pseudo - Code ====
<code id="5686b20aa7bbc">
procedure turm(ap,zp,hp,n:byte);
begin
if n=1 then
writeln(' Scheibe von Platz ',ap,' auf Platz ',zp)
else begin
turm(ap,hp,zp,n-1);
writeln(' Scheibe von Platz ',ap,' auf Platz ',zp);
turm(hp,zp,ap,n-1);
end;
end;</code>
<popup name = "Bedeutung der Variablen:">
<center>
ap - Anfangsplatz <br>
zp - Zielplatz <br>
hp - Hilfsplatz <br>
n - Anzahl der Scheiben <br>
Die Übergabe des Hilfsplatzes als Parameter kann auch entfallen, wenn man als Berechnung einsetzt: <br>
hp := 6 - ap - zp. <br>
</center>
</popup>
==== Java-Code ====
* Schreiben Sie Java-Code für Hanoi, auf der Grundlage dieses Pseudocodes . <br>
* Denken Sie auch an die Klasse '''Main''', welche die Methode '''turm''' benutzt. <br>
<code id="5688ea23bbf1b">... </code>
=== Übung 2 ===
* Sortieren Sie folgende Listen mit dem Quicksort-Algorithmus:
a) [9,2,7,12,4,1,24,77,3,1,8]<br><br>
b) [2,5,3,7,1,9,8]
=== Übung 3 ===
* Sortieren Sie ein Array indem zwei Teilarrays sortiert und dann gemischt werden. <br>
[[Bild:S3anbrem_B1a1.PNG]]
<popup name="1. Aufteilen der Eingabe">
[[Bild:S3anbrem_B1a.png]]
</popup>
<popup name="2. Rekursiv Sortieren">
[[Bild:S3anbrem_B1b.png]]
</popup>
<popup name="3. Zusammenfügen">
[[Bild:S3anbrem_B1c.png]]
</popup>
=== Übung 4 ===
Sortieren Sie die Buchstaben in der Zeichenkette aus Ihrem zusammengeschriebenen Vor- und Nachnamen mit Mergesort.
=== Übung 5 ===
* Schreiben Sie Java-Code für Merge Sort. <br>
<popup name="MergeSort-JavaCode">
1. Implementieren Sie eine Klasse '''„MergeSort"'''. <br>
2. Implementieren Sie in der Klasse eine Methode''' main '''.<br>
3. Implementieren Sie eine Variable '''ms''' als Mergesort Element.<br>
4. Erzeugen Sie ein Array (als generateRandomNumbers-Methode Element) von z.B. der Länge 7 . <br>
5. Drucken Sie die Arrays vor und nach der Sortierung. <br>
</popup>
<popup name ="mergeSort ">
1.Vervollständigen Sie diese '''mergeSort''' Methode. <br>
* Diese Methode soll ein Array sortieren.<br>
* Benutzen Sie input als Array von Integerwerten .<br>
</popup>
<code id="5694bdd8f0fc4">
...
if (input.length % 2 == 0) {
rightLength = middle;
} else {
rightLength = middle - 1;
}
int[] right = new int[rightLength];
int leftIndex = 0;
int rightIndex = 0;
for (int i = 0; i < input.length; i++) {
if (i < middle) {
left[leftIndex] = input[i];
leftIndex++;
} else {
right[rightIndex] = input[i];
rightIndex++;
}
}
left = mergeSort(left);
right = mergeSort(right);
return merge(left,right);
}
</code>
<popup name = "merge">
1. Implementieren Sie eine Methode '''merge''' ,welche zwei integer Arrays mischt , mit dem Parameter '''left''' und '''right '''. <br>
2. Definieren Sie eindimensionales Array '''result ''' und initialisieren Sie als Summe Laenge '''left''' und '''right''' Variablen. <br>
3. Definieren Sie '''leftIndex''', '''rightIndex''' und '''resultIndex''' und initialisieren Sie diese mit 0. <br>
4. Implementieren Sie die Schleife '''while ''' .<br>
5. Die Methode soll am Ende unser Resultat zurückgeben.<br>
</popup>
<code id="5694bdd8f10ab">
...
while (leftIndex < left.length || rightIndex < right.length) {
if (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result[resultIndex] = left[leftIndex];
leftIndex++;
resultIndex++;
} else {
result[resultIndex] = right[rightIndex];
rightIndex++;
resultIndex++;
}
} else if (leftIndex < left.length) {
for (int i = resultIndex; i < result.length; i++) {
result[i] = left[leftIndex];
leftIndex++;
}
} else if (rightIndex < right.length) {
for (int i = resultIndex; i < result.length; i++) {
result[i] = right[rightIndex];
rightIndex++;
}
}
}
</code>
<popup name = "generateRandomNumbers">
1. Implementieren Sie eine Methode '''generateRandomNumbers''' ,welcher ein Zufallszahlengenerator, mit dem Parameter '''n'''(length) darstellt. <br>
2. Definieren Sie ein eindimensionales Array und initialisieren als das Array mit '''n'''. <br>
3. Benutzen Sie Random . <br>
4. Implementieren Sie die Schleife , welche die Zahlen sucht und diese im Array speichert. <br>
5. Die Methode soll am Ende unser Resultat zurückgeben.<br>
</popup>
=== Übung 6 ===
Wenden Sie die binäre Suche auf das Resultat aus Aufgabe 2a) mit den folgenden Suchelementen an:<br>
a) 7
b) 11
c) 3
=== Übung 7 ===
Das Element $e=T$ soll in folgender Liste gesucht werden:<br>
a) [A,C,E,G,J,L,M,N,P,Q,R,T,U,V,W,Z]
<li> http://www.sorting-algorithms.com/
== Quellen ==
Wagenknecht, 2003, Algorithmen und Komplexität <br>
Cormen, Leierson, Rivest und Stein, 2004, Algorithmen - Eine Einführung <br>
http://www.inf-schule.de/ <br>
http://www.awb1.ch/ <br>
http://www.ki.informatik.uni-frankfurt.de/ <br>
http://ddi.cs.uni-potsdam.de/ <br>
http://thm.de/ <br>
http://de.wikiversity.org/ <br>
http://www.roland-illig.de/ <br>
https://de.wikipedia.org/wiki/Quicksort<br>
http://www.linux-related.de/index.html?/coding/sort/sort_quick.htm<br>
http://en.literateprograms.org <br>
http://www.sorting-algorithms.com/ <br>