GnomeSort

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

GnomeSort - los geht's!

Inhaltsverzeichnis

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:

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

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

Da keine Indizierung der Listenelemente möglich ist, wird der Algorithmus mit den beiden Listen ls1 und ls2 implementiert. Die Liste ls1 enthält die unsortierte Zahlenliste. Mit ls2 wird die sortierte Zahlenlise gebildet. Beim Schritt nach rechts wird das erste Listenelement von ls1 der Liste ls2 vorangestellt. Analog wird beim Schritt nach links das erste Listenelement von ls2 zurückgenommen und ls1 vorangestellt. Zum Schluss muss die sortierte Liste (d.h. ls2) umgekehrt werden:

 

Quelltext überprüfen:

Ungeordnete Zufallszahlen:

 

Geordnete Zufallszahlen:

Hinweis: Syntax der Prozedur balkendiagramm:

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

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

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

Achtung! Mit kleinen Wiederholraten und etwas Geduld experimentieren!

Die empirischen Untersuchungen zeigen im Mittel offensichtlich einen quadratischen Zeitaufwand von GnomeSort.
Es gilt:

average case:   $T(n) = \frac{1}{2} \cdot n^2$   bzw.
$T(n) = \mathcal{O}(n^2)$

Best- und Worst-Case-Experimente

Zur Untersuchung dieser Spezialfälle wollen wir die beiden Prozeduren gnomesort-mehrfach und experiment 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:

GnomeSort: best-case

 

GnomeSort: worst-case

Für die beiden Spezialfälle gilt:

best case:   $T(n) = n$   bzw.
$T(n) = \mathcal{O}(n)$
worst case:   $T(n) = (n-1)^2 + 1$   bzw.
$T(n) = \mathcal{O}(n^2)$

Die Effizienz von GnomeSort verbessert sich also, wenn schon eine gewisse Ordnung ("Vorsortierung") vorliegt.
Im ungünstigsten Fall ist GnomeSort etwas uneffizienter als MinSort.

Zurück zu MinSort.

Persönliche Werkzeuge