Grundlagen der funktionsorientierten Programmierung mit SCHEME/MinSort
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>SchemeJS</language>
<code id="5bb86db55ca45" hidden>
(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 ==
Bei einfachen rekursiven Problemlösungen haben wir Algorithmen implementiert, die der Suche des Minimums bzw. dem Streichen eines Elements in [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Komplexe Anwendungen: Numerische Listen|unverschachtelten numerischen Listen]] entsprechen.
Daraus haben wir bereits einen ersten ''Sortieralgorithmus'' konstruiert:
'''Beschreibung:'''
* Suche aus der Liste das Minimum heraus,
* streiche es an seiner ursprünglichen Stelle und
* stelle es der Minimum-sortierten Restliste voran.
Da sich dieser Algorithmus am Minimum einer Liste orientiert, bezeichnen wir ihn als ''MinSort''. Auf diese Weise sortieren Kartenspieler recht häufig ihre Spielkarten in der Hand.<br />
Implementieren Sie den Algorithmus und testen Sie ihn an Listen mit Zufallszahlen <math>z</math>, mit <math>z \in \mathbb{Z}</math>.<br />
Stellen Sie dazu die ungeordnete und die geordnete Zahlenliste jeweils in einem Balkendiagramm grafisch dar.
<code id="4be1586d28238">
(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))))))
;Minimum einer Liste
(define minimum
(lambda (ls)
...))
;Streichen eines Listenelements beim ersten Auftreten
(define streichen
(lambda (el ls)
...))
;Minsort
(define minsort
(lambda (ls)
...))
</code>
<check>
(listequal? (minsort '(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="4e75b49a970fd">
(define ls (zufallsliste 1 1000 100))
(balkendiagramm ls 1)
(define ls-sort (minsort ls))
(balkendiagramm ls-sort 2)
</run>
'''Hinweis:''' Um mehrere Zeichenflächen nutzen zu können, muss die Prozedur <tt>balkendiagramm</tt> mit einem zusätzlichen Parameter ausgestattet werden, der einer fortlaufenden Nummerierung entspricht:
(balkendiagramm
<ls> ; Liste mit Zahlenwerten
<nr>) ; fortlaufende Nummerierung des Balkendiagramms
== Effizienz von MinSort ==
=== Theoretische Analyse des Zeitaufwands ===
Wir überlegen uns zunächst, wie viele Vergleiche bei der Minimumsuche insgesamt durchgeführt werden:
<blockquote>[[Bild:MinSort-Schema1.gif]]</blockquote>
Das Schema lässt sich mit einer Dreieckfläche vergleichen. Damit sind also <math>\tfrac{n}{2} (n-1)</math> Vergleiche zum Auffinden des Minimums notwendig.<br />
Zum Streichen des gefundenen Minimums sind ähnliche Überlegungen möglich.
Im Mittel kann man aber davon ausgehen, dass das Streichen nach <math>\tfrac{n}{2}</math> Vergleichen pro Durchlauf abgeschlossen ist (endständig rekursive Prozedur).<br />
Damit ist folgende Abschätzung für den Gesamtaufwand möglich:<br />
<blockquote>
<math>T(n) = \underbrace{\frac{n}{2} \cdot (n-1)}_{Min-Suche} + \underbrace{\frac{1}{2} \cdot \frac{n}{2} \cdot (n-1)}_{Streichen} = \frac{3}{4} \cdot n \cdot (n-1)</math><br /><br />
<math>T(n) \approx \frac{3}{4} \cdot n^2</math> bzw.<br /><br />
<math>T(n) = \mathcal{O}(n^2)</math>
</blockquote>
Das Minimum-Sortieren erfolgt mit ''quadratischem Zeitaufwand''.
=== Experimente zum Zeitaufwand ===
Wir wollen unsere theoretische Analyse empirisch bestätigen. Dazu definieren wir unseren MinSort-Algorithmus mit einem "eingebauten" (Zeittakt-)Zähler:
<code id="5bb86db55cadb">
(define count 0)
(define minsort-aufwand
(lambda (ls)
(letrec
([minsuche
(lambda (ls)
(cond
[(null? (cdr ls)) (car ls)]
[(< (car ls) (cadr ls))
(set! count (+ 1 count)) ;Extremwertsuche mit neuem Element
(minsuche (cons (car ls) (cddr ls)))]
[else
(set! count (+ 1 count)) ;Extremwertsuche mit altem Element
(minsuche (cdr ls))]))]
[streiche
(lambda (el ls)
(cond
[(null? ls) ()]
[(eqv? el (car ls))
(set! count (+ 1 count)) ;Streichen
(cdr ls)]
[else
(set! count (+ 1 count)) ;Suche zum Streichen
(cons (car ls) (streiche el (cdr ls)))]))])
(if (null? ls)
()
(let ([el (minsuche ls)])
(cons el (minsort-aufwand (streiche el ls))))))))
(define minsort-ausgabe
(lambda (min max anzahl)
(let ([ls (zufallsliste min max anzahl)])
(set! count 0)
(display "Ungeordnete Zufallszahlen:")
(display ls)
(display "Geordnete Zufallszahlen:")
(display (minsort-aufwand ls))
(display "Anzahl der Minimumvergleiche und Streichungen: " (number->string count))
'ok)))
</code>
<run id="5bb86db55cbf5">
(minsort-ausgabe 1 1000 20)
</run>
Im Weiteren wollen wir uns wieder nur auf die Zählergebnisse unseres "Zeittaktmessers" konzentrieren.<br />
Dazu sollen die Wiederholungen des Experimentes automatisiert werden:
<code id="5bb86db55cb61">
(define minsort-mehrfach
(lambda (min max anzahl whlg)
(letrec
([summe
(lambda (n)
(if (= n 0)
0
(begin
(set! count 0)
(minsort-aufwand (zufallsliste min max anzahl))
(+ count (summe (- n 1))))))])
(/ (summe whlg) whlg))))
</code>
<run id="5bb86db55cc6b">
(minsort-mehrfach 1 1000 20 10)
</run>
Schließlich sollen die Ergebnisse unserer empirischen Untersuchung wieder im Balkendiagramm visualisiert werden.
<code id="4be6644a0f20c">
(define experiment
(lambda (min max anzahl schrittweite whlg)
(if (< anzahl 1)
()
(append (experiment min max (- anzahl schrittweite) schrittweite whlg)
(list (minsort-mehrfach min max anzahl whlg))))))
</code>
'''Achtung!''' Mit kleinen Wiederholraten und etwas Geduld experimentieren!
<canvas w="400" h="300"></canvas>
<run id="5bb86db55ccd5">
(balkendiagramm (experiment 1 1000 20 1 10) 3)
</run>
Die empirischen Untersuchungen bestätigen den quadratischen Zeitaufwand von MinSort.
== Aufgaben ==
<ol>
<li>
Ermitteln Sie mit der Prozedur <tt>minsort-mehrfach</tt> empirisch die Zeitaufwandsfunktion
<math>T:\mathbb{N} \rightarrow \mathbb{R}^+</math>.<br />
Nutzen Sie dazu eine Tabellenkalkulation oder den grafikfähigen Taschenrechner.
Bestimmen Sie die Funktionsgleichung <math>T(n) = f(n)</math> durch quadratische Regression und vergleichen Sie diese mit den oben angeführten theoretischen Überlegungen.
</li>
<li>
Implementieren Sie unter ''DrScheme'' den MinSort-Algorithmus zum lexikografischen Ordnen von Zeichenketten.<br />
Dabei soll wahlweise aufsteigend oder absteigend geordnet werden können (Prozeduren höherer Ordnung!).
</li>
</ol>
== Zum Weiterarbeiten ==
[[Datei:Gartenzwerg_Blumentopf1.JPG|miniatur|GnomeSort?]]
=== GnomeSort ===
In einem Garten sind Bumentöpfe in einer Reihe aufgestellt. Gartenzwerge sollen sie nun der Größe nach aufsteigend sortieren. Sie benutzen dazu den folgenden Algorithmus:<br />
<ul>
<li> Beginne links und vergleiche die beiden ersten Töpfe.</li>
<li> Stehen sie in der richtigen Reihenfolge gehe ein Schritt nach rechts.</li>
<li> Wenn sie nicht in der korrekten Reihenfolge stehen, vertausche die beiden Töpfe und gehe einen Schritt nach links.<br />
Ist der Schritt nach links nicht möglich, gehe ein Schritt nach rechts.</li>
<li> Wiederhole das Sortieren bis zum letzten Blumentopf.</li>
</ul>
Implementieren Sie diesen Algorithmus und untersuchen Sie seine Effizienz im average- best- und worst-case-Fall.<br />
Zur [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/GnomeSort|Problemlösung]].