GnomeSort

Aus ProgrammingWiki

function ausgabe(feld) { var maxAnzahl = 25; var teilFeld = new Array(); var i = 0, j = 0; while (i < feld.length) { j = i + maxAnzahl; if (j < feld.length) teilFeld = feld.slice(i, j); else teilFeld = feld.slice(i, feld.length); console.log(teilFeld); i = j; } } var rand = 50; var maxBreite = 400 - 2 * rand; var maxHoehe = 300 - 2 * rand; function minMax(feld) { var ergebnis = new Array(0, 0); for (var i = 0; i < feld.length; i++) { if (ergebnis[0] > feld[i]) ergebnis[0] = feld[i]; if (ergebnis[1] < feld[i]) ergebnis[1] = feld[i]; } return ergebnis; } function balken(turtle, hoehe, breite) { turtle.forward(breite); turtle.left(90); turtle.forward(hoehe); turtle.left(90); turtle.forward(breite); turtle.left(90); turtle.forward(hoehe); turtle.left(90); turtle.forward(breite); } function BalkenDiagramm(canvas, turtle, feld) { var breite = maxBreite / feld.length; var extremWert = minMax(feld); var min = extremWert[0]; var max = extremWert[1]; canvas.clear(); turtle.hide(); turtle.move(rand, rand + max /(max - min) * maxHoehe); turtle.right(90); for (var i = 0; i < feld.length; i++) balken(turtle, feld[i] / (max - min) * maxHoehe, breite); }

Inhaltsverzeichnis 1 Algorithmus 2 Aufwandsbetrachtungen 2.1 Empirische Untersuchungen 2.2 Grafische Auswertung

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.
• 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; }

function gleich(feld1, feld2) { var test = (feld1.length == feld2.length); var i = 0; while (test && i < feld1.length - 1) { test = (feld1[i] == feld2[i]); i++ } return test; } function sortTest(von, bis, anz, n) { var i = 1; do { var feld1 = GnomeSort(erzeugen(von, bis, anz)); var feld2 = feld1.slice(); feld2.sort(function(a,b) {return a - b;}); var test = gleich(feld1, feld2); i++ } while (test && i < n); return test; }

Ungeordnete Zufallszahlen:

Geordnete Zufallszahlen:

var newFeld = erzeugen(-50, 100, 100); BalkenDiagramm(canvas1, turtle1, newFeld); var sortFeld = GnomeSort(newFeld); BalkenDiagramm(canvas2, turtle2, sortFeld);

ausführen

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; if (i > 0) i--; else i++; } else i++; count++; } return count; }

sortAufwand(-50, 100, 1000);

ausführen

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

ausführen

Grafische Auswertung

Wir wollen diese empirischen Ergebnise visualisieren.

function experiment(von, bis, anz, step, whlg) { var feld = new Array(); var s = step, i = 0; while (s < anz) { feld[i] = sortMittel(von, bis, s, whlg); s = s + step; i++; } return feld; }

var expFeld = experiment(-50, 100, 1000, 50, 10); BalkenDiagramm(canvas3, turtle3, expFeld);

ausführen

Interessant werden diese Aufwandsbetrachtungen, wenn das übergebene Datenfeld bereits aufsteigend sortiert (best-case-Fall) bzw. absteigend sortiert (worst-case-Fall) ist. Das Sortieren selbst soll natürlich mit unserem GnomeSort-Algorithmus erfolgen.

var aufstFeld = GnomeSort(erzeugen(-50, 100, 100)); var abstFeld = GnomeSort(erzeugen(-50, 100, 100)).reverse();

Zur Gegenüberstellung nutzen wir die modifizierten Funktionen sortAufwand und experiment:

function sortAufwand(feld) { 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; if (i > 0) i--; else i++; } else i++; count++; } return count; } function experiment(nr, von, bis, anz, step) { var feld = new Array(); var s = step, i = 0; while (s < anz) { if (nr == 1) var newFeld = GnomeSort(erzeugen(von, bis, s)); if (nr == 2) var newFeld = GnomeSort(erzeugen(von, bis, s)).reverse(); feld[i] = sortAufwand(newFeld); s = s + step; i++; } return feld; }

Für die Parameter der Funktion experiment gilt insbesondere:

function experiment(nr, von, bis, anz, step)
 nr   ... 1: aufsteigend sortiert / 2: absteigend sortiert
 von  ... kleinste Zufallszahl
 bis  ... größte Zufallszahl
 anz  ... Anzahl der Zufallszahlen
 step ... Schrittweite zum Variieren der Anzahl der Zufallszahlen

In den beiden Spezialfällen sind keine Wiederholungen notwendig.

GnomeSort: best-case

GnomeSort: worst-case

console.log("best-case-Aufwand: " + sortAufwand(aufstFeld)); var expAufstFeld = experiment(1, -50, 100, 1000, 50); BalkenDiagramm(canvas4, turtle4, expAufstFeld); console.log("worst-case-Aufwand: " + sortAufwand(abstFeld)); var expAbstFeld = experiment(2, -50, 100, 1000, 50); BalkenDiagramm(canvas5, turtle5, expAbstFeld);

ausführen

Aufgabe: Interpretiere die Ergebnisse und die beiden Diagramme.

Zurück zu BubbleSort.