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="5c3b5cca7e460">
function BubbleSort(feld) {
 // -- weitere Anweisungen --
 return feld; 
}
</code>

<code id="5c3b5cca7e4e8" 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 = BubbleSort(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="5c3b5cca7e57d">
var newFeld = erzeugen(-50, 100, 100);
BalkenDiagramm(canvas1, turtle1, newFeld);
console.log("Unsortiertes Datenfeld:");
ausgabe(newFeld);

var sortFeld = BubbleSort(newFeld);
BalkenDiagramm(canvas2, turtle2, sortFeld);
console.log("Sortiertes Datenfeld:");
ausgabe(sortFeld);
</run>

== Aufwandsbetrachtungen ==

=== Empirische Untersuchungen ===

Wie wirken sich große Datenmengen auf die Dauer des Sotiervorgangs aus?<br />
Wir wollen den sogenannten ''Zeitaufwand'' des BubbleSort-Algorithmus untersuchen. Dazu soll stark vereinfacht angenommen werden, dass jeder Vergleich zweier benachbarter Feldelemente sowie der mögliche Tausch dieser Feldelemente je einem Zeittakt entsprechen.<br />
Diese Zeittakte sollen in Abhängigkeit der Anzahl der zu sortierenden Feldelemente ermittelt werden.

<code id="5c3b932b33005">
function sortAufwand(von, bis, anz) {
 var feld = erzeugen(von, bis, anz);
 var count = 0;
 for (var j = feld.length - 1; j > 0; j--)
  for (var i = 0; i < j; i++) {
   count++;
   if (feld[i] > feld[i + 1]) {
    count++;
    var h = feld[i]; feld[i] = feld[i + 1]; feld[i + 1] = h;
   }
  }
 return count;  
}
</code>

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

Wegen der beträchlichen Streuung der Zählergebnisse soll der Mittelwert aus Mehrfachanwendungen der Funktion <tt>sortAufwand</tt> ermittelt werden. Vervollständige die entsprechende Funktion.

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

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

=== Theoretische Untersuchungen ===

Wir überlegen uns zunächst, wie viele Vergleiche der Feldelemente insgesamt durchgeführt werden:
<blockquote>[[Bild:BubbleSort-Schema1.gif]]</blockquote>
Das Schema lässt sich mit einer Dreieckfläche vergleichen. Damit sind also $\tfrac{n}{2} (n-1)$ Vergleiche notwendig.<br />
Zum Tauschen der Feldelemente sind ähnliche Überlegungen möglich. Im Mittel kann man aber davon ausgehen, dass das Tauschen nur bei der Hälfte aller Vergleiche notwendig ist.<br />
Damit ist folgende Abschätzung für den Gesamtaufwand $T(n)$ möglich:<br />

<blockquote>
$T(n) = \underbrace{\frac{n}{2} \cdot (n-1)}_{Vergleiche} + \underbrace{\frac{1}{2} \cdot \frac{n}{2} \cdot (n-1)}_{Vertauschungen} = \frac{3}{4} \cdot n \cdot (n-1)$<br /><br />
$T(n) \approx \frac{3}{4} \cdot n^2$ &nbsp; bzw.<br /><br />
$T(n) \sim n^2$
</blockquote>

Das BubbleSort erfolgt also mit ''quadratischem Zeitaufwand''.

=== Grafische Auswertung ===

Um unsere theoretischen Betrachtungen zu bestätigen, wollen wir die empirischen Ergebnise visualisieren.

<code id="5c3ba96b38273">
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="5c3ba96b38343">
var expFeld = experiment(-50, 100, 1000, 50, 100);
BalkenDiagramm(canvas3, turtle3, expFeld);
</run>