Bubble Sort
Vergleicht in jeder Runde benachbarte Elemente und schiebt das größte an das Ende, wie Blasen die aufsteigen.
- Vergleiche 0
- Tauschvorgänge 0
- sortierte Indizes 0
- Vergleich
- Tausch
- sortiert
Pseudocode
1 for i from 0 to n - 1
2 for j from 0 to n - i - 2
3 if a[j] > a[j + 1]
4 swap a[j], a[j + 1]
5 done
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Bubble Sort durchläuft das Array von links nach rechts und vergleicht in jedem Schritt zwei benachbarte Elemente. Stehen sie in der falschen Reihenfolge, werden sie getauscht. Nach einer kompletten Runde steht das größte Element ganz rechts wie eine Blase, die aufgestiegen ist. Im nächsten Durchlauf braucht der Algorithmus dieses Element nicht mehr anzufassen, der zu betrachtende Bereich schrumpft also um eins. Nach höchstens n Runden ist das Array sortiert. Eine kleine Optimierung speichert, ob in einer Runde getauscht wurde: falls nicht, ist das Array bereits sortiert und der Algorithmus kann sofort abbrechen. Dieser Frühausstieg sorgt für die lineare Best-Case-Laufzeit O(n) bei bereits sortierter Eingabe. Im Mittel und im schlimmsten Fall sind quadratisch viele Vergleiche und Tausche nötig (O(n^2)). Der Speicherverbrauch bleibt konstant, weil ausschließlich im Eingabe-Array getauscht wird (O(1)). Bubble Sort ist stabil: gleichwertige Elemente vertauschen ihre Reihenfolge nicht.
Komplexität
- Best Case
O(n) - Average Case
O(n^2) - Worst Case
O(n^2) - Zusatz-Speicher
O(1)
Wann verwenden?
In der Praxis fast nur didaktisch sinnvoll. Bubble Sort braucht quadratisch viele Schritte und ist damit deutlich langsamer als Insertion oder Merge Sort. Er lohnt sich nur, wenn der Code minimal sein muss, das Array wenige Elemente hat oder bereits fast sortiert ist. Die Variante mit Early-Exit erkennt eine bereits sortierte Eingabe nach einer einzigen Runde und bricht sofort ab.