Bubble Sort
Task: Sort this array in ascending order
Why we need Bubble Sort
Analogy
- Imagine students standing in a line in a random order, and you want them arranged shortest to tallest.
- You do not need to see the whole line. You only look at two students standing next to each other.
- If the left one is taller, they swap places. Then you move one step to the right and do it again.
- Keep going and the line sorts itself. That is bubble sort.
What is bubble sort?
Definition
Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.
One walk from left to right is called a pass. After each pass, the largest remaining value has been carried to the end.
It keeps making passes until one goes by with no swaps at all.
Compare the neighbours
Take four heights:
170 155 180 160
Look at the first two. 170 > 155, so they swap. Move one step right and look at the next pair. 170 < 180, so nothing happens. Step right again: 180 > 160, so they swap.
That is one pass, and it took three comparisons for four values.
Why is it called bubble sort?
Follow what happened to 180. It started in the middle, and every comparison moved it one place right until it reached the end.
Large values keep rising toward the right the way a bubble rises to the surface, and that is where the name comes from.
Note
The bubbling only goes one way. A large value can travel the whole array in a single pass, but a small value stranded at the right moves left by one place per pass at most. That asymmetry is why bubble sort is slow.
One pass puts one value in its place
After the first pass, 180 is exactly where it belongs, so there is no reason to ever look at it again. The next pass only has to work on what is left.
Each pass is one comparison shorter than the last. For four values that is 3, then 2, then 1.
Try it
Try it yourself
Compare neighbours, swap the bigger one right
Press step to watch a single comparison, pass to run a whole sweep, and sort to go to the end. The counter shows what it cost.
The trick that makes it stop early
What if the array is already sorted?
10 20 30 40
Bubble sort still compares every pair, but nothing gets swapped. A pass that makes no swaps is proof that the array is already in order, so there is no reason to make another one.
Watch out
That check is what gives bubble sort its best case. Without it, an already-sorted array still costs O(n2). With it, one pass is enough and the cost is O(n).
In code
def bubble_sort(arr): n = len(arr) for i in range(n): swapped = False for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True if not swapped: break return arr print(bubble_sort([5, 3, 8, 4, 2]))# [2, 3, 4, 5, 8]The n - i - 1 is the shrinking pass: after i passes, the last i values are already finished.
What it costs
| Case | Time | Space | Why |
|---|---|---|---|
| Best | O(n) | O(1) | Already sorted, so one pass makes no swaps and it stops. |
| Average | O(n2) | O(1) | About half of n squared comparisons. |
| Worst | O(n2) | O(1) | Reverse order, so every pair is swapped every time. |
Space is O(1) because it sorts the array in place. Nothing is copied.
Advantages and limitations
What it is good for
- Very easy to understand and to write
- Sorts in place, using no extra memory
- Detects an already-sorted array in one pass
Where it falls down
- Very slow on large inputs
- A small value at the wrong end moves only one place per pass
- Rarely used in practice, where merge sort or quick sort win
Quick recap
- Compare adjacent elements
- Swap when they are in the wrong order
- Repeat until a pass makes no swaps
Each pass carries the largest remaining value to the end, so each pass is shorter than the last.
Key takeaway
Compare your neighbour, swap the bigger one right, and repeat until nothing moves.