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 <math>A</math> ein Problem mit <math>O\left(n^2\right)</math>, also <math>T_A\leq c \cdot n^2</math>, löst. Für ein Algorithmus <math>B</math>, der drei dieser Probleme der Größe <math>\frac{n}{2}</math> mit <math>A</math> bearbeitet und mit <math>O\left( n \right) </math> 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 $\mathcal{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}
\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]]
===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>
Somit ist die Anzahl der Vergleiche minimal.
</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, dass zu einem sehr langsamen Quicksort führt, was 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}
Dies entspricht der Anzahl der Vergleiche in Bezug auf die Elemente.
</div><br>
====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> Erklärung.
* Die zu sortierende Folge 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>).
* Dann werden die sortierten Hälften zu einer insgesamt sortierten Folge verschmolzen (<font color="green">'''combine'''</font>).
* 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.
* Abarbeiten Daten '''sequentiell. '''
=== 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.
=== Effizienzanalysen ===
* Im Gegensatz zur Effizienzanalyse von Quicksort, gibt es bei Mergesort keine Unterscheidung zwischen Worst-, Best- und Average-Case, da hierbei nicht mit einem Pivot-Element gearbeitet wird, sondern "stupide" 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 ('''n''' = Zahl der Listenelemente): <br>
Sei <font color="green">'''$\mathit{T}\left(n\right)$''' </font> die Laufzeit von Merge-Sort.<br>
Das <font color="green">'''Aufteilen''' </font> braucht ''' $\mathcal{O}\left(n\right)$''' Schritte(bei Implementierung als List mit divide in $\mathcal{O}\left(n\right)$) oder '''$\mathcal{O}\left(0\right)$''' Schritte(bei Implementierung als Array mit divide in $\mathcal{O}\left(1\right)$).<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 <br>
Basisfall : $\mathit{T}\left(1\right)$ = 0 , also :<br><br>
<font color="green">'''Best-Case'''</font>: $\mathit{T}\left(n\right) = \mathcal{O}\left(n \log n\right)$ <br> <font color="green">'''Average-Case'''</font>: $\mathit{T}\left(n\right) = \mathcal{O}\left(n \log n\right)$ <br> <font color="green">'''Worst-Case'''</font>: $\mathit{T}\left(n\right) = \mathcal{O}\left(n \log n\right)$
=== Viualisierung , 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]
=== Pseudocode ===
<code id="568ba6a3cd536">
funtion mergesort( liste ):
if liste.laenge <= 1 then
return liste;
else
linkeListe = liste[0] bis liste[laenge/2];
rechteListe = liste[laenge-(laenge/2)] bis liste[laenge-1];
linkeListe =mergesort(linkeListe);
rechteListe=mergesort(rechteListe);
return merge(linkeListe, rechteListe);
end
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>
=== 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 Such 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)=O(n)$ , da er jedes Element der Liste durchgehen muss. <br><br>
Im <b>Best Case</b> einen Aufwand $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]$, $ 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 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=====
<br>
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)=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)=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>
== 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.
<li> '''Mergesort''' - ein schnelleres (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, daß die beiden Teilfelder bereits sortiert sind.
* Mit einer Zeitkomplexität von Θ(n log(n)) ist das Verfahren immer '''optimal'''.
</ul>
== Ü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 ====
* Auf der Grundlage diese Pseudocode schreiben Sie Java-Code für Hanoi. <br>
* Denken Sie auch an der Klasse '''Main''', welche wird die Methode '''turm''' benutzen. <br>
<code id="5688ea23bbf1b">... </code>
=== Übung 2 ===
* Sortieren Sie eine 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 3 ===
Sortieren Sie die Buchstaben in der Zeichenkette aus Ihrem zusammengeschriebenen Vor- und Nachnamen mit Merge Sort.
=== Übung 4 ===
<popup name="MergeSort-JavaCode">
1. Implementieren Sie eine Klasse '''„MergeSort"'''. <br>
2. Implementieren Sie in der Klasse eine Methode''' main '''.<br>
3. Implementiere Sie eine Variable '''ms''' als MergeSort Elemente.<br>
4. Erzeugen Sie ein Array (als generateRandomNumbers-Methode Element) von der Länge , z.B 7 . <br>
5. Drucken Sie Arrays vor und nach der Sortierung. <br>
</popup>
<popup name ="mergeSort >
* This Methode soll Array sortieren.<br>
* Benutzen Sie input als Array von Integer .<br>
1. Implementieren '''middle'''. <br>
2. Implementiere '''left''' als middle. <br>
3. Implementieren Sie die Schleife , welche überprüft ob inputLength ist durch 2 teilbar.
</popup>
<code id="5694bdd8f0fc4">
int rightLength = 0;
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);
</code>
<popup name = "merge">
1. Implementieren Sie eine Methode '''merge''' ,welche wird zwei integer Arrays mischen , mit dem Parameter '''left''' und '''right '''. <br>
2. Definieren Sie eindimensionales Array '''result ''' und initialisieren als Summe Laenge '''left''' und '''right''' Variablen . <br>
3. Definieren Sie '''leftIndex''', '''rightIndex''' und '''resultIndex''' und initialisieren mit 0.
4. Implementieren Sie die Schleife '''while ''' .
5. Die Methode soll am Ande unseres 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''' ,welche wird den Zufallszahlengenerator, mit dem Parameter '''n'''(length). <br>
2. Definieren Sie eindimensionales Array und initialisieren als das Array mit '''n'''. <br>
3. Benutzen Sie Random . <br>
4. Implementieren Sie die Schleife , welche sucht die Zahlen und speichert diese Zahlen in Array. <br>
5. Die Methode soll am Ande unseres Resultat zurückgeben.<br>
</popup>
<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>