JavaScript Algorithms: Quick Sort
If you haven’t already done so, I strongly encourage you to read my post on Insertion Sort first as this post builds upon the principles discussed therein 😊
Quick Sort is far more efficient than anything we’ve discussed so far. It’s also a bit more complicated and difficult to explain but I’ll do my best.
How does it work?
Well, in order to understand quick sort, you’ll need to understand two main concepts: pivots and partitions. A pivot is a position in the array where we partition the array so that items larger than value at the pivot index are to the right and items smaller are to the left. The order of the items to the left and right of the pivot does not matter. All that matters is that everything smaller than the value at the pivot index is on the left and everything larger than the value at the pivot index is on the right. I use the term partition in two ways in this post: as a noun and as a verb. As a noun to describe a part of the array that contains values larger or smaller than the pivot. As a verb to indicate the action of dividing the array around a pivot.
It might not be obvious, but if you partition all the smaller items to the left of the pivot and the larger items to the right of the pivot, the pivot will always end up in the correct position—the pivot will be sorted.
Make sense? No? Yeah, it didn’t make much sense to me at first either. An example is needed.
Say you have an array…
[ 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 ]… this is how Quick Sort would start out:
[ 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 ]
The pivot is 8 (chosen at random).
Swap pivot with the last item (to get it out of the way):
[ 10, 1, 9, 2, 5, 3, 7, 4, 6, 8 ]
Searching left and right for swaps...
[ 10, 1, 9, 2, 5, 3, 7, 4, 6, 8 ]
10 is LARGER than the pivot. 6 is SMALLER than the pivot.
10 and 6 should SWAP.
...
[ 6, 1, 9, 2, 5, 3, 7, 4, 10, 8 ]
9 is LARGER than the pivot. 4 is SMALLER than the pivot.
9 and 4 should SWAP.
...
No more swaps found.
End searching...
Swap pivot with the last left search position:
[ 6, 1, 4, 2, 5, 3, 7, 8, 10, 9 ]So as you can see, we’re choosing a pivot randomly then swapping it with the last item in the array to get it out of the way. We then start at the beginning and end of the list and move towards the center. Each time we find an item on the left that is larger than the pivot we look for an item on the right the swap it with. When we run out of items that can be swapped, we swap the pivot item at the last left search position. Miraculously, the pivot value is now “sorted”, meaning it’s a the correct index.
What do we do now? Well, remember when I said there are two concepts, pivot and partition? This is where partition comes in. We repeat the process with the partition to the left of the pivot, that is, all the values that are less than the value at the pivot index:
[ 6, 1, 4, 2, 5, 3, 7 ]
The pivot is 6.
Swap pivot with the last item:
[ 7, 1, 4, 2, 5, 3, 6 ]
Searching left and right for swaps...
[ 7, 1, 4, 2, 5, 3, 6 ]
7 is LARGER than the pivot. 3 is SMALLER than the pivot.
7 and 3 should SWAP.
...
No more swaps found.
End searching...
Swap pivot with the last left search position:
[ 3, 1, 4, 2, 5, 6, 7 ]Then we continue repeating with the left partitions…
[ 3, 1, 4, 2, 5 ]
The pivot is 4.
Swap pivot with the last item:
[ 3, 1, 5, 2, 4 ]
Searching left and right for swaps...
[ 3, 1, 5, 2, 4 ]
5 is LARGER than the pivot. 2 is SMALLER than the pivot.
5 and 2 should SWAP.
...
No more swaps found.
End searching...
Swap pivot with the last left search position:
[ 3, 1, 2, 4, 5 ]
------------------------------
[ 3, 1, 2 ]
The pivot is 2.
(no need to swap it to the end)
Searching left and right for swaps...
[ 3, 1, 2 ]
3 is LARGER than the pivot. 1 is SMALLER than the pivot.
3 and 1 should SWAP.
...
No more swaps found.
End searching...
Swap pivot with the last left search position:
[ 1, 2, 3 ]… until everything to the left of the original pivot (8) has been pivoted and partitioned over and over again until, as a whole, the array looks like this:
[ 1, 2, 3, 4, 5, 6, 7, 8, 10, 9 ]What do we have left to do? Yep, you guessed it. We need to do the same thing on the right side of the original pivot (8).
[ 10, 9 ]
The pivot is 9.
(no need to swap it to the end)
Searching left and right for swaps...
No swaps found.
End searching...
Swap pivot with the last left search position:
[ 9, 10 ]And finally we’re left with a sorted array:
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]How do we choose a pivot?
Ideally you would want your pivot to result in an evenly partitioned list. However since there is no way of knowing which value will create even partitions without first sorting the list, often people simply choose a pivot at random. Another common strategy is to choose three pivot candidates then take the median of the three. Yet another, is to simply make the last item in the partition the pivot, since the last item is just as likely as any other to create an evenly partitioned list. Choosing the last item is the most common method since it eliminates the need to swap the pivot to the end of the list.
Let’s do it in JavaScript!
There are at least two ways to approach this: the in-place method and the new array method. The in-place method sorts the original array in-place. It returns the original array after sorting. The new array method uses the values from the original array but ultimately returns a new array. I’ll discuss both methods but the new array method happens to be much easier to understand so I’ll start with that one.
New array method:
Step 1: define the function.
const quickSort = (arr) => {
// stuff will go here
}Step 2: Return if the array only contains one item.
const quickSort = (arr) => {
if (arr.length <= 1) return arr;
// more stuff will go here
}Step 3: Choose a pivot. In this case, we simply choose the last item in the list.
const quickSort = (arr) => {
if (arr.length <= 1) return arr;
const p = arr.pop();
// more stuff will go here
}Note: by calling .pop() on the array, we’re also removing the last item from that array. You’ll understand why we did that in step 7.
Step 4: Define leftArr and rightArr. This is where we’ll put the partitioned values.
const quickSort = (arr) => {
if (arr.length <= 1) return arr;
const p = arr.pop();
const leftArr = [];
const rightArr = [];
// more stuff will go here
}Step 5: Define a for loop
const quickSort = (arr) => {
if (arr.length <= 1) return arr;
const p = arr.pop();
const leftArr = [];
const rightArr = [];
for (const item of arr) {
}
}Step 6: Add the items to the appropriate partition array based on whether they are greater or less than the pivot value.
const quickSort = (arr) => {
if (arr.length <= 1) return arr;
const p = arr.pop();
const leftArr = [];
const rightArr = [];
for (const item of arr) {
if (item <= p) {
leftArr.push(item);
} else {
rightArr.push(item);
}
}
}Step 7: Return a new array in which we’ll put the result of calling quickSort recursively on the leftArr and the rightArr with the pivot value (p) sandwiched between the two.
const quickSort = (arr) => {
if (arr.length <= 1) return arr;
const p = arr.pop();
const leftArr = [];
const rightArr = [];
for (const item of arr) {
if (item <= p) {
leftArr.push(item);
} else {
rightArr.push(item);
}
}
return [...quickSort(leftArr), p, ...quickSort(rightArr)];
}I feel like step 7 needs a little more explaining. There are several things going on. First off, we’re using recursion because we’re calling quickSort from within quickSort. If you don’t know what that is, I talk about it in depth here and here. Secondly, we use the spread operator (...) to concat the results of calling quickSort on the left and the right with p, the pivot value, sandwiched between. Why does p get sandwiched? Well, remember earlier when we talked about how partitioning make it so the pivot value ends up sorted at the correct index? That’s exactly what’s happening here. p ends up sandwiched between a bunch of values that are smaller than it and a bunch of values that are larger than it.
In-place method:
The in-place method is much more common and probably a lot more efficient since it doesn’t involve constructing new arrays for each new partition. However, it’s far less intuitive and requires quite a bit more brain power to understand what all is happening.
Step 1: Define a function for swapping values at indices.
const swap = (arr, x, y) => {
[arr[x], arr[y]] = [arr[y], arr[x]];
}Notice how we’re using destructuring syntax. This is a slick new feature of ES6. You can read about it more here if you like.
Step 2: Define the quickSort function.
const quickSort = (arr, left = 0, right = arr.length - 1) => {
// stuff will go here
return arr;
}Notice there are several default parameters (left = 0, right = arr.length — 1). This is because the first time you call quickSort it’ll be partitioning the entire array. As you’ll see, we later call quickSort recursively and override those default parameters.
Step 3: If left is greater than right, there’s nothing to do so check for this condition before proceeding.
const quickSort = (arr, left = 0, right = arr.length - 1) => {
if (left < right) {
// stuff will go here
}
return arr;
}This also has to do with how we’ll be calling quickSort recursively. Since we’re doing an in-place sort, the left and right index values will get closer and closer together as recursion progresses. Eventually they’ll meet. Obviously, when that happens there’s nothing do so we check for it.
Step 4: call a (yet to be defined) function for partitioning the array.
const quickSort = (arr, left = 0, right = arr.length - 1) => {
if (left < right) {
const pivotIndex = partition(arr, left, right);
// more stuff will go here
}
return arr;
}So the (yet to be defined) partition function will be choosing the pivot index and partitioning the values on the left and the right of the pivot based on whether those values are smaller or larger than the value at the pivot index. It returns the pivotIndex which is the index in which the pivot is located.
Step 5: Call quickSort recursively for the values on the left of pivotIndex.
const quickSort = (arr, left = 0, right = arr.length - 1) => {
if (left < right) {
const pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
// more stuff will go here
}
return arr;
}Step 6: Call quickSort recursively for the values on the right of the pivotIndex.
const quickSort = (arr, left = 0, right = arr.length - 1) => {
if (left < right) {
const pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
return arr;
}Notice how we don’t touch pivotIndex when calling quickSort on the partition to the left and the right? Well, that’s because this is no different than the new array method where the pivot (p) ended up sorted in the right place. The partitions to the left and right of the pivotIndex are smaller and larger than the value at pivotIndex but otherwise unsorted so that’s why we need to call quickSort on them recursively again and again until they become sorted. Let’s talk more about how partition works…
Step 7: Define the partition function.
const partition = (arr, left, right) => {
// stuff will go here
}Step 8: Set pivot to the last item in the partition (right) and decrement right to take pivot out of the search.
const partition = (arr, left, right) => {
const pivot = right--;
// more stuff will go here
}Note how we do right-- instead of --right. That’s because when you put -- before the variable, decrements before performing assignment operation. When you put -- after the variable, it decrements after the assignment operation.
Step 9: Define a while loop which continues until left and right intersect.
const partition = (arr, left, right) => {
const pivot = right--;
while (left <= right) {
// more stuff will go here
}
}Step 10: Add an inner while loop to increment left as long as the arr[left] is less than arr[pivot].
const partition = (arr, left, right) => {
const pivot = right--;
while (left <= right) {
while (arr[left] < arr[pivot]) {
left++;
}
// more stuff will go here
}
}Step 11: Add an inner while loop to decrement right as long as the arr[right] is greater than arr[pivot].
const partition = (arr, left, right) => {
const pivot = right--;
while (left <= right) {
while (arr[left] < arr[pivot]) {
left++;
}
while (arr[right] > arr[pivot]) {
right--;
}
// more stuff will go here
}
}Step 12: Swap values at indices of left and right if matches are found.
const partition = (arr, left, right) => {
const pivot = right--;
while (left <= right) {
while (arr[left] < arr[pivot]) {
left++;
}
while (arr[right] > arr[pivot]) {
right--;
}
if (left <= right) {
swap(arr, left, right);
// more stuff will go here
}
}
}Step 13: Increment and decrement left and right after the swap has been made.
const partition = (arr, left, right) => {
const pivot = right--;
while (left <= right) {
while (arr[left] < arr[pivot]) {
left++;
}
while (arr[right] > arr[pivot]) {
right--;
}
if (left <= right) {
swap(arr, left, right);
left++;
right--;
}
}
// more stuff will go here
}Step 14: Swap the pivot for the last known left position since this is the position in which the search no longer could find a match and therefore is the true pivot index point.
const partition = (arr, left, right) => {
const pivot = right--;
while (left <= right) {
while (arr[left] < arr[pivot]) {
left++;
}
while (arr[right] > arr[pivot]) {
right--;
}
if (left <= right) {
swap(arr, left, right);
left++;
right--;
}
}
swap(arr, left, pivot);
// something else will go here
}How do we know pivot will be in the correct position after swapping with left? Well if you think about what’s happening in the while loops you’ll realize that even if no swaps are found, left will get incremented to the point where it eventually lands on pivot and stops. At this point, it won’t matter where right ends up because left will have exceeded right and that’s a condition for the outer while loop to exit. That will also mean everything to the left of pivot is smaller than the value at pivot index which means pivot is in the right place and no swap is needed.
Step 15: Return left because it is the pivot index—the index at which the pivot value is located.
const partition = (arr, left, right) => {
const pivot = right--;
while (left <= right) {
while (arr[left] < arr[pivot]) {
left++;
}
while (arr[right] > arr[pivot]) {
right--;
}
if (left <= right) {
swap(arr, left, right);
left++;
right--;
}
}
swap(arr, left, pivot);
return left;
}And we’re done! Wow! That was a lot.
Just to be extra thorough another example is needed. Lets say we call quickSort like so:
quickSort([ 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 ])Below is a map of all the swaps. The partition swaps are in bold and the pivot is shown in italics. When the pivot gets swapped, it’s shown in bold-italics.
[ 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 ] <- Initial State
[ 4, 1, 9, 2, 8, 3, 7, 10, 6, 5 ]
[ 4, 1, 3, 2, 8, 9, 7, 10, 6, 5 ]
[ 4, 1, 3, 2, 5, 9, 7, 10, 6, 8 ]
[ 1, 4, 3, 2 ]
[ 1, 2, 3, 4 ]
[ 3, 4 ]
[ 6, 7, 10, 9, 8 ]
[ 6, 7, 8, 9, 10 ]
[ 6, 7 ]
[ 9, 10 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] <- End StateNotice how little actual swapping needs to occur to reach the state where everything is sorted. The process of partitioning results in a natural sorting because there are exponentially fewer permutations each time you make a partition. Unlike other sorting algorithms where each element needs to be compared to every other element in the list, Quick Sort uses the pivots as comparison proxies. After the first partition, you know nothing on the left is larger than anything on the right so you never need to make a direct comparison between anything on the left and the right. That therein lies the reasons for Quick Sort’s superior efficiency.
Solution
So I already shown you the two possible solutions, but here they are again in color!
In-place method:
New array method: