## Algorithm

for i = 1:n,
swapped = false
for j = n:i+1,
if a[j] < a[j-1],
swap a[j,j-1]
swapped = true
*→ invariant: a[1..i] in final position*
break if not swapped
end

## Properties

- Stable
- O(1) extra space
- O(n
^{2}) comparisons and swaps
- Adaptive: O(n) when nearly sorted

## Discussion

Bubble sort has many of the same properties as insertion
sort, but has slightly higher overhead. In the case of
nearly sorted data, bubble sort takes O(n) time, but
requires at least 2 passes through the data (whereas
insertion sort requires something more like 1 pass).

## Key

- Black values are sorted.
- Gray values are unsorted.
- A red triangle marks the algorithm position.