Bubble sort
Goes through the list again and again and swaps neighbours that are in the wrong order. After each pass, the largest remaining value is at the end.
- best Ω(n)
- average Θ(n²)
- worst O(n²)
- space O(1)
- stable
- in place
What do these mean?
- Best case: how the time grows with the list size n when the input is the easiest for this algorithm.
- Average: the usual growth of time with n. n² means twice as many values take about four times as long; n log n grows much more slowly.
- Worst case: the growth on the hardest input. Useful when speed must never drop.
- Space: how much extra memory is needed besides the list. 1 means a few variables, n means a copy of the list.
- Stable: two equal values keep their original order. Matters when sorting by one field of a record.
- In place: sorts inside the list itself, with no second list.
- comparing
- moving
- in final place
Pairs out of order: 154 (at the start: 154) out of order put in order Both axes: values from smallest to largest
Press play: the lines show how the cost grows as the sort runs
Press play or step through the algorithm.
Space: play or pause. Left and right arrows: step. Home and End: jump.
Try this: Pick a nearly sorted list. After one pass with no swaps, the algorithm stops early.
How it works
It compares two neighbours at a time and swaps them if the left one is bigger. So in each pass the biggest value moves all the way to the right, like a bubble rising. If a pass makes no swaps, the list is already sorted.
When it is a good choice
Almost never in real programs, because it is slow on long lists. It is great for learning: it shows the basic idea of sorting by comparing and swapping. It is fast only when the list is already sorted.