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ü