Bubble Sort

Bubble Sort

Bubble Sort

Bubble sort consists of $n-1$ iterations. In each iteration, it walks through the array and swaps any adjacent pair that is out of order. After each full pass, the largest unsorted element "bubbles up" to its correct position at the end.

Note that Python allows swapping two variables in a single line without a temporary variable: a[i], a[i + 1] = a[i + 1], a[i].

Example

Early Exit Optimization

If no swap was made during a full pass, the array is already sorted and we can stop early:

With this optimization, bubble sort runs in $O(N)$ on an already sorted array.

Asymptotic Complexity

$O(N^2)$ in the worst and average case.