It is named bubble sort for the way that the smaller or larger elements bubble up to the top. Sometimes it is also known as sinking sort for the opposite reason. It is a comparison sort that repeatedly iterates through the list, compares the adjacent elements and swaps them if they are in the wrong order. This is repeated until the list is sorted.
This is the first day of the 30 days of algorithm series. In the last day, we discussed about the basics of algorithms. You can check that too!
How bubble sort works?
Before diving into the working mechanism of bubble sort let’s assume we have an unordered list as [50, 12, 65, -5, 10, -8]. We’ll try to understand how bubble sort works by sorting this list into an ascending ordered list.
We’ll start from the first index. The algorithm will compare the first and second elements. If the first element is greater than the second element, they will be swapped.
Now we’ll compare the second and third elements. If they are in order, nothing will happen. Otherwise, we’ll swap them. This process will be continued until we reach the last element.
As we can see after the first iteration the largest element will be at the end. Now the iteration will start from the beginning again and this will continue until we get an ordered list.
At each iteration, the largest element among the unordered elements is placed in the last position. The iteration continues only in the unordered elements.
So That’s how the bubble sort works. Let’s now jump into the algorithm.
The Bubble Sort Algorithm
The pseudocode of the algorithm can be written as:
Implementation
Following is the python implementation of the algorithm.
You can find the full implementation here.
Optimizing the algorithm
If we observe well we can see that in the second loop all the elements are being checked. But as we already saw the last items are already in place after some iterations. Again if array[j] and array[j+1] are the last two elements that were swapped, then we can say all elements between array[j+1] to array[n-1] are in the correct place. So for the next iteration considering array[0] to array[j] is enough. This optimization can ignore potentially many elements at each iteration. The pseudocode of the optimized algorithm can be written as:
Implementation
Implementation of the optimized algorithm is as followed:
You can find the full implementation here.
Complexity analysis
There are two loops in the sorting algorithm. In the first iteration number of comparisons is n-1, in the second iteration it is n-2, then n-3, n-4 … 1 accordingly to the last iteration. So the total number of comparisons are:
\((n-1) + (n-2) + (n-3) + … + 3 + 2 + 1 = \frac{n(n-1)}{2} \approx n^2\)
So the complexity is \(O(n^2)\). This can be deduced from the number of loops also. There are two loops; one of them is nested. So the complexity is \(n * n = n^2\); thus, \(O(n^2)\).
Time complexities:
- Worst case complexity: \(O(n^2)\)
If the list is in descending order and we want to sort it in ascending order then the worst case occurs. - Best case complexity: \(O(n)\)
If the list is already sorted then the best case occurs. - Average case complexity: \(O(n^2)\)
If the list is in jumbled order, an average case occurs.
Space complexities:
Space complexity is \(O(1)\) because with length only one extra variable swapped or bound is used.
Applications of bubble sort
Bubble sort is one of the most simple algorithms. But it is rarely used in the practice because of its \(O(n^2)\) time complexity. Performance of this algorithm dramatically decreases as input length, \(n\) grows up.
It is mostly used for educational purposes, as an introduction to the sorting algorithms. Sometimes it is also used when the performance is not countable and a shortcode is preferred.