Einführung in den Bubble-Sort Algorithmus

Bubble-Sort-Algorithmus

Bubblesort ist der einfachste und gleich auch der älteste Sortieralgorithmus. Hier müssen einfach alle Elemente eines Arrays durchlaufen und miteinander verglichen werden. Wollen wir vom kleinsten zum größten Wert sortieren und ist ein Element größer als sein Nachfolger, werden diese Elemente getauscht. Damit ist Bubblesort ein stabiler, in-place Algorithmus.

Beim Bubblesort werden jeweils zwei aufeinanderfolgende Elemente miteinander verglichen und – wenn das linke Element größer ist als das rechte – werden diese vertauscht. Diese Vergleichs- und Tauschoperationen führt man von links nach rechts über alle Elemente durch, so dass nach dem ersten Durchlauf das größte Element ganz rechts positioniert ist. Diesen Prozess wiederholt man solange, bis es in einem Durchlauf zu keinem weiteren Vertauschen mehr kommt.

Die Laufzeitkomplexität beim Bubblesort ist im Best-Case O(n) und im Worst-Case O(n²), wobei n die Anzahl der zu sortierenden Elemente angibt.

Beispiel

Beispiel
Formel: ((Anzahl der Element n) x (Anzahl der Iterationen)) x 1/2

Vereinfacht: 1/2 x (n² - n)

Werte einsetzen: 1/2 x (7² - 7) = 1/2 x (49 - 7) = 1/2 x (42) = 21

Im obigen Beispiel sind 21 Vergleiche/Tausche notwendig, um die Zahlenreihe einmal umgekehrt aufsteigend zu sortieren.

Lernvideo zum Bubblesort
Lernvideo

Hinweis: Alle Ergebnisse und Zwischenergebnisse müssen in Moodle abgegeben werden.