Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order (ascending or descending arrangement). Bubble sort is based on Brute force method.
Bubble Sort is actually inefficient with its O(N^2) time complexity.
However, it can be terminated early, e.g. try Bubble Sort on the small sorted ascending example shown above [3, 6, 11, 25, 39] where it terminates in O(N) time.
The improvement idea is simple: If we go through the inner loop with no swapping at all, it means that the array is already sorted and we can stop Bubble Sort at that point.
Given an array of N elements, Bubble Sort will:
- Compare a pair of adjacent items (a, b)
- Swap that pair if the items are out of order (in this case, when a > b)
- Repeat Step 1 and 2 until we reach the end of array
- By now, the largest item will be at the last position.
- We then reduce N by 1 and repeat Step 1 until we have N = 1.
Comparison and swap require time that is bounded by a constant, let's call it c. There are two nested loops in (the standard) Bubble Sort.
The outer loop runs for exactly N iterations. But the inner loop runs get shorter and shorter:
When i=0, (N−1) iterations, When i=1, (N−2) iterations, ..., When i=(N−2), 1 iteration, When i=(N−1), 0 iteration.
Thus, the total number of iterations = (N−1)+(N−2)+...+1+0 = N*(N−1)/2 (derivation).
Total time = cN(N−1)/2 = O(N^2).
| Name | Best | Average | Worst | Memory |
|---|---|---|---|---|
| Bubble sort | n | n2 | n2 | 1 |