.:: Informationen zu Bubblesort ::.

Die Grundidee des Verfahrens ist es, die unsortiert vorliegenden Daten dadurch zu sortieren,
daß immer zwei benachbarte Elemente verglichen und ggf. vertauscht werden.
Durch dieses Vorgehen werden also zunächst die Positionen 0 und 1 verglichen,
anschließend die Positionen 1 und 2 usw.
Durch die Vertauschung wird dabei das soeben vertauschte, größere Element direkt in den
nächsten Vergleich einbezogen, so daß ein relativ großes Element in einem Durchlauf recht weit
nach hinten wandern kann.

Bei überwiegend sortierten Daten ist Bubble Sort daher relativ günstig - für sortierte Daten
beträgt die Komplexität O(n). In allen anderen Fällen liegt die Komplexität aber bei
O(n2) und damit deutlich höher als bei vielen anderen Sortierverfahren, etwa Heapsort
oder Quicksort.

Um unnötige Durchläufe zu vermeiden, wird in einer boole'schen Variablen vermerkt, ob es im
aktuellen Durchlauf zu einer Vertauschung kam. War dies nicht der Fall, bricht das
Verfahren ab.
Bei überwiegend sortierten Daten ist Bubble Sort daher relativ günstig - für sortierte Daten
beträgt die Komplexität O(n). In allen anderen Fällen liegt die Komplexität aber bei
O(n²) und damit deutlich höher als bei vielen anderen Sortierverfahren, etwa Heapsort
oder Quicksort.

Daher ist Bubblesort trotz seiner Beliebtheit in der Lehre kein gutes Sortierverfahren.

Spezialfall: Bei fast sortierten Feldern kann man mit "Bubblesort mit Merker" ein viel besseres
Ergebnis als sogar mit Quicksort erreichen. Das ist aber auch nur möglich wenn im Feld nur
ganz wenig Elemente nicht sortiert sind. Siehe: Tabelle
.: Zurück zum Menü