Implementing Sorting Algorithms in JavaScript
So you need to sort an array of numbers. Stop. Run, do not walk, over to the MDN and get yourself acquainted with the Array.prototype.sort() method. You almost certainly don’t need to implement your own sort. Nearly any language you pick up will have a battle-tested sort implementation ready for you to use. If, however, you are curious about how different sorting algorithms are implemented and how they perform, read on!
The Basics
Ok. So you have an array of numbers. It’s all jumbled. You need it not to be. Maybe it looks like [9, 8, 3, 7, 2] but you want it to look like [2, 3, 7, 8, 9]. I won’t judge. I will, however, walk you through a few ways to get there.
Firstly, let’s try something simple. We’re going to start from the left side of the array and compare the first element to the one next to it. If the left one is greater than the right one, we switch them. Now we compare the second element to the third. Again, switch them if they are out of order. Keep repeating this process until we have reached the end of the array. Though you might think we’ve sorted the array, we’re actually just getting started. In order to finish the process, we have to repeat these steps once for every element in the array:
You may have noticed that this becomes quite repetitive. I omitted the last 7 checks because they would not have updated the array any further. Note also that each time we iterate, we create an increasing section at the end of the array which is already sorted. We will take advantage of both of these phenomena to improve our algorithm.
So wait, which algorithm is this? This is the Bubble Sort, named for the manner in which the large values bubble up to the end of the array. Since we are looping over each element of the array once for each element in the array, bubble sorting has a worst-case time complexity of O(n^2), which is disappointingly slow. On the leaderboard above you can see the results of sorting a 1000-element array composed of numbers from 0–999 1000 times. Our bubble sort is unusably slow in this application, unless it is handling sorted or equal data.
There are several things to note about this implementation. Firstly, the inner loop covers a shorter and shorter section of the array each time the outer loop increments (j < arr.length — (i + 1)) . This stops it from checking the already sorted part at the end of the array. Secondly, the change flag is used to determine whether any elements were switched on this pass through the array. If not, the array is already sorted and we can break early. That second trick makes bubble sort very quick on data that is nearly sorted. Thirdly, line 7 features one of my favorite ES6 features, array destructuring. In this case, I’m using it to swap elements in the array without needing to define a temporary variable.
Let’s Get Clever
If we have a lot of random data to sort, we are going to need a better algorithm. Clearly comparing every element to every other element for each element in the array is just too many comparisons. One way that we can reduce the comparisons is by partitioning the array. The Quick Sort algorithm involves recursively separating an array into partitions that are (in the simplest version), less than or greater than a chosen element, which is known as the pivot.
First you choose a pivot, an element of the array to compare the others to. There are several techniques for choosing one, but we are going to chose one at random. Next, you iterate over the array, partitioning the elements that are less than and greater than the pivot. Finally, you call quick sort on the two partitions, returning the combination of the results from each with the pivot (making sure to combine them in the correct order: less than, pivot, greater than). The base case for the recursion is when the given array is shorter than two elements. In that case, simply return the array.
Why do we pick our pivot at random? It keeps our algorithm efficient even when our data is sorted. For example, if we have a sorted data set and we always pick the first element, all of the other elements in the array will all end up in the greater-than partition. This means that we will end up individually checking each element against all the other remaining elements. For this reason quick sort actually has a worst-case complexity of O(n^2), just like bubble sort. That’s not very quick, is it‽ Fortunately a random pivot makes such a situation extremely unlikely.
Another element of a robust quick sort is to partition the array three ways as I did above. You put all of the elements that are equal to the pivot in their own partition, and don’t recurse on them. This keeps quick sort fast even when presented with an array that contains many or all repeating numbers. Instead of recursing for every repeated element, we simply iterate over them once, place them all in the equal-to partition, and are essentially done. Indeed, with an equal-to partition, quick sort operates in nearly linear time on equal data.
So is quick sort faster than bubble sort? Yes (in nearly all cases). If you check the scoreboard above, you will see that quick sort is dramatically faster on random and reversed data, and barely eeks out a win on equal data, while bubble sort manages to be fastest of all on sorted data.
So how is quick sort so fast? Simple: it (almost always) performs far fewer comparisons than bubble sort. This may seem counterintuitive since you compare each element with the pivot each time quick sort is called. Remember, however, that by partitioning we significantly reduce the number of elements for subsequent pivots to compare to. As a result, quick sort has an average time complexity of O(n log n), which is pretty quick!
Let’s Get Silly!
Alright, so quick sort is pretty fast, but can we go faster? You bet! Quick sort is a very efficient comparison sorting algorithm, but there are alternatives that eschew comparison entirely. How can you sort an array without comparing its elements? Magic… erm… Radix Sort! There are several other non-comparison sorting algorithms like the counting sort, but radix sort is particularly fun to wrap your head around.
Radix sort works by repeatedly grouping numbers that have the same value in the same significant position. What? Ok, so numbers can have multiple significant digits. 3 only has one, but 33 has two, 234 has three, etc. To perform our radix sort I’m going to make 10 buckets; one for each of the base-10 numerals. Then I’m going to place each number to be sorted into the appropriate bucket for their least significant digit. 3 and 33 both go in the 3-bucket, while 234 goes in the 4-bucket. Then you take all of the numbers out of their buckets and repeat the process on the next significant digit. It looks like this:
You can start from the greatest significant digit or the least. I’ve implemented a least-significant-digit radix sort for your entertainment:
There are several things to note here. On line 2 we’re finding the largest number in the array and multiplying it by 10. We’re going to use this number to determine when we have checked all of the significant digits for all of the numbers in the array. Line 6 contains a trick for iterating a particular number of times with JavaScript’s functional iteration methods. This is the closest I’ve found to Python’s range() function. It’s certainly less elegant, but it gets the job done for us here, providing us with an array of 10 empty arrays. (For the curious, I would do this in Python with a list comprehension: buckets = [[] for _ in range(10)]). Thirdly, line 12 is a trick to flatten an array of arrays by applying the concat method to each of the elements in the second parameter.
The real meat of the operation is line 9. First, we find the appropriate significant digit of the current number. Then, we append that number to the bucket with that index. Lets work through an example, say 436. At first, divisor will be 10, so (436%10)/(10/10) = 6. The second time through, divisor will be 100, giving us (436%100)/(100/10) = 3.6, which Math.floor makes into 3. Likewise (436%1000)/(1000/10) = 4.36, which becomes 4. That’s how we are able to place each number into the correct bucket for each significant digit.
So how fast is radix sort? This implementation makes it pretty clear: it loops over the array (n) once for each significant digit (m), for a complexity of O(n * m). Pretty darn quick, for sure. Radix sort is the king of the leaderboard, significantly outperforming quick sort on random and reversed data, and hanging right with it on sorted and equal data. If you’d like to perform some benchmarking yourself, here’s the code I used for this article:
Iteration Notes
I wrote an article a few weeks ago about iteration, wherein I mentioned that I preferred the functional iteration methods for all of my iteration needs. Subsequently, I have written a bunch of algorithmic code that I have benchmarked for speed. I have discovered that the functional iteration methods are significantly slower than for...of loops, and have, therefore, used them almost exclusively for the code in this article. The functional methods are quite handy and absolute performance is not usually a top concern when writing JavaScript. However, if you find yourself needing a quick speed boost in some code, using plain old loops is an easy way to do it.
I hope you’re fully sorted now!
