Bubble Sort

Vergleichsbasiert

Vergleicht benachbarte Elemente wiederholt und tauscht sie bei falscher Reihenfolge — das größte unsortierte Element „blubbert" dabei pro Durchgang an seine endgültige Position.

Live-Visualisierung

Komplexität

Bester Fall	O(n)
Durchschnitt	O(n²)
Schlechtester Fall	O(n²)
Speicherkomplexität	O(1)
Stabiles Sortieren	Ja
In-Place	Ja

Legende

O(1): Konstant: Egal wie viele Elemente — der Aufwand bleibt gleich.
O(n): Linear: Doppelt so viele Elemente → doppelt so viel Aufwand.
O(n log n): Quasi-Linear: Wenig schlechter als linear — der Goldstandard für Sortieren.
O(n²): Quadratisch: 10× mehr Elemente → 100× mehr Aufwand. Langsam bei großen Listen.
Stabil: Stabile Sortierung: Gleiche Werte behalten ihre ursprüngliche Reihenfolge zueinander.
In-Place: In-Place: Sortiert direkt im vorhandenen Speicher, ohne eine Kopie der Liste anzulegen.
Vergleichsbasiert: Vergleichsbasiert: Der Algorithmus entscheidet nur durch „ist A kleiner als B?" — funktioniert mit beliebigen Werten.
Nicht-Vergleichsbasiert: Nicht-Vergleichsbasiert: Nutzt die Struktur der Zahlen selbst (z. B. Ziffern) — kann dadurch schneller als O(n log n) sein.

Implementierung

TypeScript-Implementierung — direkt kopierbereit.

function bubbleSort(arr: number[]): number[] {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // Bereits sortiert
  }
  return arr;
}

Wie es funktioniert

Bubble Sort ist der einfachste Sortieralgorithmus. Er funktioniert, indem er benachbarte Paare wiederholt vergleicht und sie bei falscher Reihenfolge tauscht. Nach jedem vollständigen Durchgang „blubbert" das größte unsortierte Element an seine korrekte Position am Ende. Eine optimierte Version prüft, ob ein Tausch stattgefunden hat — bleibt ein Durchgang tauschfrei, ist das Array bereits sortiert, was eine O(n)-Laufzeit im besten Fall ergibt.

Wann verwenden: In der Praxis fast nie — bei den meisten Eingaben ist die Laufzeit O(n²). Sein Hauptwert liegt im Lernbereich: Er ist leicht zu verstehen und zu visualisieren. Die einzige praktische Nische sind winzige Arrays (< 10 Elemente), wo der Overhead komplexerer Algorithmen ihren Vorteil überwiegt.

Vergleiche Bubble Sort direkt mit einem anderen Algorithmus

Code vergleichen →

Selection Sort