Gymnasium Löbau/Vertiefungsklasse 2013/BubbleSort

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
<code id="5c3afcce647d8" hidden>
function erzeugen(von, bis, anz) {
 var feld = new Array();
 for (var i = 0; i < anz; i++)
  feld[i] = zufallszahl(von, bis);
 return feld;
}

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>

== Voraussetzungen ==

Mit der [[Gymnasium_Löbau/Vertiefungsklasse_2013/Die_Datenstruktur_Feld|Datenstruktur Feld]] haben wir bereits eine große Anzahl von Zufallszahlen generiert und ausgegeben.<br />
Dazu wurde die Funkion <tt>zufallszahl</tt> implementiert:

<code id="5c3afcce6485a">
function zufallszahl(von, bis) {
 return Math.floor(Math.random() * (bis - von + 1) + von);
}
</code>

Weiterhin halten wir die bekannten Funktionen zum Erzeugen bzw. Ausgeben eines zufälligen Datenfeldes bereit:

 function erzeugen(von, bis, anz)
 function ausgabe(feld)

Wir testen zunächst die Generierung und Ausgabe eines umfangreichen Datenfeldes mit Zufallszahlen:

<code id="5c3b042da584c">
var newFeld = erzeugen(-50, 100, 100);
</code>

<run id="5c3b042da5a10">
ausgabe(newFeld);
</run>

== Modifizierte Maximumsuche ==

Zunächst wollen wir die sequenzielle Suche nach dem größten Feldelement eines numerischen Datenfeldes modifizieren.<br />
Wir benutzen dazu den folgenden Algorithmus:

* Vergleiche die beiden ersten Feldelemente.
* Steht das größere Element vor dem kleineren, so vertausche die Positionen beider Elemente.
* Verfahre derart mit allen weiteren benachbarten Feldelementen.
* Gib das letzte Feldelement zurück - es ist das größte Element des Datenfeldes.

Implementiere diesen Algorithmus.

<code id="5c3b042da58f3">
function maxElement(feld) {
 // -- weitere Anweisungen --
 return feld[feld.length - 1];
}
</code>

<check execute="(maxElement([23, 5, 67, 17, 88, 17]) == 88) && (maxElement([-23, -5, -67, -17, -88, -17]) == -5) && (maxElement([0]) == 0);">
true
</check>

<run id="5c3b136a2bb1b">
var newFeld = erzeugen(-50, 100, 100);
ausgabe(newFeld);
console.log("Das größte Element im Datenfeld ist " + maxElement(newFeld) + ".");
</run>

== BubbleSort-Algorithmus ==

Wir stellen uns nun vor, dass unser Datenfeld der modifizierten Maximumsuche unterzogen und anschließend das letzte Feldelement gedanklich abgetrennt wird. Eine erneute Anwendung der Maximumsuche auf das Restfeld führt dazu, dass das zweitgrößte Element an vorletzter Stelle steht.<br /> 
Wir erkennen: Die Mehrfachanwendung der modifizierten Maximumsuche auf ein Datenfeld, dessen größter Feldindex schrittweise dekrementiert (zurükgesetzt) wird, führt zum Sortieren des gesamten Datenfeldes.<br />
Jedes Teil-Maximum rückt dabei schrittweise, ähnlich einer Luftblase, die in einem Sumpf aufsteigt, an seine korrekte Stelle. Wir nennen deshalb diesen Sotieralgorithmus ''BubbleSort''.

<code id="5c3b136a2ba73">
function BubbleSort(feld) {
 for (var j = feld.length - 1; j > 1; j--)
  for (var i = 0; i < j; i++)
   if (feld[i] > feld[i + 1]) {
    var h = feld[i]; feld[i] = feld[i + 1]; feld[i + 1] = h;
   }
 return feld; 
}
</code>

<run id="5c3b136a2bb9f">
var newFeld = erzeugen(-50, 100, 100);
console.log("Unsortiertes Datenfeld:");
ausgabe(newFeld);
console.log("Sortiertes Datenfeld:");
ausgabe(BubbleSort(newFeld));
</run>