GnomeSort

Aus ProgrammingWiki

< Gymnasium Löbau < Vertiefungsklasse 2013

Archivierte Version vom 2019-01-20T15:23:01+00:00. Aktuelle Version

GnomeSort - los geht's!

Algorithmus

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:

Beginne links und vergleiche die beiden ersten Töpfe.
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 einen Schritt nach rechts.
Gehe auch in jedem anderen Fall einen Schritt nach rechts.
Wiederhole diesen Vergleich benachbarter Töpfe bis zum letzten Blumentopf.

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

function zufallszahl(von, bis) {
 return Math.floor(Math.random() * (bis - von + 1) + von);
}

function erzeugen(von, bis, anz) {
 var feld = new Array();
 for (var i = 0; i < anz; i++)
  feld[i] = zufallszahl(von, bis);
 return feld;
}

Auf die explizite Ausgabe unsortierter bzw. sortierter Datenfelder wollen wir im Weiteren verzichten. Uns soll die Visualisierung im Balkendiagramm genügen.

function GnomeSort(feld) {
 // -- weitere Anweisungen --
 return feld; 
}

Ungeordnete Zufallszahlen:

Geordnete Zufallszahlen:

var newFeld = erzeugen(-50, 100, 100);
BalkenDiagramm(canvas1, turtle1, newFeld);

var sortFeld = GnomeSort(newFeld);
BalkenDiagramm(canvas2, turtle2, sortFeld);

Aufwandsbetrachtungen

Empirische Untersuchungen

Wir wollen hier stark vereinfacht annehmen, dass jeder Vergleich zweier benachbarter Feldelemente, ihr möglicher Tausch sowie das Weiterrücken nach links bzw. rechts je einem Zeittakt entsprechen.
Diese Zeittakte werden wieder in Abhängigkeit der Anzahl der zu sortierenden Feldelemente ermittelt.

function sortAufwand(von, bis, anz) {
 var feld = erzeugen(von, bis, anz);
 var count = 0, i = 0;
 while (i < feld.length - 1) {
  count++;
  if (feld[i] > feld[i + 1]) {
   count++;
   var temp = feld[i]; feld[i] = feld[i + 1]; feld[i + 1] = temp;
   count++;
   if (i > 0) i--; else i++;
  }
  else
   i++;  
 }
 return count;  
}

sortAufwand(-50, 100, 1000);

Auch hier soll der Mittelwert aus Mehrfachanwendungen der Funktion sortAufwand ermittelt werden:

function sortMittel(von, bis, anz, whlg) {
 var sum = 0;
 // -- weitere Anweisungen --
 return Math.round(sum / whlg);
}

sortMittel(-50, 100, 1000, 100);

Zurück zu BubbleSort.

GnomeSort

Algorithmus

Aufwandsbetrachtungen

Empirische Untersuchungen

Suche