Sorting Algorithms Part 4: Quicksort
For today’s algorithm we’re going to take a look at Quicksort. Quicksort is a sorting algorithm, that takes an array of numbers and sorts it in ascending order. We’ve seen some sorting algorithms before — selection sort, bubble sort, and insertion sort. If you were paying close attention while reading those blogs, you might remember that we noticed that those algorithms are all a bit slow, running a time efficiency of O(n2). Quicksort solves that problem by using a slightly more complex, but ultimately more efficient method of sorting though its input array.
Quicksort breaks down sorting an array using the Divide and Conquer or D & C method. D & C is a technique for breaking down complex problems using recursion. To use the D & C method, we first define a recursive case and a base case and then use our cases to create a recursive solution. Let’s start with a base case. The base case is usually the simplest case, so for our sorting algorithm the base case is going to be an empty array or an array with only one entry, since in both those cases there is nothing to sort, instead we can simply return the array. Our recursive case is a bit trickier. Here’s what it’s going to look like: we are going to choose a pivot, which can be any value of our array. Then we will create and array of all the values greater than our pivot and another array of all the values less than our pivot. We can now call our own function on each of those sub-arrays. The recursion will keep going until we reach and empty array or array of one value which will simply return itself. We can then return the results of our recursive function call on our sub-array of values larger than the pivot plus the pivot, plus the recursive function call on our sub-array of values less than the pivot. This will be our sorted array. The code for that looks like this:
function quicksort(array) {if(array.length < 2)return arraylet middle = Math.floor(array.length/2)let pivot = array[middle]let less = array.filter(n => n < pivot)let more = array.filter(n => n > pivot)return quicksort(less).concat(pivot).concat(quicksort(more))}
Ideally, Quicksort has a time efficiency of O(n log n), but it can be slower depending on which pivot you pick — to be most efficient you should use the middle value of the array as the pivot. That’s way more efficient than our other sorting algorithms though, so hooray! We don’t need to worry about bogging down our app with slow code!
So, by using recursion, we can write a method that’s both shorter and quicker than our previous sorting algorithms. In fact Quicksort is used as the basis for the built in sorting function in many coding languages such as C and others because it’s so nice and efficient. Have some fun with this algorithm explore how it works in more detail!
