Overview
Bubble Sort vergleicht benachbarte Elemente und tauscht sie bei falscher Reihenfolge. In jedem Durchlauf wandert das größte verbleibende Element nach rechts.
Analogy
Wie Luftblasen im Wasser: die größten Blasen steigen in jeder Runde nach oben.
Step-by-step
- Liste durchlaufen und arr[j] mit arr[j+1] vergleichen.
- Wenn arr[j] > arr[j+1], swap ausführen.
- Nach einem Durchlauf steht das größte Element am Ende.
- Bereich verkleinern, weil das Ende bereits sorted ist.
- Früh abbrechen, wenn kein swap stattfindet.
Visual
Pass 1: [5,3,8,1,2] -> [3,5,1,2,8]; danach wird der Suchbereich pro Pass kleiner.
Common mistakes
- Innere Schleifengrenze nicht verkleinern.
- >= statt > verwenden und Stabilität verlieren.
- Kein early exit bei 0 swaps.
Practice questions
- Bubble Sort auf bereits sortierter Liste mit/ohne early exit vergleichen.
- Erklären, warum Bubble Sort stabil ist.
- Auf absteigende Sortierung umstellen.
Time
O(n²) schlechtester/avg Fall, O(n) bester Fall mit early exit