Bubble Sort
Compares adjacent elements in every pass and bubbles the largest to the end.
- Comparisons 0
- Swaps 0
- sorted indices 0
- compare
- swap
- sorted
Pseudocode
1 for i from 0 to n - 1
2 for j from 0 to n - i - 2
3 if a[j] > a[j + 1]
4 swap a[j], a[j + 1]
5 done
Step log
How it works, runtime and memory
Bubble Sort sweeps through the array from left to right, comparing two adjacent elements at every step. When they are in the wrong order it swaps them. After one full pass the largest element has bubbled to the right end, so the next pass can ignore it and the considered range shrinks by one. After at most n passes the array is sorted. A small optimisation tracks whether any swap happened during a pass: if not, the array is already sorted and the algorithm exits immediately. This early-exit produces the linear best-case runtime O(n) on already-sorted input. Average and worst case need quadratically many comparisons and swaps (O(n^2)). Memory stays constant since all swaps happen inside the input array (O(1)). Bubble Sort is stable: equal elements keep their relative order.
Complexity
- Best case
O(n) - Average case
O(n^2) - Worst case
O(n^2) - Extra space
O(1)
When to use it
In practice almost only useful for teaching. Bubble Sort needs quadratically many steps and is therefore much slower than Insertion or Merge Sort. It only pays off when the code has to be minimal, the array has very few elements, or the data is already almost sorted. The early-exit variant detects a sorted input after one pass and stops immediately.