Bubblesort

Bubblesort ist ein Sortieralgorithmus und arbeitet wie folgt:

Gegeben: Liste A der Länge n.

• Falls n < 2: A ist sortiert, brich ab. Ansonsten…
• Wiederhole n-1 Mal:
  • Gehe von A[0] bis A[n-2] durch
  • Betrachte jeweils ein Element und seinen rechten Nachbarn (also A[i] und A[i+1])
  • Falls A[i] > A[i+1], vertausche die beiden
• Danach ist die Liste sortiert, gib die sortierte Liste als Ergebnis zurück

Laufzeit

Eine Liste mit $n$ Elementen muss $n-1$ Mal durchgegangen werden und bei jedem Durchgang werden $n-1$ Vergleiche angestellt. Insgesamt sind das $(n-1)^{2}$ Vergleiche. Damit bewegt sich die Laufzeit in ${\mathcal {O}}(n^{2})$.

Implementierung in Python

def swap(A,i,j):
    temp = A[i]
    A[i] = A[j]
    A[j] = temp

def bubblesort(A):
    for n in range(len(A)):
        for i in range(len(A)-1):
            if A[i] > A[i+1]:
                swap(A,i,i+1)
    return A

Weblinks

• Sortieralgorithmen auf VisuAlgo.net 🇬🇧 🇨🇳 🇮🇩
• Bubblesort getanzt 🇬🇧

Sortieralgorithmen

Bubblesort | Selectionsort | Insertionsort | Quicksort | Mergesort | Gnomesort