BubbleSort

Aus ProgrammingWiki

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

Inhaltsverzeichnis 1 Voraussetzungen 2 Modifizierte Maximumsuche 3 BubbleSort-Algorithmus 4 Aufwandsbetrachtungen 4.1 Empirische Untersuchungen 4.2 Theoretische Untersuchungen 4.3 Grafische Auswertung 5 Zum Weiterarbeiten 5.1 GnomeSort

Voraussetzungen

Mit der Datenstruktur Feld haben wir bereits eine große Anzahl von Zufallszahlen generiert und ausgegeben.
Dazu wurde die Funkion zufallszahl implementiert:

function zufallszahl(von, bis) { return Math.floor(Math.random() * (bis - von + 1) + von); }

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:

var newFeld = erzeugen(-50, 100, 100);

ausgabe(newFeld);

ausführen

Modifizierte Maximumsuche

Zunächst wollen wir die sequenzielle Suche nach dem größten Feldelement eines numerischen Datenfeldes modifizieren.
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.

function maxElement(feld) { // -- weitere Anweisungen -- return feld[feld.length - 1]; }

var newFeld = erzeugen(-50, 100, 100); ausgabe(newFeld); console.log("Das größte Element im Datenfeld ist " + maxElement(newFeld) + ".");

ausführen

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.
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.
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.

function BubbleSort(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 = 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; }

Ungeordnete Zufallszahlen:

Geordnete Zufallszahlen:

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

ausführen

Aufwandsbetrachtungen

Empirische Untersuchungen

Wie wirken sich große Datenmengen auf die Dauer des Sotiervorgangs aus?
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.
Diese Zeittakte sollen in Abhängigkeit der Anzahl der zu sortierenden Feldelemente ermittelt werden.

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

sortAufwand(-50, 100, 1000);

ausführen

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

function sortMittel(von, bis, anz, whlg) { var sum = 0; // -- weitere Anweisungen -- return Math.round(sum / whlg); }

sortMittel(-50, 100, 1000, 100);

ausführen

Theoretische Untersuchungen

Wir überlegen uns zunächst, wie viele Vergleiche der Feldelemente insgesamt durchgeführt werden:

Das Schema lässt sich mit einer Dreieckfläche vergleichen. Damit sind also $\tfrac{n}{2} (n-1)$ Vergleiche notwendig.
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.
Damit ist folgende Abschätzung für den Gesamtaufwand $T(n)$ möglich:

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

$T(n) \approx \frac{3}{4} \cdot n^2$   bzw.

$T(n) \sim n^2$

Das Sortieren mit dem BubbleSort-Algorithmus erfolgt mit quadratischem Zeitaufwand.

Grafische Auswertung

Um unsere theoretischen Betrachtungen zu bestätigen, wollen wir die 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

Zum Weiterarbeiten

GnomeSort

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.

Implementieren diesen Algorithmus.

Zur Problemlösung.