GnomeSort

Aus ProgrammingWiki

< Gymnasium Löbau < Vertiefungsklasse 2013

Archivierte Version vom 2019-01-19T16:01:55+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);

Zurück zu BubbleSort.

GnomeSort

Algorithmus

Suche