Sortieren mit Bubblesort = Blasen steigen auf
``Vertausche jeweils unsortierte Nachbarn''
4 9 3 2 5
3 9
2 9
4 3 2 5 9
3 4
2 4
3 2 4 5 9
Source: BubbleSort.java JavaDoc: BubbleSort.html
Analyse von Bubblesort
| Best case: | O(n) |
| Worst case: | O(n2) |
Die kleinste Zahl wandert in der for-Schleife jeweils um eine Position nach links.
Wenn sie zu Beginn ganz rechts steht, so sind n - 1 Phasen nötig.
| Average case: | O(n2) |
Weitere Verbesserungen möglich ( Shaker Sort),
aber es bleibt bei O(n2)
Grund: Austauschpositionen liegen zu nahe beieinander.