Bubble Sort
- Ω( n )
- Θ( n2 )
- O( n2 )
- space O( 1 )
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How bubble sort works
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
Read more
Bubble sort is not a practical sorting algorithm because of its poor performance. It has a time complexity of O(n²) on average, which makes it inefficient on large data sets. However, bubble sort is a simple algorithm that is easy to understand and implement, which makes it a good choice for educational purposes and simple cases.
| Best time | Ω( n ) | good |
|---|---|---|
| Average time | Θ( n2 ) | poor |
| Worst time | O( n2 ) | poor |
| Worst space | O( 1 ) | good |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.