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="5c44925578120">
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;  
}
</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>

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