Bubblesort

Kurz: Bubblesort sortiert, indem es benachbarte Elemente vergleicht und vertauscht, wenn sie in falscher Reihenfolge stehen – größere Werte „blubbern“ nach hinten. Es ist einfach, aber mit O(n²) langsam.

Genauer: In jedem Durchlauf wandert das größte noch nicht einsortierte Element ans Ende. Nach n−1 Durchläufen ist die Liste sortiert. Bubblesort eignet sich zum Lernen, nicht für den Einsatz bei großen Datenmengen.

Im Detail

def bubblesort(liste):
    n = len(liste)
    for i in range(n - 1):
        getauscht = False
        for j in range(n - 1 - i):
            if liste[j] > liste[j + 1]:
                liste[j], liste[j + 1] = liste[j + 1], liste[j]
                getauscht = True
        if not getauscht:        # schon sortiert: abbrechen
            break
    return liste
 
print(bubblesort([5, 1, 4, 2, 8]))   # [1, 2, 4, 5, 8]

Ablauf

[5, 1, 4, 2, 8] → 1. Durchlauf: [1, 4, 2, 5, 8] → 2. Durchlauf: [1, 2, 4, 5, 8] → 3. Durchlauf ohne Tausch: fertig.

Eigenschaften

Merkmal	Wert
Laufzeit (schlechtester/Durchschnitt)	O(n²)
Laufzeit (bereits sortiert, mit Abbruch)	O(n)
Zusatzspeicher	O(1) (in-place)
Stabil	ja (gleiche Elemente behalten ihre Reihenfolge)

Schnellere Verfahren sind Quicksort und Mergesort mit durchschnittlich O(n log n). In der Praxis nutzt man die eingebaute Sortierfunktion der Sprache (siehe Sortieren und fortgeschrittene Sortierverfahren).

Siehe auch: Sortieren, Quicksort, Mergesort, Big-O-Notation