Bubble sort is a simple sorting algorithm that steps though the input list performing pair-wise comparisons. With each pass, large values ‘bubble up’ to the top of the list.
In most real world cases it performs poorly and is primarily used as an education tool.
n ← length(A)
FOR i ← 1 to n-1
FOR j ← 0 to n-i
IF A[j] > A[j+1] THEN
swap A[j] and A[j+1]| Worst | Average | Best | |
|---|---|---|---|
| Time | \(O(n^2)\) | \(O(n^2)\) | \(O(n)\) |
| Space | \(O(n)\) |