BubbleSort

Voraussetzungen

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

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:

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.

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.