MinSort

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2010-10-07T10:09:38+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Algorithmus
2 Effizienz von MinSort
- 2.1 Theoretische Analyse des Zeitaufwands
- 2.2 Experimente zum Zeitaufwand
3 Aufgaben

;-- 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)   ; stellt current-time usw. bereit

(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 canvas turtle)
    (let* ([breite (/ maxbreite (length ls))] 
           [extremwerte (minmax ls)]
           [min (car extremwerte)] [max (cdr extremwerte)])
      (letrec
          ([zeichnen
            (lambda (min max ls)
              (if (null? ls)
                  'ok
                  (begin
                    (balken (* (/ (car ls) (- max min)) maxhoehe) 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)))))

Algorithmus

Bei einfachen rekursiven Problemlösungen haben wir Algorithmen implementiert, die der Suche des Minimums bzw. dem Streichen eines Elements in 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.
Implementieren Sie den Algorithmus und testen Sie ihn an Listen mit Zufallszahlen z, mit z \in \mathbb{Z}.
Stellen Sie dazu die ungeordnete und die geordnete Zahlenliste jeweils in einem Balkendiagramm grafisch dar.

(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)
    ...))

Ungeordnete Zufallszahlen:

Geordnete Zufallszahlen:

<eval id="4be1586d291d6"> (define ls (zufallsliste 1 1000 100)) (balkendiagramm ls canvas1 turtle1) (define ls-sort (minsort ls)) (balkendiagramm ls-sort canvas2 turtle2) </eval>

Hinweis: Um mehrere Zeichenflächen nutzen zu können, muss die Prozedur balkendiagramm syntaktisch erweitert werden:

(balkendiagramm
  <ls>       ;Liste mit Zahlenwerten   
  <canvas>   ;Zeichenfläche
  <turtle>)  ;Turtle (Zeichenroboter)

Effizienz von MinSort

Theoretische Analyse des Zeitaufwands

Wir überlegen uns zunächst, wie viele Vergleiche bei der Minimumsuche insgesamt durchgeführt werden:

Das Schema lässt sich mit einer Dreieckfläche vergleichen. Damit sind also \tfrac{n}{2} (n-1) Vergleiche zum Auffinden des Minimums notwendig.
Zum Streichen des gefundenen Minimums sind ähnliche Überlegungen möglich. Im Mittel kann man aber davon ausgehen, dass das Streichen nach \tfrac{n}{2} Vergleichen pro Durchlauf abgeschlossen ist (endständig rekursive Prozedur).
Damit ist folgende Abschätzung für den Gesamtaufwand möglich:

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)

T(n) \approx \frac{3}{4} \cdot n^2 bzw.

T(n) = \mathcal{O}(n^2)

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:

(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:") (newline)
      (display ls) (newline)
      (display "Geordnete Zufallszahlen:") (newline)
      (display (minsort-aufwand ls)) (newline)
      (display "Anzahl der Minimumvergleiche und Streichungen: ") (display count) (newline)
      'ok)))

<eval id="4be330b1c9ba7"> (minsort-ausgabe 1 1000 20) </eval>

Im Weiteren wollen wir uns wieder nur auf die Zählergebnisse unseres "Zeittaktmessers" konzentrieren.
Dazu sollen die Wiederholungen des Experimentes automatisiert werden:

(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))))))])     
      (exact->inexact (/ (summe whlg) whlg)))))

<eval id="4be330b1cab47"> (minsort-mehrfach 1 1000 20 100) </eval>

Schließlich sollen die Ergebnisse unserer empirischen Untersuchung wieder im Balkendiagramm visualisiert werden.

(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))))))

Achtung! Mit kleinen Wiederholraten und etwas Geduld experimentieren!

<eval id="4be330b1cbae6"> (balkendiagramm (experiment 1 1000 200 5 10) canvas3 turtle3) </eval>

Die empirischen Untersuchungen bestätigen den quadratischen Zeitaufwand von MinSort.

Aufgaben

Ermitteln Sie mit der Prozedur minsort-mehrfach empirisch die Zeitaufwandsfunktion T:\mathbb{N} \rightarrow \mathbb{R}^+.
Nutzen Sie dazu eine Tabellenkalkulation oder den grafikfähigen Taschenrechner. Bestimmen Sie die Funktionsgleichung T(n) = f(n) durch quadratische Regression und vergleichen Sie diese mit den oben angeführten theoretischen Überlegungen.
Implementieren Sie unter DrScheme den MinSort-Algorithmus zum lexikografischen Ordnen von Zeichenketten.
Dabei soll wahlweise aufsteigend oder absteigend geordnet werden können (Prozeduren höherer Ordnung!).