UniProMax/Algorithmen/bubblesort

Bubblesort

Der intuitive Sortieralgorithmus: zwei verschachtelte Schleifen, größere Werte blubbern nach oben. Einfach zu erklären, in der Praxis aber zu langsam: O(n²).

3LerneinheitenVoraussetzungen:Big-O Notation

Relevant für:Informatik(Klausurniveau)Wirtschaftsinformatik(Grundlagen)Data Science(Grundlagen)

Sprache wählen

Sprache

Lerneinheit 1 von 3java + python

Bubblesort

Der intuitive Sortieralgorithmus. So einfach, dass Erstsemester ihn ohne nachzudenken hinschreiben können.

Die Idee

Geh durchs Array, vergleiche zwei benachbarte Elemente, tausche sie wenn sie in falscher Reihenfolge sind. Wiederhole bis nichts mehr getauscht wird.

Größere Elemente "blubbern" wie Luftblasen nach oben, daher der Name.

Implementierung

java// snippet

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

Java: klassischer swap über eine Hilfsvariable. Zwei verschachtelte Schleifen über n Elemente.

Komplexität

Zwei verschachtelte Schleifen über $n$ Elemente:

Fall	Vergleiche	Tauschungen
Worst Case (umgekehrt sortiert)	$\frac{n(n-1)}{2}$	$\frac{n(n-1)}{2}$
Average Case	$\sim \frac{n^2}{2}$	$\sim \frac{n^2}{4}$
Best Case (sortiert, mit Early-Exit)	$n-1$	$0$

→ O(n²) im Worst und Average Case.

Eigenschaften

✅ In-Place: braucht nur O(1) Zusatzspeicher
✅ Stabil: gleiche Werte behalten ihre relative Reihenfolge
❌ Lahm: bei großen Arrays unbrauchbar

Wann sinnvoll?

In der Praxis: fast nie. Bubblesort wird hauptsächlich als didaktisches Beispiel verwendet, weil er so einfach zu erklären ist. Selbst für sehr kleine Arrays nutzt man eher Insertion Sort (gleiches O(n²), aber in der Praxis ~2× schneller).

VorkenntnisBig-O Notation Baut darauf aufSortier-Vergleich