Gymnasium Löbau/Vertiefungsklasse 2013/GnomeSort

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
<code id="5c4347f74789f" hidden>
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);
}
</code>

[[Datei:Gartenzwerg_Blumentopf1.JPG|miniatur|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:<br />

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

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

<code id="5c4349f32f877">
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;
}
</code>

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

<code id="5c4347f747983">
function GnomeSort(feld) {
 // -- weitere Anweisungen --
 return feld; 
}
</code>

<code id="5c4347f7479e7" hidden>
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;
}
</code>

<check execute="(sortTest(-50, 100, 10, 100));">
true
</check>

<table border="0" cellpadding="0" cellspacing="0">
<tr>
<td align="center">
'''Ungeordnete Zufallszahlen:'''
<canvas w="400" h="300"></canvas>
</td>
<td>&nbsp;</td>
<td align="center">
'''Geordnete Zufallszahlen:'''
<canvas w="400" h="300"></canvas>
</td>
</tr>
</table>

<run id="5c4347f747a5a">
var newFeld = erzeugen(-50, 100, 100);
BalkenDiagramm(canvas1, turtle1, newFeld);

var sortFeld = GnomeSort(newFeld);
BalkenDiagramm(canvas2, turtle2, sortFeld);
</run>

== 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.<br />
Diese Zeittakte werden wieder in Abhängigkeit der Anzahl der zu sortierenden Feldelemente ermittelt.

<code id="5c45c502d7037">
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;  
}
</code>

<run id="5c44925578245">
sortAufwand(-50, 100, 1000);
</run>

Auch hier soll der Mittelwert aus Mehrfachanwendungen der Funktion <tt>sortAufwand</tt> ermittelt werden:

<code id="5c449255781b4">
function sortMittel(von, bis, anz, whlg) {
 var sum = 0;
 // -- weitere Anweisungen --
 return Math.round(sum / whlg);
}
</code>

<run id="5c449255782b1">
sortMittel(-50, 100, 1000, 100);
</run>

=== Grafische Auswertung ===

Wir wollen diese empirischen Ergebnise visualisieren.

<code id="5c4493ef4a682">
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;
}
</code>

<canvas w="400" h="300"></canvas>

<run id="5c4493ef4a74b">
var expFeld = experiment(-50, 100, 1000, 50, 10);
BalkenDiagramm(canvas3, turtle3, expFeld);
</run>

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

<code id="5c44cf069fd89">
var aufstFeld = GnomeSort(erzeugen(-50, 100, 100));
var abstFeld = GnomeSort(erzeugen(-50, 100, 100)).reverse();
</code>

Zur Gegenüberstellung nutzen wir die modifizierte Funktion <tt>experiment</tt>:

 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.

<code id="5c45c502d711c" hidden>
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;
}
</code>

<table border="0" cellpadding="0" cellspacing="0">
<tr>
<td align="center">
'''GnomeSort: best-case'''
<canvas w="400" h="300"></canvas>
</td>
<td>&nbsp;</td>
<td align="center">
'''GnomeSort: worst-case'''
<canvas w="400" h="300"></canvas>
</td>
</tr>
</table>

<run id="5c44cf069fe41">
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);
</run>

Interpretiere die Ergebnise und die beiden Diagramme!

Zurück zu [[Gymnasium Löbau/Vertiefungsklasse 2013/BubbleSort|BubbleSort]].