Informatikmaterialien
von Tino Hempel

	Richard-Wossidlo-Gymnasium Ribnitz-Damgarten Fachbereich Informatik

BubbleSort

Sortierverfahren II – Bubblesort

Prinzip des Verfahrens

Beim Durchlaufen des Feldes werden die jeweiligen Nachbarelemente miteinander verglichen und ggf. ausgetauscht. Am Ende des ersten Laufs befindet sich das größte Element am Feldende. Dieser Vorgang wird nun erneut gestartet, allerdings diesmal ohne das letzte Element. Danach hat man das zweitgrößte Element gefunden. Der ganze Vorgang wird nun so oft wiederholt, bis das gesamte Feld sortiert ist.

Der Name des Verfahrens beschreibt damit anschaulich den Vorgang. Die größten Elemente steigen wie Luftblasen im Wasser nach oben.

Darstellung des Algorithmus als Struktogramm

worst-case-Komplexität

Die Berechnung der Zeitkomplexität erfolgt in Analogie zu der von Rippelsort. Bubblesort hat also die Zeitkomplexität O(n²).

Verbesserung

Der obige Algorithmus arbeitet stur. Ist das Feld nach dem ersten Tausch etwa schon sortiert, so geht der Algorithmus trotzdem das gesamte Feld durch. Hier kann die Einführung eines Merkers für den Tauschvorgang sinnvoll sein. Der Algorithmus lässt sich danach wie folgt schreiben:

Allerdings ändert diese Option nichts an der worst-case-Komplexität.

zur Startseite

Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.
Für alle Seiten gilt der

Haftungsausschluss/Disclaimer.