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.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- yes
- yes
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
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.