Quicksort

Quicksort is a very efficient sorting algorithm, invented by C.A.R. Hoare in 1960. It is widely used to sort arrays. The algorithm presented below is a recursive version of Quicksort that picks an element as the pivot and partitions the array so that all elements smaller than the pivot come before it and the larger ones come after it. The subarrays are then sorted recursively.

But before we start talking about the algorithm, you need to understand what D&C (Divide and Conquer) methods are.

D&C methods

D&C methods are algorithms that solve a problem by splitting it into subproblems, solving the subproblems recursively and combining their solutions to solve the original problem.

Let's look at an example of an algorithm that uses D&C.

Example

Imagine you have an array of integers and want to know the sum of all its elements. You can solve this problem with D&C like this:

Array: [1, 2, 3, 4, 5]

What is the base case? The base case is when the array has only one element. In that case, the sum is the element itself.

How do we reach the base case? We remove one element at a time and see what is left.

Now that we have reached the base case, let's solve the problem. The sum of all elements of the array [5] is 5. Now we add the 4 we removed earlier. The sum of all elements of the array [4, 5] is 9. Now we add the 3 we removed earlier. The sum of all elements of the array [3, 9] is 12. And so on.

The sum of all elements of the array [1, 2, 3, 4, 5] is 15.

This is a simple case of D&C, and many algorithms use this concept to solve problems.

Why not use a loop?

You may be wondering why not just use a loop to solve this problem. And the answer is: you can! But in some cases, the D&C solution is simpler and easier to understand.

Another important point is that some languages, especially functional ones, have no loop constructs (for, while, etc.). In those, the only way to solve such a problem is with D&C.

Once you understand this approach, you can work with other programming languages and understand how they work.

If you have any questions, look for more examples and try solving problems using D&C.

Quicksort

Now that you understand what D&C is, let's talk about Quicksort.

Quicksort is a very efficient sorting algorithm, invented by C.A.R. Hoare in 1960. It is widely used to sort arrays. The algorithm presented below is a recursive version of Quicksort that picks an element as the pivot and partitions the array so that all elements smaller than the pivot come before it and the larger ones come after it. The subarrays are then sorted recursively.

Example

Let's see an example of how Quicksort works.

Step 1: Pick an element as the pivot. Let's pick 6.

Step 2: Partition the array so that all elements smaller than the pivot come before it and the larger ones come after it.

Step 3: Sort the subarrays recursively.

What does sorting the subarrays recursively mean? It means repeating steps 1 and 2 for each subarray, picking a pivot and partitioning it.

Let's pick 1 as the pivot.

Let's pick 2 as the pivot.

Now we have to pick 3 as the pivot.

Now that we have reached the base case, let's sort the subarrays recursively.

We go back up through the arrays until the left side is sorted.

Now let's sort the right side.

Step 1: Pick an element as the pivot. Let's pick 10.

Step 2: Partition the array so that all elements smaller than the pivot come before it and the larger ones come after it.

Now that we have reached the base case, let's sort the subarrays recursively.

We go back up through the arrays until the right side is sorted.

Now that the subarrays are sorted, the original array is sorted.

That is an example of how Quicksort works.

Performance

In software development, performance is a very important factor, and we often use Big O notation to describe an algorithm's efficiency.

If you are not familiar with Big O notation, I recommend an article I wrote about it (in Portuguese): Big O Notation.

Quicksort's performance is O(n log n) in the best case and O(n²) in the worst case.

Performance depends on the pivot you choose. If you pick a pivot that is the smallest or largest element of the array, Quicksort runs in O(n²). But if you pick a pivot that is the middle element, Quicksort runs in O(n log n).

So how do you choose the pivot? There are several ways, and the right choice depends on your problem. One option is to pick the middle element of the array.

With that in mind, I created a GitHub repository with a Quicksort implementation in Go. If you want to see it, click here.

This article is an introduction to Quicksort, and I hope you now understand how the algorithm works. Next time you hear someone talking about Quicksort, you will know what it is about.

Remember that practice makes perfect, and the more you practice, the more you will understand the subject.

If you have any questions, look for more examples and try solving problems using Quicksort.

I hope you enjoyed the article. See you next time!