Bubble Sort
Swap neighbours that are out of order until each pass floats one value home.
Bubble Sort: Seven values
5 is larger than 1, so they swap.
Cost
- Best
- O(n)
- Average
- O(n^2)
- Worst
- O(n^2)
- Space
- O(1)
Best case O(n) requires the early-exit check on an already sorted array.
Properties
- Yes: Comparison based
- Yes: Stable
- Yes: In place
- Yes: Adaptive
- No: Online
Before this
Variants
- Early Exit
Related
Leads to
Topics that need this one first.