Bubblesort

Einfache Sprache

Bubblesort ist ein Sortierverfahren bei dem immer direkte Nachbarn verglichen und ggf. getauscht werden.

Idee Bubblesort

Laufe über das Feld und prüfe bei jedem Schritt ob die das Element und das nächste in der richtigen Reihenfolge sind, wenn nicht tausche sie. Gehe immer ein Schritt weniger am Ende, da sich das jeweils Hinterste bereits “durchgetauscht” hat.

Algorithmus

1def bubblesort(A):
2    n = len(A)
3    for i in range(n-1):
4        for j in range(n-i-1):
5            if A[j] > A[j+1]:
6                t = A[j]
7                A[j] = A[j+1]
8                A[j+1] = t

Laufzeit

Die Laufzeit von Bubblesort ist $\mathcal O(n^2)$.