Bubble Sort - Your Sorting 101 Guide
Updated: Jun 3, 2022
Algorithm
Bubble sort is one of the simplest sorting algorithms. Bubble sort works by scanning (passing) the given array multiple times and repeatedly swapping adjacent elements until all elements in the array are sorted. In each pass, the largest element is pushed or bubbled to its correct position towards the end of the array. Hence the name bubble sort.
During its processing bubble sort segregates the array into two parts, sorted portion and unsorted portion. Sorted portion (sorted elements) will be towards the end of the array. In each pass once the elements are moved to their correct position in the array (sorted portion), there is no need to compare those elements again.
For a given input array arr that needs to be sorted in ascending order, bubble sort does the following steps:
Bubble sort compares adjacent elements and swaps them if they are not in correct order.
We start by comparing the first and second element in the array. If first element is greater than second element, that means they are not in correct order, so we swap them. If first element is less than second element, that means they are in correct order, so there is no need to swap. If first and second elements are equal then also there is no need to swap, because whether we swap them or not it doesn't make any difference to the output (however if you want your algorithm to be stable, then you should not be swapping them).
Next we move on to compare the second and third element and repeat the comparisons mentioned in step 2. Then we compare third and fourth elements and so on until we reach the end of the array. This comparison procedure, described in step 2 to 3, from first element to the last element is known as one "pass" on the array.
For an array of size n, we need a total of n-1 such passes on the array for it to be fully sorted.
Also in each pass one element is moved to its correct sorted position in the array, we don't have to consider this element again in the next pass as it is already sorted.
Simulation
Consider we are given the below input array:
Below is a simulation of how bubble sort sorts the given array in each pass. Elements marked in green are the elements to be compared and elements marked in grey are sorted elements.
Pass 1
The largest element in pass 1, i.e. 19, is bubbled to the last position in the array.
Pass 2
Pass 3
Pass 4
Color code used in above diagrams:
Implementation
The implementation for bubble sort is pretty straight forward, we need to run two loops. The outer loop keeps track of the number of "passes" and in the inner loop we compare the adjacent elements.
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Below code shows a basic implementation of bubble sort:
Code
Language: Go
Note: In the above code "n-i-1" ensures that we are not processing the already sorted elements again.
Language: Python
In the above implementation, the algorithm does all the comparisons even if the given array is already sorted. Clearly this takes extra time and is not an efficient way to implement bubble sort. In bubble sort it takes just one pass to determine if the array is already sorted. We can use this to our advantage, we can make a minor tweak to our basic implementation by introducing a boolean flag to optimize it as show in code below:
Language: Go
Language: Python
This optimized solution does not improve to the worst case time complexity of bubble sort, which is still O(n^2) for both the approaches, however we can save a few unnecessary comparisons using this optimized solution.
Complexity Analysis
Time Complexity: O(n^2)
The worst case time complexity of bubble sort is O(n^2) since we have to run two loops to implement it and in the worst case we would end up making nearly O(n^2) comparisons to get the final sorted array.
The worst case occurs when the input array is in non-increasing or descending order.
The best case time complexity of bubble sort is O(n). The best case occurs when the input array is already sorted. Bubble sort just needs one pass in this case to determine that the array is already sorted.
Space Complexity: O(1)
Bubble sort does not use any extra space to sort the given array, it sorts the given array in place.
Key Points
Bubble sort works well for large arrays where the given data is mostly sorted since it takes just one pass on the array to determine if the array is already sorted. But if most elements in the array are not sorted and if it is a large array then it is not preferred to use bubble sort as it is not efficient, algorithms like quick sort would be a better choice in such cases. Bubble sort is only useful for very small and nearly sorted arrays.
Now you know how bubble sort works. Don't stop here, you can explore more sorting algorithms from code recipe here.
That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.
If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).
You can explore more such amazing articles from code recipe in our blogs section. You can explore more algorithms in our algorithms section.
Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time. Join now.
