Bubblesort

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

$\vdots$

Source: BubbleSort.java     JavaDoc: BubbleSort.html    

Analyse von BubbleSort

Best case:	$O(n)$
Worst case:	$O(n^{2})$

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(n^{2})$

Weitere Verbesserungen möglich (ShakerSort), aber es bleibt bei $O(n^{2})$
Grund: Austauschpositionen liegen zu nahe beieinander.