Algo Corner: Bubble Sort
Welcome Back to Algo Corner! This is my little corner of the internet to teach you and me about different algorithm concepts and break down how algorithms work in a fundamental manner. This will all be in Javascript with ES6 formatting.
DISCLAIMER: I AM NO EXPERT AND STILL LEARNING. If you find an error in my algorithm or math please let me know and let it be a teachable moment rather than a sarcastic or self-righteous one.
Today, I will be covering the first of the three “easier” sorting methods that can get you acclimated with sorting algorithms, Bubble Sort.
What is Bubble Sort?
The best way to describe Bubble Sort is to iterate an array, and compare every iteration to every other element in the array. If our current number is larger than the next element in the array, we swap. If not we move on to the next element in the array and check again.
This might sound like a lot and it is! This sorting method is almost never used due to the inefficiency of its Big O. However, it is a good intro algorithm to get our feet wet, and understand sorting at a base level.
Problem
Write a function that takes in an array of integers and returns a sorted version of that array. Use the Bubble Sort algorithm to sort the array.
Sample
array = [8, 5, 2, 9, 5, 6, 3]**BUBBLE SORT MAGIC**array = [2, 3, 5, 5, 6, 8, 9]
Now I know that seems simple, but we are not really concerned with the end product, but the process. Take a look at the solution walk through below to get into the meat of it.
Solution
const bubbleSort = (array) => {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
if (array[j] > array[j + 1]) {
[array[j], array[j + 1]] = [array[j + 1], array[j]];
}
}
}
return array;
}Key Elements of Solution
ES6 Swap: Prior to this handy dandy function, we needed to create a swap helper function that did some sleight of hand with reassignments. But now, to swap two items in an array all we need to do is set two arrays equal to each other, pass them items you want to swap into the first array, and switch the two values in the second array.
arr = [thing1, thing2, thing3, thing4]
[thing1, thing2] = [thing2, thing1]
// New Array after swap
arr = [thing2, thing1, thing3, thing4]It looks so much neater and really cleans up the code.
What is happening in the code?
We are running two for loops(uh oh)! Our first number is the number we will compare every other element to. If there is a larger number than the first number, that number will take over moving to the end. If not, our original number will make it all the way to the end. The best way to see what happens is to map it out! We will go over the outer for loop iteration, and if you want just follow the pattern for the rest of the numbers in the array.
[8,5,2,9,5,6,3]
First Loop j= 0 Value = 8
Hence, the term bubble sort, because we are bubbling the largest number to the top! Not much to really cover here. Please write it out! You will see the pattern. It is always better to understand the principle of the sort, than the actual code. The algorithm is code agnostic!
Important Note: I am going to re-stress that you would never use this in production! There are far better sorts. We are using this as a spring board because (a) it is easy to grasp and (b) we love bubbles!
Time/Space Complexity
Our time complexity is O(n²) because of the nested loops. We can have a best case scenario of O(n), but that is only if the list is sorted already.
Our space complexity is O(1) because we are not using any additional space. We are mutating the array and swapping indexes. We are not creating any new indexes, or any new data structures to cache or parse data for us.
Next Time on Algo Corner
We will be continuing our sorting series with Insertion Sort! The sort that puts itself in the middle of everything.
