What to know about “Bubble Sort”
What is Bubble Sort?
Bubble sort is a type of algorithm tactic. The idea is that when we’re given an array, if we’re sorting the array in ascending order, we will have the larger numbers bubble up to the top one at a time. So, you can see where the name comes from! It creates a helpful visual for us in our minds.
As we loop through each item, we compare it with the next item. So let’s say we have an array: [6, 2, 9, 10, 1, 23]. The way that bubble sort algorithms perform is that it will start at the beginning and compare our first two numbers: 6 and 2. Then it will check is the first one larger than the second number we are comparing it to. If so, we swap them. So in our case we check ‘is 6 larger than 2?’ Yes, so we will swap their positions or indexes, and place 2 in front of 6 leaving us with the array in this order so far: [2, 6, 9, 10, 1, 23]. For our next step, we will proceed to check 6 and 9. This time we do not perform a swap since 6 is less than 9. It’s in the correct order. So it moves on to check the next two as a pair which will be 9 and 10. Then 10 and 1. Here since 10 is greater than 1, it will swap. Then, it will check 10 and 23 so it does not swap since 10 is less than 23. After going through our array in the first round of checks, we end up with this array: [2,6,9,1,10,23]. However, this is still not correct and, you guessed it, we are not done. This was only our first iteration on our array. Now we repeat the process and start again from the begging of our array. As you can tell from our array, 1 is the number that is in the wrong number and needs to get to the beginning of the list. In bubble sort, this algorithm will need to keep going through and looping to calculate the pairs next to each other in order to continue moving up our 1 to the first spot. Eventually, we end up with our sorted array.
As we go through, the amount of elements that we need to sort decreases since every iteration is performing some valuable change for us. In our previous example, we started out with 6 elements that needed to be sorted then after one iteration we got it in a more sorted order than the original product. We have fewer elements to sort as we go through. Since our algorithm is mainly reliant on swapping our numbers to put them in order, it is good to know there are a few ways to swap our elements such as this:
var temp = arr[indx1]
arr[indx1] = arr[indx2]
arr[indx2] = temp
Implementing Bubble Sort
In order to implement our knowledge of bubble sort into code now, you want to create function that accepts an array. You start looping from the end of the array toward the beginning with a variable called i. Then start an inner loop with a variable called j from the beginning until i-1. So we will have a nested loop. Then if arr[j] is greater than arr[j+1] (in simple terms, if our first element is greater than our second element we are comparing), we will swap the two values. At the end of the loops, we want to return the sorted array.
The reason we perform our first, outer loop starting from the end toward the beginning is because the way bubble sort works is that the last number will be locked in as the highest value. There is no reason to continue looping over numbers that we know are staying at the end of our sorted array when they belong there. This is what line 2 is saying to us. We start our array at the array length and it continues while i is greater than 0, until we finish and get to the beginning of the array. Each time it will decrease by one looking at the element that comes before it. We do this so we can use i in the definition of the loop for j, which comes next on line 3. Then, we set our conditional we previously discussed: if the first number is greater than the second number we are comparing, then we swap. We set the temp to the first variable, set the first number equal to the second number and then set the second number to our temp variable. After the loops finish, we will return our sorted array:
Optimizing Bubble Sort
Now it’s time to dive deeper into our function and optimize in places that we are able to. This will allow us as developers to be aware of what is important and DRY. Let’s say that we give our bubble sort algorithm an array that is fairly sorted already such as [1,2,3,4,7,5]. After one iteration, our 7 will be at the end of the array and it will look correct like this: [1,2,3,4,5,7]. However, the bubble sort function above will continue to compare each number in our array over and over again even though we can see that after just one iteration, it is complete. Thinking in the big picture, if we have an array with a million numbers, that’s going to be a problem. It is continuing to sort when it doesn’t need to. Seems very unnecessary and a waste of time. In order to fix our algorithm so that it doesn’t perform unnecessary actions is to create the logic where we check the last time through if we did make any swaps. If we did not make any swaps then that means we are done.
Here, we are utilizing our bubbleSort function we had before but you can just add in the variable noSwaps. If it is true, then there are no swaps and it will tell us to break out of the loop. Inside the loop, you can set noSwaps to equal true. So if we do make a swap, which is our actions inside of our conditional, then we will set noSwaps to equal false after we perform our swap. So we start out with noSwpas to equal true but in our iteration, if we swap then it will continue to set noSwaps to equal false and continue our loop. Looking at our array [1,2,3,4,7,5], it will now perform so that 7 is at the end like this: [1,2,3,4,5,7]. Then, it will loop through and check if it is sorted, since there are no swaps after 7 is at the end, our loop breaks and finishes.
Time Complexity
The time complexity of bubble sort is O(n²). This is because we are utilizing a nested loop which gives us the n². With each number in the array, we are making roughly n number of comparisons. However, with our optimized version dealing with an array that is nearly sorted, it is more like linear time O(n)… which is a good thing! Even shorter amount of time. This is the best case scenario.
Additional resource
There are plenty of online resources to help you visualize algorithms step by step performance. One particular one that was very useful is called Visualgo. Visualgo is an interactive tool in the browser that, in the link I attached, lets you step through sorting algorithms. If you go to the home page, there are algorithms you can view as well. So, I highly recommend you go check it out. It’s a great visual to learn from and really understand what is happening under the hood!
Summary
I hope this was the detailed explanation of bubble sort algorithms that you were searching for! I’m always up for some feedback so let me know if there are any comments or concerns. Happy coding :)
