Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


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(n2).

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:

BubbleII

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



zur Startseite
© Tino Hempel 1997 - 2007 Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.

Für alle Seiten gilt der 
Haftungsausschluss/Disclaimer.