AuK/Teile und Herrsche 1 SS10

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
Autoren:
* Raffael Thomas Lang ([mailto:siralang@stud.hs-zigr.de siralang@stud.hs-zigr.de])
* Sebastian Kramer ([mailto:sisekram@stud.hs-zigr.de sisekram@stud.hs-zigr.de])



== Was bedeutet Divide and Conquer (DaC)? ==

'''In vielen Programmiersprachen wird die Gliederung von Computerprogrammen in Prozeduren, Funktionen, Module, Objekte, Komponenten, Prozesse und Threads nach dem Prinzip teile und herrsche umgesetzt.'''

DaC (eng. "Divide and Conquer") auf deutsch "Teile und Herrsche" genannt und in lat. "divide et impera", angeblich ein Ausspruch des französischen Königs Ludwigs XI., soll aber sogar auf Julius Caesar zurückgehen, bezeichnet eine Strategie für Algorithmen. Es beschreibt folgendes Vorgehen bei Problemen:

# Teile das Problem in eine Anzahl von Teilproblemen auf. (''divide'')
# Beherrsche die Teilprobleme durch rekursives Lösen. Wenn die Teilprobleme ausreichend klein sind, dann löse die Teilprobleme sofort. (''conquer'')
# Verbinde die Lösungen der Teilprobleme zur Lösung des Ausgangsproblems. (''konkatenieren'')


=== Ziele von DaC ===

Ziel dieser Methode ist es eine Effiziensverbesserung zu erreichen. Der Lösungsaufwand soll minimiert werden durch die Zerlegung des Hauptproblems in Teilprobleme, welche dem Hauptproblem ähneln.
Sind die Teilprobleme noch zu aufwändig in der Lösung, werden diese weiter in noch kleinere Teilprobleme zerlegt, bis alle mit einem geringem Aufwand lösbar sind. Umso weniger "Zeitverlust" desto besser.

===Vorteile von DaC===

Ein großer Vorteil von der Technik ''Divide and Conquer'', ist die Zerlegung der Probleme.
Dadurch wird es möglich die Probleme in mehreren Instanzen, also sie parallel, zu lösen.
Beispielweise können, je nach Aufwand des Problems, dafür Multicore Prozessoren oder gar mehrere PC's verwendet werden.
Die heutigen MultiCore Prozessoren arbeiten nach dem Schema DaC. Die einzelnen Kerne teilen sich den Speicher und die Aufgaben, dies geschieht mit dieser ''DaC'' Technik.

<center>
[[Bild:MultiCore.jpg]]
</center>

====Grundsätzliche Kommunikationsparadigmen====

MultiCore-Prozessoren greifen kommunikativ über einen gemeinsamen Speicher zu , sogenanten ''shared memory''. Dies geschieht über ein Verbindungsnetz ('''''BUS''''').
Jeder Austausch von Nachrichten erfolgt über ''message passing'', d.h. jeder Prozessor verfügt über einen eigenen Speicher (''LevelCache''), auf den nur er Zugriff hat. Diese Nachrichten erlauben keinen direkten Zugriff auf entfernten Speicher.

Leistungsgewinn ist bei MultiCore-Prozessoren dadurch zu verzeichnen, da eine dynamische Lastverteilung erfolgt. Wenn ein Prozessor am Limit seiner Leistung angekommen ist, übernimmt der nächste Prozessor diese Arbeit.
Diese Divide and Conquer Methode führt zu schnelleren Abläufen, bei Leistungsstarken Rechenaufgaben, Suchverfahren oder sonstigen Aufgaben.
Ein einzelner Kern, würde das Betriebssystem einfrieren und im Hintergrund die Arbeit versuchen allein zu bewälltigen, wenn nicht eine Fehlermeldung auftritt.

====Eigenschaften und Folgen verteilter Systeme====
Nebenläufigkeit
* Viele Prozesse mit unterschiedlicher Ablaufgeschwindigkeit
* Viele Ereignisse passieren gleichzeitig
* Abläufe sind nicht reproduzierbar
* Mechanismen zur Koordination und zur Synchronisation von Aktivitäten

<center>
[[Bild:Multicore.jpg]]
</center>
<br>
Auf der linken Seite ist zu sehen, dass der SingleCore-Prozessor, alle Prozesse allein durchlaufen muss. Hingegen der MultiCore-Prozessor mit "3 Kernen" läuft alle Prozesse mit je einem einzelnen Kern durch.

===Aufwandsbetrachtung von DaC=== 

In der untenstehenden Formel wird erklärt, wie sich der Gesamtaufwand <math>T\left( n \right)</math> eines Algorithmus <math>B</math> aus den Teilproblemen multipliziert mit der Größe von Teilproblemen <math>\ \frac{n}{2} \ </math> plus den Teiler von <math>n</math> im rekursiven Aufruf ergibt. Dies alles wird dann anschließend mit einem Aufwand in <math>\mathcal{O} \left( n \right)</math> verbunden.


<center><math>
\begin{array}{ccl}
T_B \left( n \right) & = & 3T_A\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}{2} + \frac{1}{2} \right)^2+d \cdot n\\\\
		& \leq 	& 3 \cdot c \cdot \left( \frac{n^2}{4}+2\frac{n}{4}+\frac{1}{4} \right)+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)n+\frac{3}{4}c
\end{array}
</math>
</center>


Es tritt eine Effiziensverbesserung von 25% auf, jedoch ist zubeachten das immer ein rekursiver Aufruf enthalten sein muss.
Leider ist zu sehen, dass wir immer noch einen quadratischen Aufwand verzeichnen. Erst wenn der Exponent fällt, kann der Faktor für große <math>n</math> wieder in Betracht gezogen werden.
Jedoch sollten wir diese Lösung der Teilprobleme rekusiv überprüfen mit einem weiteren Algorithmus.<br>
Mit dem Algorithmus <math>C</math>, werden nun die obenen angenommenen Teilprobleme bearbeitet. Der oben genannte Basisfall <math>n \ \leq \ n_0</math>, wird nun von <math>A</math> übernommen. Somit kommen wir zu folgender Aufwandsbezeichnung.


<center><math>
T_C \left( n \right) \ = \ \left\lbrace\left
                            \ T_A \left( n \right) \text{ , wenn} \ n \ \leq \ n_0 <br>
                            3 \cdot T_C \left( \frac{n}{2}\right) \text{ , sonst}
</math>
</center>


Die Anwendung der Meistermethode ergibt folgendes Ergebnis:
<center><math>
T_C(n) \ = \ \mathcal{O}(n^{1,59})
</math>
</center>


Es ergibt sich eine bezeichnende Effizinzverbesserung gegenüber dem quadratischen Aufwand. Die Verwendung dieser beiden Algorithmen bringt uns zu dem Ergebnis, dass ''DaC'' immer aus Effiziensgründen mit Rekursion arbeitet.<br>
Um die Problemlösung rekursiv zu formulieren, muss neben dem Allgemeinen ein Basisfall verwendet werden.
Eine geringere Problemgröße haben die Teilprobleme mit der gleichen Problematik, als das zu lösende Ausgangsproblem. 
Je nach konkreten Problemen, kann es mehrere Basisfälle geben.

==Das schnelle Sortieren==

Das Musterbeispiel für Divide and Conquer, nennt sich Quicksort. Dies dient der Sortierung von Listen. Die zu sortierende Liste wird geteilt, so dass zwei Teillisten entstehen. Das wird solange ausgeführt bis die Teillisten nur noch aus einem oder keinem Element besteht. Sobald der Elementarfall erreicht ist, werden die Einzellisten wieder zusammengeführt.

Quicksort wendet folgende DaC Technik an:

# Zerlege das Problem ganau in zwei Teilprobleme (möglicherweise leer), <math>L</math> ''linkes Problem'' und <math>R</math> ''rechtes Problem''. Alle Elemente in <math>L\ < </math> und <math>R\ > </math>, als das Pivotelement (''Vergleichselement'').
# Sortiere die beiden Teilprobleme <math>L</math> und <math>R</math> durch rekursiven Aufruf von Quicksort.
# Das sortierte Grundproblem <math>G_s_o_r_t_i_e_r_t</math> setzt sich wie folgt zusammen:
#* <math>L_s_o_r_t_i_e_r_t</math>
#* <math>v</math> Pivotelement
#* <math>R_s_o_r_t_i_e_r_t</math>
Exakt in dieser Reihenfolge.

===Grundprinzip===

Quicksort nimmt eine Liste Zahlen und Teilt sie mit Hilfe eines Hilfselements (Pivotelement) auf. Dabei werden 2 Teillisten erzeugt. Diese beiden Teillisten werden wie folgt gefüllt. In die Sogenannte linke Liste kommen alle Zahlen die kleiner als das Pivotelement sind hinein. Jede Zahl die größer oder Gleich dem Vergleichselement sind kommen in die rechte Teilliste. Das Pivotelement, kann auf verschiedene Art und Weise gewonnen werden. Beispielsweise nimmt man sich willkürliche eine Zahl aus der Gesamtliste herraus oder man berechnet das Element in dem alle Elemente der Liste mit einander addiert und durch die gesamte Anzahl der Listenelemente Teilt, also man das Durchschnittselement berechnet. Dies hat je nach wahl des Pivotelements Auswirkungen auf die Effizienz von Quicksort, was aber nur im Worstcase eine Rolle spielt. Die Teilung der Listen wird solange rekursiv durchgeführt, bis nur noch einzel Elemente in den Teillisten übrig sind. Diese einzelnen listen werden dann von links nach rechts wieder zusammengefügt und erählt somit eine sortierte Liste.

<center>
[[Bild:QuickTradi.jpg|miniatur|x550px|Datenfluss]]
</center>

Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus, wobei ''daten'' das zu sortierende Feld ist. Dabei hat beim ersten Aufruf von '''quicksort''' (oberste Rekursionsebene) der Parameter linke Liste (''l'') den Wert ''0'' (Index des ersten Feld-Elements) und rechte Liste(''r'') den Wert ''n-1'' (Index des letzten Feld-Elements). Die Bezeichnungen ''l'' und ''r'' beziehen sich auf die Anordnung des Felds: ''daten[0], daten[1], ... , daten[n-1]''.

 funktion quicksort(l, r)
     l := linke Liste
     r := rechte Liste
     falls l < r dann
         teiler := teile(l, r)
         quicksort(l, teiler-1)
         quicksort(teiler+1, r)
     ende
 ende

 funktion teile(l, r)
     l := linke Liste 
     // Starte mit r links vom Pivotelement
     r := rechte Liste - 1
     pivot := daten[r]
     wiederhole
         // Suche von linke Liste ein Element, welches größer als das Pivotelement ist
         wiederhole solange daten[l] ≤ pivot und l < r
             l := l + 1  
         ende 
         // Suche von rechte Liste ein Element, welches kleiner als das Pivotelement ist
         wiederhole solange daten[r] ≥ pivot und r > l
              r := r - 1 
         ende  
         falls l < r dann 
             tausche daten[l] mit daten[r]
         ende
     solange l < r 
     // solange l an r nicht vorbeigelaufen ist 
     // Tausche Pivotelement (daten[r]) mit neuer endgültiger Position (daten[l])   
     falls daten[l] > pivot dann
             tausche daten[l] mit daten[r] 
     ende     
     // gib die Position des Pivotelements zurück    
     antworte l
 ende

 funktion append(l, v, r)
     l := linke Liste
     r := rechte Liste
     v := Pivotelement
     // nehme linke sortierte Liste und setze diese an erste Stelle
     quicksort(l)
     // gewähltes Pivotelement nehmen und setze dieses hinter die erste Stelle
     quicksort(l) + v
     // nun setze rechte sortierte Liste an letzte Stelle
     + quicksort(r)
     // gib gelöstes Gesamtproblem zurück
     quicksort(l) + v + quicksort(r)
 ende

===Quicksort Bildlich===
<center>[[Bild:QuickSort.png]]</center>
<center>[http://de.wikipedia.org/w/index.php?title=Datei:QuickSort.png&filetimestamp=20070807141119 QuickSort.png]</center>

===Schemeumsetzung Quicksort===

<code id="4bbc7964874ab">(define tl
  (lambda (ls v)
    (if (null? ls)
        (values '() '())
        (call-with-values
         (lambda () (tl (cdr ls) v))
         (lambda (li re)
           (let ((x (car ls)))
             (if (< x v)
                 (values (cons x li) re)
                 (values li (cons x re)))))))))

(define quicksort
  (lambda (ls)
    (if (or (null? ls)(null? (cdr ls)))
        ls
        (let ((v (car ls)))
          (call-with-values
           (lambda () (tl (cdr ls) v))
           (lambda (li re)
              (append
               (quicksort li)
               (list v)
               (quicksort re))))))))
</code>

<eval id="4bbc796487c77">(quicksort '( 2 8 9 13 30 21 7 1 3 6 18 14 20 16 10 12 15 19 25 11 4 5 17 ))</eval>

=== Javaumsetzung Quicksort ===
Hier geht es zur Javaumsetzung:

[[AuK/Teile und Herrsche 1 SS10/JavaQuick|JavaQuick]]

<language>Scheme</language>
===Interne Suchverfahren===

Interne Suchverfahren verbrauchen keinen weiteren Speicher. Es wird nur der Speicher verbraucht der durch die Eingabe benötigt wird. Dies ist bei der Prozedur ''mv-quicksort'' nicht gegeben, da es zu einer Aufteilung in 2 Teillisten kommt, die auch in zwei neuen Listen gespeichert werden, ergo zusätzlicher Speicherplatzverbrauch. Um dies zuverhindern werden die Werte im Schlüsselfeld hinterlegt und als Vektor implementiert.

 >(define a(vector 34 65 23 6 32 7 43 765 2 1))
 >a
 #10(34 65 23 6 32 7 43 765 2 1) // Dieser Vector hat 10 Elemente.

Man muss beachten, das bei vielen Programmiersprachen die Zählung der Vektoren bei <math> 0 </math> beginnt. Es gilt:
<center><math> a[0] = a_1 , \ a[1] = a_2 \ ... \ a[n - 1] = a_n. </math></center>
Das letzte Element hat also den sogenannten Index von <math> n-1 </math>. In unserem Beispiel wäre dies der Index <math> 9 </math>.

Das Pivotelement <math> \vartheta </math> nehmen wir von dem Index <math> a[0] </math>. Zusätzlich setzen wir zwei Zeiger auf folgende Startpositionen: 
#<math> a[1]  -</math> Zeiger <math> l  </math>
#<math> a[n-1] -</math>  Zeiger <math>r </math>.
In Einzelschritten erfolgt nun die Zeigerverschiebung. Der Zeiger <math> l </math> wird nun solange verschoben. bis <math> a[l] \ > \ \vartheta </math> und <math> r </math> wird solang nach links verschoben, bis <math> a[r] \  < \ \vartheta </math>. <math> a[l]</math> und <math>a[r]</math> werden mit einander getauscht, wenn gilt <math> l \leq r </math>. Ist die Suche immer noch nicht beendet, wird die Suche fortgesetzt. Sollte jedoch <math>a[r]</math> mit <math>a[0]</math> getauscht werden wir der die Suche beendet und Vektor <math>a</math> zurückgegeben. Somit steht <math> \vartheta </math> an der richtigen Position und alle Elemente links/rechts von <math> \vartheta </math> sind jetzt dementsprechend kleiner oder größer als <math> \vartheta </math>.


<br>
<code id="4bc1c8c120405">(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>
<eval id="4bc1c8c120fa7">(split a)</eval>

==Mergesort==

Ein treffender Begriff hierfür ist "einfädeln", was man aus dem Straßenverkehr kennt. Zusammenführen ist auch recht treffend. "Sortieren durch Mischen" ist jedoch irreführend, weil hierbei das Prinzip von Mergesort nicht erfasst wird.

===Grundprinzip===
# Divide: <br /> Das Verfahren teilt die Große Liste in zwei etwa gleichgroße Teillisten, was ohne Vergleichselement geschieht. Die Spaltung der Listen wird mit Hilfe von <math> n = |G| \div 2 = m \div 2 </math> realisiert (<math>\div</math> steht für die ganzzahlige Division).
# Conquer: <br /> Dieses Verfahren, sortiert zwei Teillisten rekursiv mit Hilfe von Sortieren durch Mischen. Ausnahme sind kleine Unterprobleme, diese werden direkt gelöst.


Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus, wobei Liste (''ls'') die zu sortierenden Elemente enthält.

 funktion mergesort(ls);
   ls := Liste
   lls := linke Liste
   rls := rechte Liste
   falls (Größe von ls <= 1) dann antworte ls
   sonst
       halbiere die ls in lls, rls
       antworte merge(mergesort(lls), mergesort(rls));
 ende

 funktion merge(lls, rls);
    lls := linke Liste
    rls := rechte Liste
    neueListe
    solange (lls und rls nicht leer)
         falls (erstes Element der lls <= erstes Element der rls)
         dann füge erstes Element lls in die neueListe hinten ein und entferne es aus lls
         sonst füge erstes Element rls in die neueListe hinten ein und entferne es aus rls
    solange_ende
    solange (lls nicht leer) 
         füge erstes Element lls in die neueListe hinten ein und entferne es aus lls
    solange_ende
    solange (rls nicht leer) 
         füge erstes Element rls in die neueListe hinten ein und entferne es aus rls
    solange_ende
    antworte neueListe
 ende

===Mergesort Bildlich===
<center>[[Bild:Merge_sort_animation2.gif]]</center>
<center>[http://de.wikipedia.org/w/index.php?title=Datei:Merge_sort_animation2.gif&filetimestamp=20090412175610 Mergesort.gif]</center>


===Schemeumsetzung Mergesort===

<code id="4bbdf2703fcab">(define (split ls)
  (letrec ([split-h
  (lambda (ls ls1 ls2)
    (cond
      [(or (null? ls) (null? (cdr ls)))
           (cons (reverse ls2) ls1)]
      [else (split-h (cddr ls)
           (cdr ls1) (cons (car ls1) ls2))]))])
    (split-h ls ls '())))

(define (merge pred ls1 ls2)
  (cond
    [(null? ls1) ls2]
    [(null? ls2) ls1]
    [(pred (car ls1) (car ls2))
     (cons (car ls1) (merge pred (cdr ls1) ls2))]
    [else (cons (car ls2) (merge pred ls1 (cdr ls2)))]))

(define (merge-sort pred ls)
  (cond
    [(null? ls) ls]
    [(null? (cdr ls)) ls]
    [else (let ([splits (split ls)])
            (merge pred
              (merge-sort pred (car splits))
              (merge-sort pred (cdr splits))))]))</code>

<eval id="4bbdf2704047a">(merge-sort < '(1 5 2 8 3 9 4 -2))</eval>

<language>Scheme</language>
=== Javaumsetzung Mergesort ===
Hier geht es zur Javaumsetzung:

[[AuK/Teile und Herrsche 1 SS10/JavaMerge|JavaMerge]]


===Funktionsorientierte Beschreibung mit Multiple-value-context===
Die Implementation im Multiple-value-context für Mergesort, erfolgt nach dem Vorbild von Quicksort.<br>
Funktion ''teillisten2'' ist nach der Quicksort ''teillisten'' nachempfunden. Ihre Aufgabe besteht darin, die als Parameter übergebene Liste in der Mitte zu teilen um so 2 gleich große Teillisten zu erhalten. Falls eine ungerade Anzahl an Elementen in der Ausgangsliste existiert, wird die linke Liste (''lls'') um 1 kleiner sein als die rechte Liste (''rls'').<br>
Dies geschieht aufgrund von (''floor()''), es gibt die Ganzzahl zurück.
<code id="4bc1ea06ea335">
(define teillisten2
  (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)))))
</code>

Funktion ''verbinden'' erwartet 2 aufsteigend sortierte Listen als Parameter, welche nun zu einer Gesamtliste verbunden werden.
<code id="4bc1ea06eaaec">
(define verbinden
  (lambda (lls rls)
    (cond
      ((null? lls) rls)
      ((null? rls) lls)
      (else
       (let ((x (car lls)) (y (car rls)))
         (if (<= x y)
             (cons x (verbinden (cdr lls) rls))
             (cons y (verbinden lls (cdr rls)))))))))
</code>

Die Implementation von Mergesort ähnelt der von Quicksort. Multiple-Value-Kontext wird ebenfalls verwendet, welches das abstrakte Arbeiten ermöglicht. Positiv ist auch der eben verwendete Multiple-Value-Kontext muss sich nicht um Beschränkungen, wie z.b. nur ein Rückgabewert je Funktion, kümmern.
<code id="4bc1ea06eb2fe">
(define mergesort
  (lambda (ls)
    (if (or (null? ls) (null? (cdr ls)))
        ls
        (call-with-values
         (lambda () (teillisten2 ls))
         (lambda (ls1 ls2)
           (verbinden
            (mergesort ls1)
            (mergesort ls2)))))))
</code>
<eval id="4bc1ea06eba72">
(mergsort '(9 2 16 7 12 8 15 4 18 10 20 3 17 14 6 13 5 11 1 19))
</eval>

== Vergleich Quicksort und Mergesort ==
===Aufwand Quicksort===
Die Wahl des Pivotelementes bestimmt im wesentlichen die Laufzeit von Quicksort, somit ergeben sich die drei Fälle Best-, Average- und Worst Case.



Sind die beiden Teillisten stets in etwa gleichgroß, Aufgrund einer guten Wahl des Pivotelementes, handelt es sich um den sogenannten Best Case. Daraus folgt: <math>\mathcal{O}( n \cdot \log (n)) </math> für die asymptotische Laufzeit. Für den Average Case gilt ein ähnlicher Aufwand, wie im Best Case. Der Durchschnitsfall lautet: <math> \frac {1}{n} \cdot \sum_{i=0}^{n-1} i= \frac{n-1}{2} </math>.
Im schlechtesten Fall kann es passieren, dass das Pivotelement immer so gewählt wird, das es jeweils das größte oder das kleinste Element der Liste ist. Folglich ist eine der zu sortierenden Teillisten immer schon sortiert. Als Folge daraus verringert sich der Rekursionsschritt immer nur um 1 und es ergibt sich ein Aufwand von <math> \mathcal{O}(n^2) </math>.

===Aufwand Mergesort===

Dieser Algorithmus ist in der Betrachtung des Aufwandes im Best-, Average- und im Worst Case gleich. Es gilt also immer: <math> \Theta( n \cdot \log (n)) </math>.

===Zeitaufwand===

<center>
<math>
\begin{array}{|c|c|c|c|c|c|c|}
\hline
 & \text Rechenzeit in sek. f\ddot ur n\\
\hline
T(n) & n = 10 & n = 100 & n = 1000 & n = 10000 & n = 100000 & n = 1000000\\
\hline
n & 10^{-5} & 10^{-4}  & 10^{-3} & 0,01 & 0,1 & 1\\
\hline
n^2 & 10^{-4} & 0,1 & 1 & 100 & 10000  \approx 2,8 d & 1000000 \approx 277 h 45 min \\
\hline
n \cdot \log_2(n) & \approx 3,2 \cdot 10^{-5} & \approx 6,6 \cdot 10^{-4} &\approx 1,0 \cdot 10^{-2} & \approx 0,13 & \approx 1,7 & \approx 20 \\
\hline
\end{array}
</math>
</center>



Die vollständige Tabelle findet ihr hier:
*[http://www.tinohempel.de/info/info/ti/komplexitaet.htm Zeitkomplexität]
'''''Hinweis - Ihr solltet bei der angegebenen Seite etwas runterscrollen!'''''

===Vergleich===

Es gilt für den Worst Case für Quicksort : <math> \mathcal{O}(n^2) </math>, jedoch spielt das für diesen Algorithmus kaum eine Rolle, da dieser Fall sehr selten eintritt. Er tritt meist nur auf, wenn man eine bereits sortierte Liste mittels Quicksort ordnen möchte. Betrachten wir Mergesort, stellen wir fest, das immer <math> \Theta( n \cdot \log (n)) </math> gilt. Mergesort scheint somit besser zu sein, wie Quicksort, aber da bei Quicksort der Worst Case selten eintritt, erweist sich Quicksort als effizienter.

== Übungen ==

*[[AuK/Teile_und_Herrsche_1_SS10/Aufgaben|Computerübung]]


==Links, Quellen und Danksagungen==

===Internet-Links===
# [http://ww3.algorithmdesign.net/handouts/MergeSort.pdf Algorithm Design - Internet Examples]
# [http://www.apl.jhu.edu/Notes/LMBrown/courses/605-202/notes/Merge-and-Quick-Sort.pdf APL Center]
# [http://www.deinprogramm.de/MUPIS/Uberblick_files/MPS6541b.pdf Dein Programm]
# [http://www.tinohempel.de/info/info/ti/komplexitaet.htm Homepage von Tino Hempel]
# [http://informatik.bildung-rp.de/fileadmin/user_upload/informatik.bildung-rp.de/Weiterbildung/pdf/WB-X-6-PraktischeGrenzenScript.pdf Informatik Bildungsserver]
# [http://www.pittsburgh.intel-research.net/~chensm/papers/multicore-cache-soda08.pdf Intel Labs - Pittsburgh]
# [http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/LectureNotes/lec3.pdf Massachusetts Institute of Technology]
# [http://zach.in.tu-clausthal.de/teaching/info2_06/folien/07_div-conq_2_4up.pdf TU-Clausthal]
# [http://www.tu-ilmenau.de/fakia/fileadmin/template/startIA/ktea/Lehre/ea/ws05/06_Sortieren_4.pdf TU-Ilmenau]
# [http://cseweb.ucsd.edu/classes/sp09/cse101/dncsteps.pdf UCSD Jacobs School]
# [http://richling.de/greifswald/VA/02-Einfuehrung.pdf Uni Greifswald]
# [http://www2.cs.uni-paderborn.de/cs/ag-bloemer/lehre/dua_SS2005/material/04_divide.pdf Uni-Paderborn]
# [http://www.cs.uni-potsdam.de/ti/lehre/04-ALuP-II/slides-18b.pdf Uni Potsdam]
# [http://cvpr.uni-muenster.de/teaching/ws08/info1WS08/script/Kapitel0-Organisation.pdf Uni Münster]
# [http://www.dcs.gla.ac.uk/~pat/52233/slides/MergeSort1x1.pdf University of Glasgow]
# [http://de.wikipedia.org/wiki/Divide_and_Conquer Wikipedia - DaC]
# [http://de.wikipedia.org/wiki/Mergesort Wikipedia - Mergesort]
# [http://de.wikipedia.org/wiki/Quicksort Wikipedia - Quicksort]

===Quellen===

; [1] Wagenknecht, Christian: 
: Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003.
; [2] Cormen, Th. H.; Leiserson, Ch. E.; Rivest, R.; Stein, C.:
: Algorithmen - Eine Einführung, 2. Auflage.- Oldenburg Wissensch. Vlg., 2007

===Danksagung===
Ein besonderer Dank geht an Prof. Dr. rer. nat. Christian Wagenknecht, für die schnelle Hilfe bei der Wiki-Arbeit und bessere Umsetzung.
Desweiteren danken wir Dipl.-Inf.(FH) Michael Hielscher für seine Hilfe, bei der Umsetzung mit dem Quellcode und Hilfestellung bei dem Umgang mit Wiki.
Und gleichfalls geht ein Dank an unseren Mitkommilitonen Felix Deutschmann, für die Hilfe bei dem Java-Code.