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 ans Ende des Arrays (nach rechts), daher der Name. Der intuitivste Sortieralgorithmus, aber auch einer der langsamsten. Du lernst hier die klassische Standard-Variante ohne Early-Exit (Θ(n²) in allen Fällen, Θ heißt sowohl Ober- als auch Untergrenze n², also exakt quadratisch), die optimierte Early-Exit-Variante mit swapped-Flag (Best Case Θ(n) bei sortiertem Input), die genaue Vergleichszahl n(n-1)/2 (Gauss'sche Summenformel für 1+2+dots+(n-1)), die Stabilität (gleiche Elemente behalten ihre Reihenfolge) und die Schleifeninvariante (nach Durchgang i stehen die i größten Elemente sortiert am Ende).

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.

Die Idee

Geh durchs Array, vergleiche zwei benachbarte Elemente, tausche sie wenn sie in falscher Reihenfolge sind. Standard-Variante: n-1 feste Durchgänge. Optimierte Variante (Early-Exit): brich ab sobald in einem Durchgang kein Tausch mehr passiert ist.

Größere Elemente "blubbern" wie Luftblasen ans Ende des Arrays (nach rechts), daher der Name.

Inline-Trace für [5, 1, 4, 2] (Durchgang 1)

Bevor wir den Code anschauen, das Prinzip in der Mini-Tabelle. Ein erster Durchgang auf [5, 1, 4, 2]:

Die 5 ist garantiert an Position 3, die innere Schleife läuft im nächsten Durchgang nur noch bis j < 2. So wächst der sortierte Bereich rechts mit jedem Durchgang um eins.

Implementierung (Standard-Variante, ohne Early-Exit)

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;
            }
        }
    }
}

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]

Komplexität

Äußere Schleife läuft n-1 mal, innere Schleife jeden Durchgang um eins kürzer (n-1-i). Summe: (n-1) + (n-2) + dots + 1 = n(n-1)/2 Vergleiche.

→ O(n²) im Worst und Average Case. Best Case O(n) nur mit Early-Exit.

Eigenschaften

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

Klausur-Trace: Zustand nach jedem Durchgang

Die klassische Klausuraufgabe lautet: "Gegeben das Array [5, 1, 4, 2, 8]. Wie sieht es nach jedem Bubblesort-Durchgang aus?". Wir tracen Standard-Bubblesort komplett durch.

Startzustand: [5, 1, 4, 2, 8], n=5, also n-1 = 4 Durchgänge.

Durchgang 1 (i=0, innere Schleife j=0..3):

Nach Durchgang 1: [1, 4, 2, 5, 8]. Die 8 ist garantiert an Position 4 (Schleifeninvariante).

Durchgang 2 (i=1, innere Schleife j=0..2):

Nach Durchgang 2: [1, 2, 4, 5, 8]. Die hinteren zwei Werte (5, 8) sitzen.

Durchgang 3 (i=2, innere Schleife j=0..1):

Beide Vergleiche keine Tausche. Array bleibt [1, 2, 4, 5, 8].

Durchgang 4 (i=3, innere Schleife j=0):

Nur ein Vergleich, kein Tausch. Array bleibt [1, 2, 4, 5, 8].

Insgesamt: 4 + 3 + 2 + 1 = 10 = (5 · 4)/2 Vergleiche, 4 Tausche. Standard-Bubblesort macht immer alle n(n-1)/2 Vergleiche, auch wenn schon nach Durchgang 2 fertig sortiert. Mit Early-Exit-Flag würde nach Durchgang 3 (kein Tausch) abgebrochen, das spart Durchgang 4.

Schleifeninvariante (Klausur-Klassiker): nach Durchgang i stehen die i größten Elemente sortiert am Ende. Die innere Schleife läuft entsprechend nur bis n-1-i, weil weiter rechts nichts mehr verändert werden muss.

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²), in der Praxis oft schneller, weil weniger Schreiboperationen).

Klausur-Falle: in MC-Fragen steht oft "Bubblesort ist immer O(n²)". Das ist nur halb richtig. Ohne Early-Exit ja, mit Early-Exit ist der Best Case O(n). Lies genau, ob die optimierte Variante gemeint ist.

Bubblesort live

Beobachte wie Bubblesort jeden großen Wert mühsam Stück für Stück nach rechts schiebt. Bei jedem Durchlauf landet das größte verbleibende Element ganz hinten.

Probier folgendes:

• Stell n auf 8: 28 Vergleiche, schnell durch
• Stell n auf 16: 120 Vergleiche
• Stell n auf 32: 496 Vergleiche, deutlich länger

Diese Werte sind exakt n(n-1)/2 für die Standard-Variante ohne Early-Exit. Mit Early-Exit kann der Best Case (bereits sortiertes Array) auf n-1 Vergleiche fallen.

Faustregel zum Mitnehmen: Verdoppel n und die Anzahl der Vergleiche vervierfacht sich. Das ist O(n²) zum Anfassen.

---

Code-Stepper: Bubblesort Zeile für Zeile

Hier siehst du was die zwei verschachtelten Schleifen wirklich machen. Wir sortieren das kleine Array [5, 1, 4, 2] und du beobachtest die Indizes i, j und das Array nach jedem Tausch. Achte darauf wie die innere Schleife nach jedem äußeren Durchlauf einen Schritt kürzer wird (n-1-i), der grösste Wert ist bereits hinten und muss nicht mehr verglichen werden.