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 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 , whether or not you use it. sort comprehend 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 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. sort 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 ( ) by age. { name: 'Charles', age: 21 } 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 as a new array so as not to mutate the original array. This isn’t necessarily required, but it’s good practice. sortedArray We create as the recursive function that will take a subarray (from start index to end index) and quicksort it, mutating the along the way. The entire array is the first array to be passed to this recursive function. recursiveSort sortedArray Finally, the sorted array is returned. The function has a variable to denote the value of our pivot and a variable to denote the index delimiting the less-than and greater-than arrays. Conceptually, all less-than values will be at indices less than and all greater-than values will be at indices greater than . is initialized to the start of the subarray, but as we discover values less than the pivot value, we will adjust accordingly. recursiveSort pivotValue splitIndex splitIndex splitIndex splitIndex splitIndex 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 and all leave all other values where they are (by default, greater than the , since the split index starts at the beginning of the sub-array). splitIndex splitIndex Once the sub-array has been reordered, we move the pivot itself to the split, since we know it is located all less-than and greater-than-or-equal-to values. between All values to the left (from to ) get recursively sorted and all values to the right (from to ) get recursively sorted. itself is now the pivot value, which no longer needs to be sorted. start splitIndex - 1 splitIndex + 1 end splitIndex Conclusion 🔚 You can find the code in this article published in on GitHub: TypeScript _An implementation of Quicksort in JavaScript/TypeScript. — CharlesStover/quicksort-js_github.com CharlesStover/quicksort-js You may also add this code to your projects from NPM: _An implementation of Quicksort in JavaScript_www.npmjs.com @charlesstover/quicksort If you have any questions or relevant insight, please leave a comment. It’s quick, it’s easy, and it’s free! To read more of my columns or contact me, you can find me on and , or . LinkedIn Twitter check out my portfolio on CharlesStover.com
