How bubble sort works
Understand repeated adjacent comparisons and swaps, and why bubble sort usually costs O(n²).
Read the Korean original on Velog ↗English translation
Bubble sort is not fast, but it clearly shows how comparisons and swaps produce an ordered array. Each pass moves another element into its final position.
Bubble sort
Compare neighboring elements and swap them if they are out of order. The basic algorithm has O(n^2) average and worst-case complexity. A version that stops after a pass with no swaps can finish in O(n) on an already sorted array.
The process
- Compare the first two elements.
- Swap them if they are in the wrong order.
- Move to the next adjacent pair.
- Continue to the end of the unsorted region.
- Repeat, excluding the elements already placed at the end.
