Grundlagen der funktionsorientierten Programmierung mit SCHEME/GnomeSort
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>SchemeJS</language>
<code id="5bb8705924281" 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>
[[Datei:Gartenzwerg_Blumentopf1.JPG|miniatur|GnomeSort - los geht's!]]
== Algorithmus ==
In einem Garten sind Blumentö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>
Die Größe der Blumentöpfe wird mit Zufallszahlen festgelegt:
<code id="4e75c1edaeaa9">
(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))))))
</code>
Da keine Indizierung der Listenelemente möglich ist, wird der Algorithmus mit den beiden Listen <tt>ls1</tt> und <tt>ls2</tt> implementiert. Die Liste <tt>ls1</tt> enthält die unsortierte Zahlenliste. Mit <tt>ls2</tt> wird die sortierte Zahlenlise gebildet. Beim Schritt nach rechts wird das erste Listenelement von <tt>ls1</tt> der Liste <tt>ls2</tt> vorangestellt. Analog wird beim Schritt nach links das erste Listenelement von <tt>ls2</tt> zurückgenommen und <tt>ls1</tt> vorangestellt. Zum Schluss muss die sortierte Liste (d.h. <tt>ls2</tt>) umgekehrt werden:
<code id="4e79d0ed68314">
;GnomeSort
(define gnomesort
(lambda (ls)
(letrec
([sort
(lambda (ls1 ls2)
...)])
(reverse (sort ls ())))))
</code>
<check>
(and (listequal? (gnomesort '(12 4 5 6 33 2 6 7 1 47)) '(1 2 4 5 6 6 7 12 33 47))
(listequal? (gnomesort '(147)) '(147))
(listequal? (gnomesort '()) '()))
</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="4e75c1edaee66">
(define ls (zufallsliste 1 1000 100))
(balkendiagramm ls 1)
(define ls-sort (gnomesort ls))
(balkendiagramm ls-sort 2)
</run>
'''Hinweis:''' Syntax der Prozedur <tt>balkendiagramm</tt>:
(balkendiagramm
<ls> ; Liste mit Zahlenwerten
<nr>) ; fortlaufende Nummerierung des Balkendiagramms
== Effizienz von GnomeSort ==
=== Average-Case-Experimente ===
Wir definieren unseren GnomeSort-Algorithmus mit einem "eingebauten" (Zeittakt-)Zähler:
<code id="5bc9d25eb3f68">
(define count 0)
(define gnomesort-aufwand
(lambda (ls)
(letrec
([sort
(lambda (ls1 ls2)
(cond
[(null? ls1) ls2]
[(null? (cdr ls1))
(set! count (+ 1 count)) ;gib die einelementige Liste zurück
(cons (car ls1) ls2)]
[(> (car ls1) (cadr ls1))
(set! count (+ 1 count)) ;vertausche das n-te Paar und gehe nach links (bzw. nach rechts)
(if (null? ls2)
(sort (cons (car ls1) (cddr ls1)) (cons (cadr ls1) ls2))
(sort (cons (car ls2) (cons (cadr ls1) (cons (car ls1) (cddr ls1)))) (cdr ls2)))]
[else
(set! count (+ 1 count)) ;gehe nach rechts
(sort (cdr ls1) (cons (car ls1) ls2))]))])
(reverse (sort ls ())))))
(define gnomesort-ausgabe
(lambda (min max anzahl)
(let ([ls (zufallsliste min max anzahl)])
(set! count 0)
(display "Ungeordnete Zufallszahlen:")
(display ls)
(display "Geordnete Zufallszahlen:")
(display (gnomesort-aufwand ls))
(display "Anzahl der Vertauschungen bzw. Bewegungen: " (number->string count))
'ok)))
</code>
<run id="4e75c1edaeef5">
(gnomesort-ausgabe 1 1000 20)
</run>
Im Weiteren wollen wir uns nur auf die Zählergebnisse unseres "Zeittaktmessers" konzentrieren.<br />
Dazu sollen die Wiederholungen des Experimentes automatisiert werden:
<code id="5bb87059243c6">
(define gnomesort-mehrfach
(lambda (min max anzahl whlg)
(letrec
([summe
(lambda (n)
(if (= n 0)
0
(begin
(set! count 0)
(gnomesort-aufwand (zufallsliste min max anzahl))
(+ count (summe (- n 1))))))])
(/ (summe whlg) whlg))))
</code>
<run id="5bb87059244e6">
(gnomesort-mehrfach 1 1000 20 10)
</run>
Schließlich sollen die Ergebnisse unserer empirischen Untersuchung wieder im Balkendiagramm visualisiert werden.
<code id="4e75c1edaece3">
(define experiment
(lambda (min max anzahl schrittweite whlg)
(if (< anzahl 1)
()
(append (experiment min max (- anzahl schrittweite) schrittweite whlg)
(list (gnomesort-mehrfach min max anzahl whlg))))))
</code>
'''Achtung!''' Mit kleinen Wiederholraten und etwas Geduld experimentieren!
<canvas w="400" h="300"></canvas>
<run id="5bb870592455f">
(balkendiagramm (experiment 1 1000 20 1 10) 3)
</run>
Die empirischen Untersuchungen zeigen im Mittel offensichtlich einen ''quadratischen Zeitaufwand'' von GnomeSort.<br />
Es gilt:
<table border="0" cellspace="0" cellpadding="4">
<tr valign="top">
<td rowspan="2"><b>average case: </b></td>
<td>$T(n) = \frac{1}{2} \cdot n^2$ bzw.</td>
</tr>
<tr>
<td>$T(n) = \mathcal{O}(n^2)$</td>
</tr>
</table>
=== Best- und Worst-Case-Experimente ===
Zur Untersuchung dieser Spezialfälle wollen wir die beiden Prozeduren <tt>gnomesort-mehrfach</tt> und <tt>experiment</tt> ''variabelstellig'' erweitern. ''Zusätzlich'' können nun beliebig viele Prozeduren übergeben, die sich auf Listen anwenden lassen. Damit kann beispielsweise die zufällige Zahlenliste "vorsortiert" oder vor dem Sortiervorgang ungekehrt werden:
<code id="5bb8705924449">
(define gnomesort-spezial
(lambda (min max anzahl whlg . proz-ls)
(letrec
([anwenden
(lambda (zuf-ls proz-ls)
(if (null? proz-ls)
zuf-ls
(apply (car proz-ls) (list (anwenden zuf-ls (cdr proz-ls))))))]
[summe
(lambda (n)
(if (= n 0)
0
(begin
(set! count 0)
(gnomesort-aufwand (anwenden (zufallsliste min max anzahl) proz-ls))
(+ count (summe (- n 1))))))])
(/ (summe whlg) whlg))))
(define experiment-spezial
(lambda (min max anzahl schrittweite whlg . proz-ls)
(if (< anzahl 1)
()
(append (apply experiment-spezial min max (- anzahl schrittweite) schrittweite whlg proz-ls)
(list (apply gnomesort-spezial min max anzahl whlg proz-ls))))))
</code>
<table border="0" cellpadding="0" cellspacing="0">
<tr>
<td align="center">
'''GnomeSort: best-case'''
<canvas w="400" h="300"></canvas>
</td>
<td> </td>
<td align="center">
'''GnomeSort: worst-case'''
<canvas w="400" h="300"></canvas>
</td>
</tr>
</table>
<run id="5bb87059245d1">
(balkendiagramm (experiment-spezial 1 1000 20 1 1 gnomesort) 4)
(balkendiagramm (experiment-spezial 1 1000 20 1 1 reverse gnomesort) 5)
</run>
Für die beiden Spezialfälle gilt:
<table border="0" cellspace="0" cellpadding="4">
<tr valign="top">
<td rowspan="2"><b>best case: </b></td>
<td>$T(n) = n$ bzw.</td>
</tr>
<tr>
<td>$T(n) = \mathcal{O}(n)$</td>
</tr>
<tr valign="top">
<td rowspan="2"><b>worst case: </b></td>
<td>$T(n) = (n-1)^2 + 1$ bzw.</td>
</tr>
<tr>
<td>$T(n) = \mathcal{O}(n^2)$</td>
</tr>
</table>
Die Effizienz von GnomeSort verbessert sich also, wenn schon eine gewisse Ordnung ("Vorsortierung") vorliegt.<br />
Im ungünstigsten Fall ist GnomeSort etwas uneffizienter als MinSort.<br />
Zurück zu [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/MinSort|MinSort]].