Grundlagen der funktionsorientierten Programmierung mit SCHEME/QuickSort
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
<code id="4e75cabaddec3" hidden>
;-- M. Hielscher / Chr. Wagenknecht / V. Berger --
(define random-maker
(let* ((multiplier 48271)
(modulus 2147483647)
(apply-congruence
(lambda (current-seed)
(let ((candidate (modulo (* current-seed multiplier) modulus)))
(if (zero? candidate)
modulus
candidate))))
(coerce
(lambda (proposed-seed)
(if (integer? proposed-seed)
(- modulus (modulo proposed-seed modulus)) 19880214))))
(lambda (initial-seed)
(let ((seed (coerce initial-seed)))
(lambda args
(cond ((null? args)
(set! seed (apply-congruence seed))
(/ (- modulus seed) modulus))
((null? (cdr args))
(let* ((proposed-top
(ceiling (abs (car args))))
(exact-top
(if (inexact? proposed-top)
(inexact->exact proposed-top)
proposed-top))
(top
(if (zero? exact-top)
1
exact-top)))
(set! seed (apply-congruence seed))
(inexact->exact (floor (* top (/ seed modulus))))))
((eq? (cadr args) 'reset)
(set! seed (coerce (car args))))
(else
(display "random: unrecognized message")
(newline))))))))
(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)
(define random (random-maker (time-nanosecond (current-time))))
(define listequal?
(lambda (ls1 ls2)
(cond
[(and (null? ls1) (null? ls2)) #t]
[(or (null? ls1) (null? ls2)) #f]
[(and (list? (car ls1)) (list? (car ls1)))
(and (listequal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))]
[else
(and (equal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))])))
(define rand 50)
(define maxbreite (- 400 (* 2 rand)))
(define maxhoehe (- 300 (* 2 rand)))
(define minmax
(lambda (ls)
(letrec
([extremsuche
(lambda (extrem ls op)
(cond
[(null? ls) extrem]
[(op extrem (car ls)) (extremsuche (car ls) (cdr ls) op)]
[else
(extremsuche extrem (cdr ls) op)]))])
(cons (extremsuche 0 ls >)
(extremsuche 0 ls <)))))
(define balken
(lambda (hoehe breite turtle)
(forward turtle breite) (left turtle 90)
(forward turtle hoehe) (left turtle 90)
(forward turtle breite) (left turtle 90)
(forward turtle hoehe) (left turtle 90)
(forward turtle breite)))
(define balkendiagramm
(lambda (ls nr)
(let* ([breite (/ maxbreite (length ls))]
[extremwerte (minmax ls)]
[min (car extremwerte)] [max (cdr extremwerte)]
[canvas (eval (string->symbol (string-append "canvas" (number->string nr))))]
[turtle (eval (string->symbol (string-append "turtle" (number->string nr))))])
(letrec
([zeichnen
(lambda (min max ls)
(if (null? ls)
'ok
(begin
(balken (floor (* (/ (car ls) (- max min)) maxhoehe)) (floor breite) turtle)
(zeichnen min max (cdr ls)))))])
(clear canvas)
(hide turtle)
(move turtle rand (+ rand (* (/ max (- max min)) maxhoehe))) (right turtle 90)
(zeichnen min max ls)))))
</code>
== Algorithmus ==
[[Datei:Hoare.jpg|miniatur|C.A.R. Hoare]]
Die Zweifel an einer guten Zeiteffizienz von MinSort unter den Sortieralgorithmen sind berechtigt.<br />
Wir betrachten deshalb den nachfolgenden Algorithmus und implementieren ihn.
'''Beschreibung:'''
* Benutze das erste Element einer (numerischen) Liste als Trennelement.
* Erzeuge zwei Teillisten, deren Elemente kleiner bzw. größer als das Trennelement sind.
* Setze dieses Verfahren für jede nichtleere Teilliste fort und
* füge die sortierten Teillisten zur Gesamtliste zusammen.
Den so beschriebenen Sortieralgorithmus bezeichnet man als ''QuickSort'' (schnelles Sortieren). Er wurde 1962 von dem britischen Informatiker Sir '''Charles Antony Richard Hoare''' (* 11. Januar 1934) vorgestellt.
'''Beispiel:'''
<blockquote>[[Bild:QuickSort-Beispiel1.gif]]</blockquote>
'''Implementation:'''
<code id="4bf43ee409dc7">
(define zufallszahl
(lambda (min max)
(+ (random (- max min -1)) min)))
(define zufallsliste
(lambda (min max anzahl)
(if (= anzahl 0)
()
(cons (zufallszahl min max) (zufallsliste min max (- anzahl 1))))))
;Erzeuge zwei Teillisten, deren Elemente bezüglich eines Trennelementes vorsortiert sind
(define zerlegen
(lambda (el ls)
(if (null? ls)
(list () ())
(let ([tls (zerlegen el (cdr ls))])
;hier erfolgt die korrekte Einordnung des ersten Listenelements
;in die bereits vorhandene erste oder zweite Teilliste
...))))
;QuickSort
(define quicksort
(lambda (ls)
(if (null? ls)
()
(let ([tls (zerlegen (car ls) (cdr ls))])
;hier werden
;- die sortierte erste Teilliste,
;- das Trennelement (als einelementige Liste),
;- die sortierte zweite Teilliste
;zusammengesetzt
...))))
</code>
<check>
(listequal? (quicksort '(12 4 5 6 33 2 6 7 1 47)) '(1 2 4 5 6 6 7 12 33 47))
</check>
<table border="0" cellpadding="0" cellspacing="0">
<tr>
<td align="center">
'''Ungeordnete Zufallszahlen:'''
<canvas w="400" h="300"></canvas>
</td>
<td> </td>
<td align="center">
'''Geordnete Zufallszahlen:'''
<canvas w="400" h="300"></canvas>
</td>
</tr>
</table>
<run id="4e75cabade0ed">
(define ls (zufallsliste 1 1000 100))
(balkendiagramm ls 1)
(define ls-sort (quicksort ls))
(balkendiagramm ls-sort 2)
</run>
== Effizienz von QuickSort ==
=== Experimente zum Zeitaufwand ===
Wir wollen uns auf die empirische Analyse des Zeitaufwands von QuickSort beschränken und definieren dazu:
<code id="4bf26382b419d">
(define count 0)
(define quicksort-aufwand
(lambda (ls)
(letrec
([zerlege
(lambda (el ls)
(if (null? ls)
(list () ())
(let ([tls (zerlege el (cdr ls))])
(set! count (+ 1 count)) ;Zerlegen in Teillisten
(if (< (car ls) el)
(list (cons (car ls) (car tls)) (cadr tls))
(list (car tls) (cons (car ls) (cadr tls)))))))])
(if (null? ls)
()
(let ([tls (zerlege (car ls) (cdr ls))])
(set! count (+ 1 count)) ;Zusammensetzen der Teillisten
(append (quicksort-aufwand (car tls))
(list (car ls))
(quicksort-aufwand (cadr tls))))))))
(define quicksort-ausgabe
(lambda (min max anzahl)
(let ([ls (zufallsliste min max anzahl)])
(set! count 0)
(display "Ungeordnete Zufallszahlen:") (newline)
(display ls) (newline)
(display "Geordnete Zufallszahlen:") (newline)
(display (quicksort-aufwand ls)) (newline)
(display "Anzahl der Zerlegungen und Zusammensetzungen: ") (display count) (newline)
'ok)))
</code>
<run id="4bf26382b512d">
(quicksort-ausgabe 1 1000 20)
</run>
Die ersten Tests zeigen: QuickSort scheint deutlich effizienter als MinSort zu sein.<br />
Wir überprüfen diese Vermutung mit den bekannten Prozeduren für Mehrfachexperimente sowie den entsprechenden grafischen Darstellungen:
<code id="4bf2a0ffe0fd7">
(define quicksort-mehrfach
(lambda (min max anzahl whlg)
(letrec
([summe
(lambda (n)
(if (= n 0)
0
(begin
(set! count 0)
(quicksort-aufwand (zufallsliste min max anzahl))
(+ count (summe (- n 1))))))])
(exact->inexact (/ (summe whlg) whlg)))))
</code>
<run id="4bf2a0ffe3eb6">
(quicksort-mehrfach 1 1000 20 100)
</run>
<code id="4bf2a0ffe1f75">
(define experiment
(lambda (min max anzahl schrittweite whlg)
(if (< anzahl 1)
()
(append (experiment min max (- anzahl schrittweite) schrittweite whlg)
(list (quicksort-mehrfach min max anzahl whlg))))))
</code>
'''Achtung!''' In Erwartung einer besseren Laufzeit wollen wir im Vergleich zu MinSort mit höheren Wiederholraten experimentieren.
<canvas w="400" h="300"></canvas>
<run id="4e75cabade19f">
(balkendiagramm (experiment 1 1000 200 5 50) 3)
</run>
Abschließend wollen wir die Effizienz an einer bereits sortierten Liste untersuchen. Der ''von uns implementierte'' QuickSort-Algorithmus führt dazu, dass die jeweils linke Teilliste leer bleibt. Damit werden bei gleichen Listenlängen größere Rekursionstiefen notwendig, was auch zu einem größeren Zeitaufwand führen muss.<br />
Wir untersuchen also QuickSort im ''Worst-case-Fall'':
<code id="4bf2dfa23a16a">
(define quicksort-worst-case
(lambda (min max anzahl)
(set! count 0)
(quicksort-aufwand (quicksort (zufallsliste min max anzahl)))
count))
(define experiment-worst-case
(lambda (min max anzahl schrittweite)
(if (< anzahl 1)
()
(append (experiment-worst-case min max (- anzahl schrittweite) schrittweite)
(list (quicksort-worst-case min max anzahl))))))
</code>
'''Beachte:''' Beim Experimentieren mit dem Worst-case-Fall sind keine Wiederholungen notwendig.
<canvas w="400" h="300"></canvas>
<run id="4e75cabade258">
(balkendiagramm (experiment-worst-case 1 1000 200 5) 4)
</run>
=== Aufgaben ===
<ol>
<li>
Belegen Sie durch eigene empirische Untersuchungen, dass für den QuickSort-Algorithmus im Mittel gilt: <math>T(n) = \mathcal{O}(n \cdot \log_2 n)</math>
</li>
<li>
Bestätigen Sie ebenfalls durch geeignete Untersuchungen, dass QuickSort im Worst-Case-Fall einem quadratischen Zeitaufwand unterliegt.
</li>
<li>
Unterbreiten Sie Vorschläge, wie der Worst-Case-Fall in der Praxis weitestgehend vermieden werden kann.
</li>
</ol>
== Zusammenfassung ==
QuickSort ist ein typisches Beispiel für ''Teile-und-herrsche-Algorithmen'' (engl.: divide and conquer):<br />
Allgemein wird ein Problem gelöst, indem man es
<ol>
<li>in Teilprobleme zerlegt (teile - divide),</li>
<li>diese Teilprobleme löst (herrsche - conquer) und</li>
<li>die Teillösungen zur Gesamtlösung zusammensetzt.</li>
</ol>
Für den Quicksort-Algorithmus lassen sich folgende Abhängigkeiten und Zeitaufwandsklassen angeben:
<table border="0" cellspace="0" cellpadding="4">
<tr valign="top">
<td rowspan="2"><b>best case: </b></td>
<td><math>T(n) = n \cdot \log_2 n</math> bzw.</td>
</tr>
<tr>
<td><math>T(n) = \mathcal{O}(n \cdot \log_2 n)</math></td>
</tr>
<tr valign="top">
<td rowspan="2"><b>average case: </b></td>
<td><math>T(n) = 2 \cdot n \cdot \ln n \approx 1.386 \cdot n \cdot \log_2 n</math> bzw.</td>
</tr>
<tr>
<td><math>T(n) = \mathcal{O}(n \cdot \log_2 n)</math></td>
</tr>
<tr valign="top">
<td rowspan="2"><b>worst case: </b></td>
<td><math>T(n) = \frac{n}{2} \cdot (n+1)</math> bzw.</td>
</tr>
<tr>
<td><math>T(n) = \mathcal{O}(n^2)</math></td>
</tr>
</table>
Im Mittel ist also QuickSort deutlich effizienter als MinSort. Im ungünstigsten Fall kann es aber ebenso ineffizient werden.<br />
Wir wollen die konkreten Funktionen zum Zeitaufwand von QuickSort vergleichend gegenüberstellen:
<code id="4e75cabaddfcc">
(define x-von 0)
(define x-bis 100)
(define y-von 0)
(define y-bis 1000)
(define log2
(lambda (x)
(/ (log x) (log 2))))
(define qs-best-case
(lambda (x)
(* x (log2 x))))
(define qs-average-case
(lambda (x)
(* 1.386 x (log2 x))))
(define qs-worst-case
(lambda (x)
(* 1/2 x (+ x 1))))
</code>
<canvas w="610" h="460"></canvas>
<code id="5071c906818dc" hidden>
(define nr 5)
(define genau 6)
(define breite 610)
(define hoehe 460)
(define rand 50)
(define canvas (eval (string->symbol (string-append "canvas" (number->string nr)))))
(define bez "x")
(define raster #f)
(define sqr
(lambda (x)
(* x x)))
(define black
(lambda (canvas)
(setcolor canvas 0 0 0)))
(define red
(lambda (canvas)
(setcolor canvas 255 0 0)))
(define brown
(lambda (canvas)
(setcolor canvas 100 50 0)))
(define orange
(lambda (canvas)
(setcolor canvas 255 100 0)))
(define yellow
(lambda (canvas)
(setcolor canvas 255 200 0)))
(define green
(lambda (canvas)
(setcolor canvas 0 255 0)))
(define blue
(lambda (canvas)
(setcolor canvas 0 0 255)))
(define pink
(lambda (canvas)
(setcolor canvas 200 50 200)))
(define n-tes-mod
(lambda (ls anz)
(list-ref ls (modulo anz (length ls)))))
(define genaurunden
(lambda (x anz)
(let ([n 0] [erg 0])
(if (not (= x 0))
(set! n (inexact->exact (round (- anz (/ (log (abs x)) (log 10)) -0.5)))))
(set! erg (/ (round (* x (expt 10 n))) (expt 10 n)))
(if (integer? erg)
(inexact->exact erg)
(exact->inexact erg)))))
(define groessenordnung
(lambda (x)
(if (= x 0)
1
(let ([pot (/ (log (abs x)) (log 10))])
(genaurunden (expt 10 (floor pot)) genau)))))
(define minimum
(lambda (x y)
(if (< x y)
(if (> x 0) 0 x)
(if (> y 0) 0 y))))
(define maximum
(lambda (x y)
(if (> x y)
(if (< x 0) 0 x)
(if (< y 0) 0 y))))
(define ungleich-null
(lambda (x y)
(if (= x y 0) (+ y 1) y)))
(define schaubild
(lambda (fkt-list x1 x2 y1 y2 von bis koordcolor color-list)
(clear canvas)
(setwidth canvas 1)
(let* ([textgroesse 9]
[xu (exact->inexact (minimum x1 x2))] [xo (exact->inexact (maximum x1 x2))] [xo (ungleich-null xu xo)]
[yu (exact->inexact (minimum y1 y2))] [yo (exact->inexact (maximum y1 y2))] [yo (ungleich-null yu yo)]
[spmin rand] [spmax (- breite rand)] [spend (+ spmax 15)]
[zemin (- hoehe rand)] [zemax rand] [zeend (- zemax 15)]
[s0 (+ (* (/ (- xu) (- xo xu)) (- spmax spmin)) spmin)]
[z0 (+ (* (/ (- yu) (- yo yu)) (- zemax zemin)) zemin)]
[spvon (+ (* (/ (- von xu) (- xo xu)) (- spmax spmin)) spmin)]
[spbis (+ (* (/ (- bis xu) (- xo xu)) (- spmax spmin)) spmin)]
[mx (- xo xu)] [teilerx 1] [stepx (/ (- spmax spmin) mx teilerx)] [ex mx] [faktorx 1]
[my (- yo yu)] [teilery 1] [stepy (/ (- zemin zemax) my teilery)] [ey my] [faktory 1])
(letrec
([anpassen
(lambda (m)
(if (> m 2)
(if (<= m 20)
m
(anpassen (/ m 10)))
(if (> m 2)
m
(anpassen (* m 10)))))]
[teilen
(lambda (m)
(cond
[(< m 3) 5]
[(< m 10) 2]
[else 1]))]
[x-raster
(lambda (sx zy)
(if (> zy (- zemax 1))
(begin
(line canvas sx zy sx zy)
(x-raster sx (- zy 3)))))]
[x-teilen-positiv
(lambda (sx)
(if (< sx (+ spmax 1))
(begin
(line canvas sx z0 sx (- z0 3))
(if raster (x-raster sx zemin))
(x-teilen-positiv (+ sx stepx)))))]
[x-teilen-negativ
(lambda (sx)
(if (> sx (- spmin 1))
(begin
(line canvas sx z0 sx (- z0 3))
(if raster (x-raster sx zemin))
(x-teilen-negativ (- sx stepx)))))]
[y-raster
(lambda (sx zy)
(if (< sx (+ spmax 1))
(begin
(line canvas sx zy sx zy)
(y-raster (+ sx 3) zy))))]
[y-teilen-positiv
(lambda (zy)
(if (> zy (- zemax 1))
(begin
(line canvas s0 zy (+ s0 3) zy)
(if raster (y-raster spmin zy))
(y-teilen-positiv (- zy stepy)))))]
[y-teilen-negativ
(lambda (zy)
(if (< zy (+ zemin 1))
(begin
(line canvas s0 zy (+ s0 3) zy)
(if raster (y-raster spmin zy))
(y-teilen-negativ (+ zy stepy)))))]
[faktor
(lambda (len step)
(if (<= len step)
1
(+ 1 (faktor (- len step) step))))]
[textwidth
(lambda (str)
(* textgroesse (string-length str)))]
[textout-widthcenter
(lambda (sx zy str)
(if (integer? (string->number str))
(text canvas (- sx (/ (textwidth str) 2))
(+ zy (/ textgroesse 2/3)) str textgroesse)
(text canvas (- sx (/ (textwidth str) 2) (- (/ textgroesse 2)))
(+ zy (/ textgroesse 2/3)) str textgroesse)))]
[textout-heightcenter
(lambda (sx zy str)
(if (integer? (string->number str))
(text canvas (- sx (textwidth str) 2)
(+ zy (/ textgroesse 2)) str textgroesse)
(text canvas (- sx (textwidth str) (- (/ textgroesse 2)))
(+ zy (/ textgroesse 2)) str textgroesse)))]
[textout-bez-widthcenter
(lambda (sx zy str)
(text canvas (- sx (/ (textwidth str) 4))
(- zy textgroesse) str textgroesse))]
[textout-bez-heightcenter
(lambda (sx zy str)
(text canvas (+ sx (/ textgroesse 2))
(+ zy (/ textgroesse 2)) str textgroesse))]
[x-bezeichnen-positiv
(lambda (sx e)
(if (< sx (+ spmax 1))
(begin
(textout-widthcenter sx z0 (number->string (genaurunden e genau)))
(x-bezeichnen-positiv (+ sx (* stepx faktorx)) (+ e (* ex faktorx))))))]
[x-bezeichnen-negativ
(lambda (sx e)
(if (> sx (- spmin 1))
(begin
(textout-widthcenter sx z0 (number->string (genaurunden e genau)))
(x-bezeichnen-negativ (- sx (* stepx faktorx)) (- e (* ex faktorx))))))]
[y-bezeichnen-positiv
(lambda (zy e)
(if (> zy (- zemax 1))
(begin
(textout-heightcenter s0 zy (number->string (genaurunden e genau)))
(y-bezeichnen-positiv (- zy (* stepy faktory)) (+ e (* ey faktory))))))]
[y-bezeichnen-negativ
(lambda (zy e)
(if (< zy (+ zemin 1))
(begin
(textout-heightcenter s0 zy (number->string (genaurunden e genau)))
(y-bezeichnen-negativ (+ zy (* stepy faktory)) (- e (* ey faktory))))))]
[x-achse-bezeichnen
(lambda (str)
(textout-bez-heightcenter spend z0 str))]
[y-achse-bezeichnen
(lambda (str)
(let ([y-str (string-append "f(" str ")")])
(textout-bez-widthcenter s0 zeend y-str)))]
[graph-startpkt
(lambda (fkt pkt)
(let ([sx (car pkt)] [zy (cdr pkt)])
(if (< sx (+ spbis 1))
(with-failure-continuation
(lambda (error-record error-k) (graph-startpkt fkt (cons (+ sx 1) zy)))
(lambda ()
(let* ([x (+ (* (/ (- sx spmin) (- spmax spmin)) (- xo xu)) xu)] [y (fkt x)])
(if (real? y)
(begin
(set! zy (+ (* (/ (- y yu) (- yo yu)) (- zemax zemin)) zemin))
(if (> zy zemin) (set! zy zemin))
(if (< zy zemax) (set! zy zemax))
(cons sx zy))
(graph-startpkt fkt (cons (+ sx 1) zy))))))
(cons sx zy))))]
[graph-zeichnen
(lambda (fkt pkt)
(let ([sx (car pkt)] [zy (cdr pkt)])
(if (< sx (+ spbis 1))
(with-failure-continuation
(lambda (error-record error-k)
(graph-zeichnen fkt (graph-startpkt fkt (cons (+ sx 1) zy))))
(lambda ()
(let* ([sx-neu (+ sx 1)]
[x (+ (* (/ (- sx-neu spmin) (- spmax spmin)) (- xo xu)) xu)] [y (fkt x)])
(if (real? y)
(let ([zy-neu (+ (* (/ (- y yu) (- yo yu)) (- zemax zemin)) zemin)])
(if (> zy-neu zemin) (set! zy-neu zemin))
(if (< zy-neu zemax) (set! zy-neu zemax))
(if (and (< zy zemin) (> zy zemax) (< zy-neu zemin) (> zy-neu zemax))
(line canvas sx zy sx-neu zy-neu))
(graph-zeichnen fkt (cons sx-neu zy-neu)))
(graph-zeichnen fkt (graph-startpkt fkt (cons (+ sx 1) zy))))))))))]
[graph-list-zeichnen
(lambda (fkt-ls anz color-ls)
(if (not (null? fkt-ls))
(let ([fkt (eval (car fkt-ls))])
((eval (n-tes-mod color-ls anz)) canvas)
(graph-zeichnen fkt (graph-startpkt fkt (cons spvon z0)))
(graph-list-zeichnen (cdr fkt-ls) (+ anz 1) color-ls))))])
(koordcolor canvas)
(line canvas spmin z0 spend z0)
(line canvas s0 zemin s0 zeend)
(line canvas (- spend 6) (- z0 2) spend z0)
(line canvas (- spend 6) (+ z0 2) spend z0)
(line canvas (- spend 6) (- z0 2) (- spend 6) (+ z0 2))
(line canvas (- s0 2) (+ zeend 6) s0 zeend)
(line canvas (+ s0 2) (+ zeend 6) s0 zeend)
(line canvas (- s0 2) (+ zeend 6) (+ s0 2) (+ zeend 6))
(set! mx (anpassen mx)) (set! teilerx (teilen mx))
(set! stepx (/ (- spmax spmin) mx teilerx))
(set! my (anpassen my)) (set! teilery (teilen my))
(set! stepy (/ (- zemin zemax) my teilery))
(x-teilen-positiv (+ s0 stepx)) (x-teilen-negativ (- s0 stepx))
(y-teilen-positiv (- z0 stepy)) (y-teilen-negativ (+ z0 stepy))
(set! ex (/ ex mx teilerx))
(set! faktorx (faktor
(* textgroesse (string-length (number->string (genaurunden ex genau))))
stepx))
(set! ey (/ ey my teilery))
(set! faktory (faktor
textgroesse
stepy))
(if (= yu 0)
(x-bezeichnen-positiv s0 0)
(x-bezeichnen-positiv (+ s0 (* stepx faktorx)) (* ex faktorx)))
(x-bezeichnen-negativ (- s0 (* stepx faktorx)) (- (* ex faktorx)))
(if (= xu 0)
(y-bezeichnen-positiv z0 0)
(y-bezeichnen-positiv (- z0 (* stepy faktory)) (* ey faktory)))
(y-bezeichnen-negativ (+ z0 (* stepy faktory)) (- (* ey faktory)))
(x-achse-bezeichnen bez)
(y-achse-bezeichnen bez)
(if (< spvon spmin) (set! spvon spmin)) (if (> spbis spmax) (set! spbis spmax))
(graph-list-zeichnen fkt-list 0 color-list)
'ok))))
</code>
<run id="4e75cabade305">
(schaubild (list qs-best-case qs-average-case qs-worst-case)
x-von x-bis y-von y-bis x-von x-bis
black '(red blue green))
</run>
== Zum Weiterarbeiten ==
=== MergeSort ===
Der Sortieralgorithmus [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/MergeSort|''MergeSort'']] ist eine effiziente Alternative zum QuickSort, da sein Zeitaufwand in allen drei Fällen (best-, average-, worst-case) <math>T(n) = \mathcal{O}(n \cdot \log_2 n)</math> beträgt. "Merge" bedeutet hier soviel wie "Zusammensetzen". Die Übersetzung mit "Sortieren durch Mischen" ist eher irreführend.
'''Beschreibung:'''
* Teile eine (numerische) Liste in zwei etwa gleich große Teillisten.
* Führe diese Teilung bei jeder Teillisten solange fort, bis nur noch einelementige Teillisten bestehen bleiben.
* Setze diese Teillisten in der richtigen Reihenfolge zur sortierten Gesamtliste zusammen.
Implementieren Sie diesen Algorithmus.<br />
Zur [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/MergeSort|Problemlösung]].