Explanation of the quicksort algorithm

Assume that we take the hearts from a deck of cards and want to arrange them in ascending order starting with the 2 of hearts and ending with the ace of hearts. How would you do it?

The most natural approach is that you place the (shuffled) cards next to each other, scan them, find the 2 of hearts and place it at the beginning of the row. Then scan the rest of the cards, find the 3 of hearts and place it on the right of the 2 of hearts, and so on and on, until only one card (the ace) is left. This way the 13 cards will get sorted.

Let’s pause for a moment and think about the above sorting methodology. You scan the cards until you find the 2 of hearts. Then you scan them again for the 3 of hearts, then again for the 4 and so on.

Scanning is nothing else but iteration, which is an expensive operation, especially if it’s done nested or multiple times. If we need to sort an array of a million or even more numbers, the sorting method described above might not be the best solution.

Luckily, smart people developed various sorting algorithms that are less expensive and more efficient. One of them is quicksort.

The algorithm

The main principle behind quicksort is that the algorithm won’t iterate over the entire array as many times as we normally would in case of the deck of cards above. Instead, a number called pivot is picked from the array and other numbers will be grouped into three partitions based on their relationship to the pivot number.

Partitioning

If any given number is less than the pivot number, it goes into the left partition. The left partition will contain all numbers from the array that are less than the pivot number.

If a number is greater than the pivot number, it will be placed in the right partition, so this partition will be the group of numbers greater than the pivot.

It can happen that a number is equal to the pivot. In this case we place these numbers into the equal partition.

Repeat it

We have now three partitions (groups) of numbers and have made some progress as we grouped the numbers relative to the pivot number. What’s next?

Luckily, we have nothing to do with the equal group, they are at the right place now (i.e. in their final position), so we will focus on the left and right partitions in the following sections. Note that if all numbers are different, the equal partition will only contain one element.

Having only one element in the partition is a good thing because we can’t group one element further, so our goal should be to have only one number (or even none) in each partition.

Let’s take now the left partition. What should we do with it? Well, we will repeat the same procedure on this partition! We consider the left group as being the new input. Pick a pivot from this collection and divide it into three groups relative to the pivot. equal will contain the new pivot, numbers smaller than the new pivot goes to the new left and those that are greater go to the new right partition.

We will then repeat the procedure described above until we get only one (or zero) number in each group. When only one number is found in a partition, it cannot be split further.

We have finished with the original left partition, and we need to complete the same process on the original right group, and repeat the sorting mechanism until we get only one element in each partition.

It’s like a tree

The algorithm can be seen in the diagram below.

As you can see, the visual representation of the quicksort algorithm can be loosely compared to a tree graph where the leaves are partitions with only one element (bold numbers). It’s very similar to the algorithm you used at school when you had to write a number as the product of primes. (No more reference to maths class or school. At least in this post. Really.)

If we place the numbers written in bold next to each other from left to right, we will get the original numbers in ascending order. Cool!

Translating it to JavaScript

After this short introduction let’s see the actual code. As always, my solution is not the only one, and it can happen that you know a different interpretation of quicksort, which is absolutely fine.

Here is the array of numbers we are going to sort (same as in the graph above):

const inputArr = [5, 9, 4, 85, 17, 6, 24, 2, 8];

The array is creatively called inputArr and all numbers are different. Note that the algorithm also works for arrays of numbers where some of the numbers are equal.

Getting the building blocks

Let’s translate the algorithm to code.

First, we will need a pivot number, which can be picked at random or systematically. I will always use the first element in the array as my pivot. It’s easy to find, doesn’t require much code and makes the iteration a bit easier.

Yes, iteration. We need to iterate over the array of numbers to see which partition to put each number into and a for loop can be implemented here.

As for the partitions, we can use arrays called left, equal and right.

We will need to repeat the process on both left and right, so the algorithm involves some recursion.

We also have to ensure that the algorithm stops where only one element is left in any arrays.

Finally, we have to concatenate the many arrays to one final, sorted array.

The code

Our function will unbelievably called quickSort and let’s start it by defining the partitions:

const quickSort = (arr) => {
  const left = [];
  const right = [];
  const pivot = arr[0];
  const equal = [pivot];
};

quickSort accepts one parameter, the array we want to sort. We define the partitions and store the first element of the array, which becomes the pivot element in the pivot variable (5 in our example). We also immediately place this number into the equal array as it belongs there. This way we can ignore the pivot element when iterating over the original array because it’s already in place, so we can start the iteration with the second (that is of index 1) element. This is one reason why it’s worth choosing the first element as our pivot number.

Now that I mentioned the word iteration, let’s create the for loop:

for (let i = 1; i < arr.length; i++) {
  if (arr[i] < pivot) {
    left.push(arr[i]);
  } else if (arr[i] > pivot) {
    right.push(arr[i]);
  } else {
    equal.push(arr[i]);
  }
}

As discussed above, we start with the second element, so i starts at 1, otherwise there is nothing fancy here. If the current number is less than pivot, we will push it into the left array. However, if it’s greater than pivot, we will place it in right. Finally, in case we have numbers that are equal to pivot, we will move it into the equal partition.

If you log left, equal and right in this order, you will see that left only contains numbers less than pivot and right only has numbers greater than pivot. We can concatenate them to one array to see the result better:

return [...left, ...equal, ...right];

Let’s call the function and log the returned value to the console:

console.log(quickSort(inputArr)); // [ 4, 2, 5, 9, 85, 17, 6, 24, 8 ]

If you look at the graph above, the returned array represents the second level of the tree. We have made a small step towards our goal by grouping 4 and 2 on the left of 5 and placing any other numbers on the right as they are all greater than 5. We can also see that equal only contains one element (which is pivot), so we don’t have to worry about it for now.

But how can we get through the rest of the tree in the graph? We should repeat the iteration and the partitioning on both left and right, so need to call quickSort with left and then right being the arguments. Remember, both left and right are arrays.

So we need to modify the return statement as follows:

return [...quickSort(left), ...equal, ...quickSort(right)];

As a result, we will get many arrays of length one (or zero in those cases where you can’t see left or right in the graph above) and we need to concatenate them to one final sorted array. We use the ... spread operator, which is a convenient way of concatenating arrays.

One last step is missing. If you run this function as is, you will get an error (“Maximum call stack size exceeded”), because we didn’t specify when to finish the recursion. We need to explicitly declare that no more runs of quickSort is needed on any branch if the length of the current array is 1 or zero.

Let’s include this line at the top of the function:

if (arr.length < 2) return arr;

We are simply returning the current array in this case.

The full code looks like this:

const quickSort = (arr) => {
  if (arr.length < 2) return arr;

  const left = [];
  const right = [];
  const pivot = arr[0];
  const equal = [pivot];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else if (arr[i] > pivot) {
      right.push(arr[i]);
    } else {
      equal.push(arr[i]);
    }
  }

  return [...quickSort(left), ...equal, ...quickSort(right)];
};

Let’s call the function on inputArr:

console.log(quickSort(inputArr)); // [ 2, 4, 5, 6, 8, 9, 17, 24, 85 ]

The array is sorted and we are done!

Why is quicksort efficient?

After doing that much work, we can raise the question: Why is quicksort more efficient than the way we sorted the cards above?

The detailed explanation is beyond the scope of this post and will be the topic of a later article.

The short answer is that quicksort does less iteration than the other sorting methodology. Iteration is a long and therefore expensive operation, especially if we have nested iterations. In the average case the execution time required for quicksort is more favourable than the time required for the card sorting “algorithm” described at the beginning of the post.

By dividing the array in partitions and apply quickSort on them again, we can greatly reduce the number of operations and we can achieve an efficiency similar to the case of binary search.

To prove the power of division, start dividing i.e. 32 by 2 until we get 1:

32 --> 16 --> 8 --> 4 --> 2 --> 1

We got to 1 in just five steps, so if we want to run the an iteration at each phase, we have to do it only five times.

Now compare this with the case when we subtract 1 from 32 each time until we get 1:

32 --> 31 --> 30 --> .. --> 1

We need 31 steps, so we run the iteration 31 times. The difference is clear.

Note that this little example is meant to show the power of division and how it reduces the number of operations needed in quicksort. It’s not subtraction what happens in the case of the card sorting example above.

Again, this is just to show that quicksort (which is a divide and conquer algorithm) can be an efficient technique in average cases. It’s true though that the worst case scenario of quicksort is less favourable than its average case and other sorting algorithms can be more efficient.

Conclusion

In this post I created a quicksort algorithm, which is an great way of sorting numbers in many cases. I hope you found the article useful. If so, see you next time!