Bubble Sort in JavaScript
Intro
Sorting algorithms are one of the foundational concepts that you’ll first encounter in the field of computer science. For junior developers or coding bootcamp grads who lack a background in CS, sorting algorithms are an integral part of having a well-rounded understanding of programming.
As you probably know, JavaScript has a sort method, so you’re maybe thinking shouldn’t that be enough? Yes and no. While the sort method in JavaScript is extremely useful, it doesn’t always do what we expect.
In the example above, the number array was sorted in an unexpected way. Instead of being sorted in either an ascending or descending manner, the array was sorted in a seemly random way. In fact, according to the sort method documentation, the method will sort an array according to the Unicode point values of the array’s elements.
While we can add a compiler function to our sort method example above, in order to control how we want to sort(ascending or descending), the key point here is that the sort method has limitations, and it’s important to familiarize ourselves with sorting “underneath the hood” in order to fundamentally understand how sorting works in JavaScript. One of the best ways to illustrate the concept of sorting in JavaScript is through the bubble sort algorithm.
Bubble Sort
Simply put, bubble sort is a sorting algorithm where the largest values “bubble up to the top”. For example, let’s return to our originally array of numbers above. In a bubble sort algorithm, we would loop through every number while comparing the current number and the number adjacent to it, and then swap the two numbers based on highest value. This process would repeat until we have the numbers in the correct order.
Bubble sorting is one of the simplest sorting algorithms to understand, but unfortunately it is not very efficient in terms of time complexity.
Let’s write our own example to demonstrate exactly how bubble sort works:
In the code above, I wrote a function called bubbleSort that takes in an array. Then the function loops through the length of the array with a variable called i, while an inner loop with a variable called j loops through.
Within the inner loop, we add our logic that orders our array in an ascending order. If j is greater than the next number in the array, then we do a switch. In order to implement the switch, we have a variable called temp which is initially set to our j value, and if the conditional is met, then j is set equal to the adjacent number, while the adjacent number is set to the temp variable (which is the initial number). In effect, we have swapped the two numbers by setting the index position of each of these numbers in the array to the one another’s.
As our loops iterate through the array, the larger numbers will be moved towards the end of the array and the smaller numbers will be moved towards the beginning of the array. Once the numbers are all in the correct ascending order, we return the sorted array at the end.
However, there is one major caveat to this example. Let’s assume that we have a nearly sorted array, and that the array will be in the correct order after 3–4 iterations, and that we also have a larger data set. Despite being in the correct order after a few iterations, the array will continue looping until both the i & j variables have iterated through the length of the array.
Big O of Bubble Sort & Optimization
Since we have a nested loop inside of our bubble sort function, the time complexity of the function is O(n²). Quadratic time complexity is very inefficient and as developers, we should do our best to avoid writing these types of low-performing functions.
One of the easiest way to optimize our bubble sort algorithm is to set a flag variable which will check a.) whether we have successfully ordered our data set and then b.) break us out of our loop. This is an easy fix that will improve the performance of our function and essentially refactor our function to be O(n) time complexity.
In the example above, our code remained largely the same with the exception of the new flag variable we created. Before starting our nested loop, I declared a variable called noSwaps. Upon the start of the loop, noSwaps is set to true.
If a swap occurs, in order words if we enter our conditional statement responsible for swapping our i & j variables, then noSwap is set to false. Now since noSwap is set to false, we will not reach our second if statement with the break code.Therefore, our nested loop continues iterating through the array.
Here is the key part of how the noSwap flags variable works: as soon as we reach the point where no swaps are occurring in our loops, this signifies that the elements in the array are all in the correct order. As a result, we will no longer enter our first conditional statement, thus the noSwap variable will remain set to true, and we will finally proceed to the second conditional statement which will break us out of the loop. Finally, our function will move on to the return statement at the end.
Conclusion
Now that we’ve seen the bubble sorting algorithm in action, there are some important takeaways to keep in mind. Bubble sorting is one of the most elementary and inefficient sorting algorithms that exist — use it sparingly, and as you become more exposed to other sorting algorithms, such as quick sort, merge sort, etc., you’ll start to understand the best use cases for these different ways of sorting.
Nevertheless, bubble sorting is a great and easy to understand introduction to sorting in JavaScript(and in turn, computer science), that allows you to go deeper into how sorting works. Lastly, although bubble sorting is typically inefficient, as we saw in the last example, there are still ways to optimize the performance of these types of algorithms.
