Bubble Sort

• We go through the input sequence looking for inversions. For each inversion, we swap the two elements to put them in order. This way, larger elements bubble up and smaller elements bubble down.

• When we go through the input sequence without making a single swap (and find that the sequence doesn’t have any more inversions), we stop.

Pseudocode

bubbleSort(A, n):
swapped = true
while not swapped:
swapped = false
for i = 0 ... n - 2:
if A[i] > A[i + 1]:
swap A[i] and A[i + 1]
swapped = true

Complexity

• In the best case, bubble sort takes $\Theta(N)$ time.

• In the worst case, $\Theta(N^2)$ time.