GnomSort

Aus ProgrammingWiki

Archivierte Version vom 2011-04-28T21:19:28+00:00. Aktuelle Version

Algorithmus

Gartenzwerge sortieren die in einer Reihe aufgestellten Blumentöpfe der Größe nach und benutzen dazu den folgenden Algorithmus:

Beginne links und vergleiche die beiden ersten Töpfe.
Stehen sie in der richtigen Reihenfolge gehe ein Schritt nach rechts.
Vertausche die beiden Töpfe, wenn sie nicht in der korrekten Reihenfolge stehen, und gehe einen Schritt nach links. Ist der Schritt nach links nicht möglich, bleibe beim ersten Topf stehen.
Wiederhole das Sortieren bis zum letzten Blumentopf.

Die Größe der Blumentöpfe wird mit Zufallszahlen festgelegt:

(define zufallszahl
  (lambda (min max)
    (+ (randomint (- max min -1)) min)))

(define zufallsliste
  (lambda (min max anzahl)
   (if (= anzahl 0)
        ()
        (cons (zufallszahl min max) (zufallsliste min max (- anzahl 1))))))

;GnomSort
(define gnomsort
  (lambda (ls)
    (letrec
        ([sort
          (lambda (ls1 ls2)
            ...])
      (reverse (sort ls ())))))

Ungeordnete Zufallszahlen:

Geordnete Zufallszahlen:

(define ls (zufallsliste 1 1000 100))
(balkendiagramm ls 1)
(define ls-sort (gnomsort ls))
(balkendiagramm ls-sort 2)

Hinweis: Um mehrere Zeichenflächen nutzen zu können, muss die Prozedur balkendiagramm mit einem zusätzlichen Parameter ausgestattet werden, der einer fortlaufenden Nummerierung entspricht:

(balkendiagramm
  <ls>       ; Liste mit Zahlenwerten   
  <nr>)      ; fortlaufende Nummerierung des Balkendiagramms

Effizienz von GnomSort

Wir definieren unseren GnomSort-Algorithmus mit einem "eingebauten" (Zeittakt-)Zähler:

(define count 0)

(define gnomsort-aufwand
  (lambda (ls)
    (letrec
        ([sort
          (lambda (ls1 ls2)
            (cond
              [(null? ls1) ls2]
              [(null? (cdr ls1)) (cons (car ls1) ls2)]
              [(> (car ls1) (cadr ls1))
               (set! count (+ 1 count)) ;vertausche das aktuelle Paar und gehe nach links
               (if (null? ls2)
                   (sort (cons (cadr ls1) (cons (car ls1) (cddr 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 gnomsort-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 (gnomsort-aufwand ls)) (newline)
      (display "Anzahl der Minimumvergleiche und Streichungen: ") (display count) (newline)
      'ok)))

(gnomsort-ausgabe 1 1000 20)

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

(define gnomsort-mehrfach
  (lambda (min max anzahl whlg)
    (letrec 
        ([summe
          (lambda (n)           
            (if (= n 0)
                0
                (begin
                  (set! count 0)
                  (gnomsort-aufwand (zufallsliste min max anzahl))
                  (+ count (summe (- n 1))))))])     
      (exact->inexact (/ (summe whlg) whlg)))))

(gnomsort-mehrfach 1 1000 20 100)

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 (gnomsort-mehrfach min max anzahl whlg))))))

Achtung! Mit kleinen Wiederholraten und etwas Geduld experimentieren!

(balkendiagramm (experiment 1 1000 200 5 10) 3)

Die empirischen Untersuchungen zeigen offensichtlich einen quadratischen Zeitaufwand von GnomSort.

GnomSort

Algorithmus

Effizienz von GnomSort

Suche