When our room is a mess and we’re tired of cleaning, sometimes we just wave a wand, and everything sorts itself back where it belongs. But the best way for this magic to work is for all the messy items to group together based on what area they’re going to. This way we get lots of things sorted a little better all at once, before we go and sort each thing individually. Well, what’s great is, that we can do this in computer science as well. We have invented algorithms that sort things by moving them into groups, and one algorithm like this is called “quicksort”.
The algorithm quicksort divides an array into smaller arrays, and recursively divides those subarrays. When we write quicksort in JavaScript, it looks like this:
function quicksort(arr) {
var pivot = arr[0];
var less = [];
var greater = [];
if(arr.length < 2) {
return arr;
}
for (var i = 1; i < arr.length; i++) {
if ( arr[i] > pivot ) {
greater.push(arr[i]);
} else {
less.push(arr[i]);
}
}
return quicksort(less).concat(pivot, quicksort(greater));
}
const myArr = [7, 4, 11, 220, 30, 99];
console.log(quicksort(myArr));The main idea with quicksort is that we divide the original array into three components. At the beginning of the algorithm, a value from the array is chosen, called a “pivot”. The pivot will be used as a reference to divide the array into two subarrays: one array containing values greater than the pivot, and one array containing lesser values. Different algorithms can be used to choose a good pivot, but one adequate way to choose a pivot is to simply use the first value in the array.
Or if we take a numerical example in pseudocode:
//Quicksort in pseudocode!
arr = [7, 4, 11, 220, 30, 99]
pivot = 7
less = [4]
greater = [11, 220, 30, 99]When we sort the values, we exclude the pivot from the sorted arrays. The pivot will be added at the end of the quicksort function, so we don’t want to include it more than once.
The operation above is quicksort! Congratulations! You figured it out. What we need to do is basically just repeat this formula for each subarray. That’s where the recursion comes in. Each time we create a subarray, we send it back to quicksort to be resorted. This way, each time, we are sorting the values a little bit better. We keep doing this until the subarrays get smaller and smaller, and eventually the last subarrays left contain either 1 or 0 values. So really, there should be one more line in this pseudocode:
//Quicksort in pseudocode!
arr = [7, 4, 11, 220, 30, 99]
pivot = 7
less = [4]
greater = [11, 220, 30, 99]
concatenate: quicksort(less) + pivot + quicksort(greater) // <-------New line! Hooray!In separating the array like this, we get two arrays, each one containing values that are more sorted than they were before they were separated, plus a value in the middle. So we’ve achieved a higher level of organization for all the numbers just by cycling through them once.
In quicksort, we add an “if” at the beginning of the function, to return arrays that contain 1 or 0 values. We don’t need to sort them anymore, because there’s nothing left in these small arrays to sort! We can spot one already in our quicksort pseudocode above: less = [4]. This array will be sent to quicksort, but it will be returned at once. However, the “greater” array is sent to quicksort, but it is resorted:
//Quicksort: Round 2! Pseudocode
newArr = [11, 220, 30, 99]
pivot = 11
less = []
greater = [220, 30, 99]
concatenate: quicksort(less) + pivot + quicksort(greater)Wow! We just got back another blank array! That means once again, only one of our resulting arrays is going to get resorted when sent to quicksort (because only one resulting array is 2 or more values long). Before we finish off the rest of that array, let’s see where we stand right now with our concatenation business. From Quicksort Round 1 we have:
//Quicksort Round 1
concatenate: quicksort(greater) + pivot + quicksort(less)
//which becomes:
concatenate: quicksort([4]) + 7 + quicksort([11, 220, 30, 99])
//and this becomes:
concatenate: [4] + 7 + [insert quicksort concatenation from Round 2]
One small detail: We write the 7 above without brackets in the pseudocode, because it’s not in an array, it’s just a saved variable (pivot). Okay, now let’s look at our Quicksort from Round 2, and add it to the concatenation from Round 1:
//Quicksort Round 2
concatenate: [] + 11 + quicksort([220, 30, 99])
//Add result from Round 2 to Round 1 concatenation:
concatenate: [4] + 7 + [ [] + 11 + quicksort([220, 30, 99]) ]
= [4] + 7 + [] + 11 + quicksort([220, 30, 99]) This result is really cool! We can see here the fruit of our efforts, as we observe how the first few values of the concatenation are sorted low to high! How exciting! This is great because it shows us that our quicksort is working. We can see that by splitting each array into a lower and higher array, and keeping the value in the middle, that we are ordering three sets of values each time. If we were doing this with only three digits, we would be done in one step. Take the following array, for example:
[2, 3, 1]
Our pivot is 2, lower values are just 1, and higher values are just 3. There we have it! [1, 2, 3]. So if we continue with our quicksort algorithm, we will eventually end up with the last array sorted:
//Round 3
newArr = [220, 30, 99]
pivot = 220
greater = []
less = [30, 99]
concatenate: quicksort([30, 99]) + 220 + []
//And finally, Round 4: our quicksort([30, 99])
newArr = [30, 99]
pivot = 30
less = []
greater = [99]
concatenate: [] + 30 + [99]
//so from Round 3 & 4 combined we get:
concatenate: [] + 30 + [99] + 220 + []
//which is to say:
quicksort([220, 30, 99]) = [] + 30 + [99] + 220 + []
//and now we add this to the result of Rounds 1 & 2:
quicksort from Round 2 = [4] + 7 + [] + 11 + [] + 30 + [99] + 220 + []
And there we have it! Our sorted values! Which of course, when concatenated, look like this:
[4, 7, 11, 30, 99, 220]
We can see that each of the Rounds resulted in a part of the results:
We can see from this diagram that each of the successive quicksort recursions takes place within the previous one.
So there we have it. Quicksort is a recursive algorithm that helps us speed things along when it comes to sorting an array, compared to sorting the array one value at a time.
References:
Bhargava, Aditya Y. (2016). Grokking Algorithms. (p.69). Manning Publications Co. [Print]
Sorting Hat image credit: Buzzfeed
Ron applauding image credit: Pinterest