Algorithmen·8 Min Lesezeit·Fortgeschritten

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²).

Voraussetzung:Big-O Notation

Sprache wählen

Sprache

Lerneinheit 1 von 3java + python

Bubblesort

Bubblesort sortiert ein Array, indem es immer wieder benachbarte Elemente vergleicht und vertauscht, bis keine Vertauschung mehr nötig ist. Größere Elemente "blubbern" wie Luftblasen nach oben, daher der Name. Der intuitivste Sortieralgorithmus, aber auch einer der langsamsten.

Was du in der Klausur können musst:

Idee: Schritt für Schritt benachbarte Paare vergleichen, vertauschen wenn falsch herum
Komplexität: O(n²) im Worst- und Average-Case, O(n) im Best-Case (bereits sortiert mit Optimierung)
In-Place: ja, kein zusätzlicher Speicher außer Hilfsvariable
Stabil: ja, gleiche Werte behalten ihre Reihenfolge

In Klausuren wirst du oft gefragt: gegeben dieses Array, zeichne den Zustand nach jedem Durchgang. Pro Durchgang wandert das größte unsortierte Element ans Ende, also wachsen die sortierten Bereiche von rechts.

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.

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.

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.

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

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).

Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen

Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).

Teil 1·Erklärung

Erklärung

Bubblesort

Mehr aus Algorithmen

Algorithmen

Mergesort

Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.

Algorithmen

Quicksort

Der schnellste der Klassiker im Average Case: O(n log n), in-place, partitioniert um einen Pivot. Bei sortiertem Input rutscht er aber auf O(n²) ab.

Algorithmen

Lineare Suche

Der simpelste Suchalgorithmus: jedes Element prüfen bis Treffer oder Ende. Funktioniert auf jedem Array, sortiert oder nicht. O(n) im Worst Case.

Was du danach lernen kannst

Folge-TopicSortier-VergleichAnschauen

Bubblesort — Algorithmen · UniProMax

UniProMax/Algorithmen/bubblesort

Algorithmen·8 Min Lesezeit·Fortgeschritten

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²).

Voraussetzung:Big-O Notation

Sprache wählen

Sprache

Lerneinheit 1 von 3java + python

Bubblesort

Was du in der Klausur können musst:

Idee: Schritt für Schritt benachbarte Paare vergleichen, vertauschen wenn falsch herum
Komplexität: O(n²) im Worst- und Average-Case, O(n) im Best-Case (bereits sortiert mit Optimierung)
In-Place: ja, kein zusätzlicher Speicher außer Hilfsvariable
Stabil: ja, gleiche Werte behalten ihre Reihenfolge

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.

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.

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.

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

Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen

Teil 1·Erklärung

Erklärung

Bubblesort

Mehr aus Algorithmen

Algorithmen

Mergesort

Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.

Algorithmen

Quicksort

Der schnellste der Klassiker im Average Case: O(n log n), in-place, partitioniert um einen Pivot. Bei sortiertem Input rutscht er aber auf O(n²) ab.

Algorithmen

Lineare Suche

Der simpelste Suchalgorithmus: jedes Element prüfen bis Treffer oder Ende. Funktioniert auf jedem Array, sortiert oder nicht. O(n) im Worst Case.

Was du danach lernen kannst

Folge-TopicSortier-VergleichAnschauen

Beispiel-CodeJava

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.

Beispiel-CodePython

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Python: Tuple-Unpacking statt Hilfsvariable. Komplexität ist identisch.

Komplexität

Zwei verschachtelte Schleifen über n Elemente:

Fall	Vergleiche	Tauschungen
Worst Case (umgekehrt sortiert)	`n(n-1)/2`	`n(n-1)/2`
Average Case	`∼ n²/2`	`∼ n²/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?

Teil 3·Quiz / Klausurfragen

Quiz

Klausurfragen mit Lösungen (6)

F1.Welche Komplexität hat Bubblesort im Worst Case?

Antwort: O(n²)

Erklärung: Zwei verschachtelte Schleifen über n Elemente führen zu n × n = n² Vergleichen im schlimmsten Fall (z.B. komplett umgekehrt sortiertes Array).

F2.Ein Array hat 1.000 Elemente und ist bereits sortiert. Wie viele Vergleiche macht Bubblesort in einer naiven Implementierung (ohne Early-Exit)?

Antwort: Etwa 500.000

Erklärung: Bubblesort vergleicht (n−1) + (n−2) + ... + 1 = n(n−1)/2 Mal. Bei n = 1000 sind das ~500.000 Vergleiche, auch wenn das Array schon sortiert ist! Mit Early-Exit (Flag, ob getauscht wurde) wären es nur n−1 = 999.

F3.Was macht dieser Code-Schnipsel innerhalb einer Bubblesort-Iteration?

if (arr[j] > arr[j + 1]) {
    int tmp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = tmp;
}

Antwort: Vergleicht zwei Elemente und tauscht sie wenn nötig

Erklärung: Das ist der Kern jeder Bubblesort-Iteration: zwei Nachbarn vergleichen, tauschen wenn sie in falscher Reihenfolge sind. Java braucht eine Hilfsvariable, Python kann mit Tuple-Unpacking direkt tauschen.

F4.Welche Eigenschaft hat Bubblesort?

Antwort: In-Place und stabil

Erklärung: Bubblesort ist in-place (braucht O(1) Zusatzspeicher) und stabil (gleiche Werte behalten ihre relative Reihenfolge, weil Tausch nur bei strikt größer passiert).

F5.Wie viele Vergleiche macht Bubblesort im Worst Case bei einem Array der Länge n = 5? (Standard-Implementierung ohne Early-Exit)

Antwort: 10

Erklärung: n(n−1)/2 = 5·4/2 = 10 Vergleiche im Worst Case. Generell: bei n Elementen sind es maximal n(n−1)/2 Vergleiche, daher O(n²).

Typ: Zahlen-Eingabe

F6.Bubblesort mit Early-Exit (Optimierung mit Tausch-Flag) hat im Best Case eine Komplexität von O(n).

Antwort: Wahr

Erklärung: Mit Early-Exit prüft Bubblesort nach jeder Iteration ob ein Tausch passiert ist. Wenn nein → Array bereits sortiert → Abbruch. Bei sortiertem Input: nur n−1 Vergleiche im ersten Durchlauf → O(n) Best Case.

Typ: Wahr/Falsch

Bubblesort

Bubblesort

Die Idee

Implementierung

Komplexität

Eigenschaften

Wann sinnvoll?

Erklärung

Bubblesort

Mergesort

Quicksort

Lineare Suche

Bubblesort

Bubblesort

Die Idee

Implementierung

Komplexität

Eigenschaften

Wann sinnvoll?

Erklärung

Bubblesort

Mergesort

Quicksort

Lineare Suche

Die Idee

Implementierung

Komplexität

Eigenschaften

Wann sinnvoll?

Interaktiv

Bubblesort live

Quiz

Binäre Suche

Such-Vergleich

Stack und Queue