1,056 reads

Implementing Quicksort in JavaScript

by Charles StoverFebruary 6th, 2019

Too Long; Didn't Read

Quicksort is one of the most efficient methods for sorting an array in computer science. <a href="https://en.wikipedia.org/wiki/Quicksort" target="_blank">For a thorough breakdown, it has its own Wikipedia article.</a>

Companies Mentioned

featured image - Implementing Quicksort in JavaScript

Quicksort is one of the most efficient methods for sorting an array in computer science. For a thorough breakdown, it has its own Wikipedia article.

This article will cover implementing quicksort in JavaScript. Quicksort is not built in to JavaScript. Due to the sort method on the Array prototype, sorting is rarely questioned or optimized in the language. Despite that, Quicksort is still an important algorithm to at least comprehend, whether or not you use it.

How does it work? 🤔

Quicksort works by picking an element from the array and denoting it as the “pivot.” All other elements in the array are split into two categories — they are either less than or greater than this pivot element.

Each of the two resulting arrays (array of values less-than-the-pivot and array of values greater-than-the-pivot) is then put through that very same algorithm. A pivot is chosen and all other values are separated into two arrays of less-than and greater-than values.

Eventually, a sub-array will contain a single value or no value at all, as there will be no more values with which to compare it. The rest of the values were all denoted to be “pivots” at some previous point and did not trickle down to this lowest sub-array. At that point, the values will be sorted, as all values have now been declared as less than or greater than all other values in the array.

How do we implement it? 💡

Since the Array prototype method sort uses its own sorting algorithm, we cannot use it for implementing quicksort. We must create a function that receives the array-to-sort as a parameter and return the sorted-array.

Since the “value” of the item in the array may not be immediately obvious, we should offer an optional parameter for the comparator. Sorting strings or numbers is built in to JavaScript, but sorting objects isn’t. We may want to sort a collection of user objects ({ name: 'Charles', age: 21 }) by age.

Since the number of times we can divide this array into less-than/greater-than halves can vary towards infinity, we want to recursively define our logic so that we aren’t repeating our code (“pick a pivot, split, repeat”).

You may use any index as the pivot location: first, middle, last, random. Assuming randomly-sorted data, the location of the pivot won’t impact the time complexity. I will be using the last index, because that is what Wikipedia uses in its demonstration graphic, and it is nice to have a visual to coincide with the code.

The array in front of the pivot is split into two: less than the pivot at the front, greater than the pivot at the end. Finally, the pivot itself is moved between the two sub-arrays, then the sub-arrays are sorted by the same quicksort algorithm.

We create sortedArray as a new array so as not to mutate the original array. This isn’t necessarily required, but it’s good practice.

We create recursiveSort as the recursive function that will take a subarray (from start index to end index) and quicksort it, mutating the sortedArray along the way. The entire array is the first array to be passed to this recursive function.

Finally, the sorted array is returned.

The recursiveSort function has a pivotValue variable to denote the value of our pivot and a splitIndex variable to denote the index delimiting the less-than and greater-than arrays. Conceptually, all less-than values will be at indices less than splitIndex and all greater-than values will be at indices greater than splitIndex. splitIndex is initialized to the start of the subarray, but as we discover values less than the pivot value, we will adjust splitIndex accordingly.

We’ll loop through all the non-pivot values, moving the ones less than the pivot value to before the start index.

We move all values less than the pivot value to splitIndex and all leave all other values where they are (by default, greater than the splitIndex, since the split index starts at the beginning of the sub-array).

Once the sub-array has been reordered, we move the pivot itself to the split, since we know it is located between all less-than and greater-than-or-equal-to values.

All values to the left (from start to splitIndex - 1) get recursively sorted and all values to the right (from splitIndex + 1 to end) get recursively sorted. splitIndex itself is now the pivot value, which no longer needs to be sorted.