While we do want to learn the most efficient algorithms, studying the most inefficient algorithms can also give us context about what exactly a good algorithm is, what it looks like, and why it’s considered ‘good’. Bubble sort is by far one of the worst sorting algorithms and should (most likely) never be used in production code, so keep that in mind as we move forward :)
This is often the easiest to conceptualize and a natural way for the brain to think about sorting. Bubble sort gets its name from what a visualization might look like as each number is bubbled up to the front of the array space by space. It’s a quadratic sorting algorithm because it uses an iterative approach by continuously looping and swapping elements until they are in the correct order.
Elements are only swapped with other elements that are one index away. This can lead to a large number of swaps because it’s so inefficient. Algorithms like insertion sort and selection sort perform drastically better.
The worst case scenario of this algorithm is quadratic — O(n²) — because it’s possible that the data will be the exact opposite of ordered. Best case scenario is linear — O(n) — because even if it’s entirely ordered, we have to check through each set of numbers.
The space complexity of Bubble Sort is O(1).
There is one case where bubble sort is fairly efficient. This is when the list is sorted or almost entirely sorted, therefore it would only require swapping a few elements that are only one index away. However, this is only true if you use an optimized algorithmic approach to bubble sort which tracks if no swaps take place and therefore exits the sort early. I’ll explore the code for this algorithm below.
Below is the optimized version of bubble sort that will exit the sort function if no swaps take place. The key here is to use a while loop where it can track if it doesn’t attempt to sort elements after the element that was swapped last in the most previous iteration.
Congratulations on completing (possibly) your first sorting algorithm! Next up is insertion sort :)
Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.
I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!