Quicksort

The Quicksort algorithm is a combination of partitions and recursion. It works as follows:

1. Partition the array. The pivot is now in its proper place.

2. Treat the subarrays to the left and right of the pivot as their own arrays, and recursively repeat Steps 1 and 2. That means we’ll partition each subarray and end up with even smaller sub-subarrays to the left and right of each subarray’s pivot. We then partition those sub-subarrays, and so on and so forth.

3. When we have a subarray that has zero or one elements, that’s our base case and we do nothing.

Let’s return to our example. We began with the array of [0, 5, 2, 1, 6, 3] and ran a single partition on the entire array. Since Quicksort begins with such a partition, that means we’re already partly through the Quicksort process. We left off with:

As you can see, the value 3 was the original pivot. Now that the pivot is in the correct place, we need to sort whatever is to the left and right of the pivot. Note that in our example, it just so happens that the numbers to the left of the pivot are already sorted, but the computer doesn’t know that yet.

The next step after the partition is to treat everything to the left of the pivot as its own array and partition it.

We’ll obscure the rest of the array for now, as we’re not focusing on it at the moment:

Now, of this [0, 1, 2] subarray, we’ll make the rightmost element the pivot. So that would be the number 2:

We’ll establish our left and right pointers:

And now we’re ready to partition this subarray. Let’s continue from after Step 8, where we left off previously.

Step 9: We compare the left pointer (0) to the pivot (2). Since the 0 is less than the pivot, we continue moving the left pointer.

Step 10: We move the left pointer one cell to the right, and it now happens to be pointing to the same value the right pointer is pointing to:

We compare the left pointer to the pivot. Since the value 1 is less than the pivot, we move on.

Step 11: We move the left pointer one cell to the right, which just happens to be the pivot:

At this point, the left pointer is pointing to a value that is equal to the pivot (since it is the pivot!), and so the left pointer stops.

Note how the left pointer managed to sneak past the right pointer. That’s okay, though. The algorithm is designed to work even with such an occurrence.

Step 12: Now we activate the right pointer. However, because the right pointer’s value (1) is less than the pivot, it stays still.

Since our left pointer has passed our right pointer, we’re done moving pointers altogether in this partition.

Step 13: Next, we swap the pivot with the left pointer’s value. Now, it just so happens that the left pointer is pointing to the pivot itself, so we swap the pivot with itself, which results in no change at all. At this point, the partition is complete and the pivot (2) is now in its correct spot:

We now have a subarray of [0, 1] to the left of the pivot (the 2) and no subarray to its right. The next step is to recursively partition the subarray to the pivot’s left, which again, is [0, 1]. We don’t have to deal with any subarray to the right of the pivot since no such subarray exists.

Because all we’ll focus on in the next step is the subarray [0, 1], we’ll block out the rest of the array so it looks like this:

To partition the subarray [0, 1], we’ll make the rightmost element (the 1) the pivot. Where will we put the left and right pointers? Well, the left pointer will point to the 0, but the right pointer will also point to the 0 since we always start the right pointer at one cell to the left of the pivot. That gives us this:

We’re now ready to begin the partition.

Step 14: We compare the left pointer (0) with the pivot (1):

It’s less than the pivot, so we move on.

Step 15: We shift the left pointer one cell to the right. It now points to the pivot:

Since the left pointer’s value (1) is not lower than the pivot (since it is the pivot), the left pointer stops moving.

Step 16: We compare the right pointer with the pivot. Since it’s pointing to a value that is less than the pivot, we don’t move it anymore. And since the left pointer has passed the right pointer, we’re done moving pointers for this partition.

Step 17: We now swap the left pointer with the pivot. Again, in this case, the left pointer is actually pointing to the pivot itself, so the swap doesn’t actually change anything. The pivot is now in its proper place, and we’re done with this partition.

That leaves us with this:

Next up, we need to partition the subarray to the left of the most recent pivot. In this case, that subarray is [0]—an array of just one element. An array of zero or one elements is our base case, so we don’t do anything. The element is just considered to be in its proper place automatically. So now we’ve got this:

We started out by treating 3 as our pivot, and recursively partitioned the subarray to its left ([0, 1, 2]). As promised, we now need to come back to recursively partitioning the subarray to the right of the 3, which is [6, 5].

We’ll obscure the [0, 1, 2, 3], since we’ve already sorted those, and now we’re only focusing on the [6, 5]:

In the next partition, we’ll treat the rightmost element (the 5) as the pivot. That gives us this:

When setting up our next partition, our left and right pointers both end up pointing to the 6:

Step 18: We compare the left pointer (6) with the pivot (5). Since 6 is greater than the pivot, the left pointer doesn’t move further.

Step 19: The right pointer is pointing to the 6 as well, so we would theoretically move on to the next cell to the left. However, there are no more cells to the left of the 6, so the right pointer stops moving. Since the left pointer has reached the right pointer, we’re done moving pointers altogether for this partition. That means we’re ready for the final step.

Step 20: We swap the pivot with the value of the left pointer:

Our pivot (5) is now in its correct spot, leaving us with this:

Next up, we technically need to recursively partition the subarray to the left and right of the [5, 6] subarray. Since there’s no subarray to its left, that means we only need to partition the subarray to the right. Since the subarray to the right of the 5 is a single element of [6], that’s our base case and we do nothing—the 6 is automatically considered to be in its proper place:

And we’re done!

Code Implementation: Quicksort

Following is a quicksort method we can add to the previous SortableArray class that would successfully complete the Quicksort:

The code here is surprisingly concise, but let’s look at each line. For now, we’ll skip over the first line of code, which represents the base case. Let’s jump straight to the meaty recursion.

We begin by partitioning the range of elements between the left_index and right_index:

The first time we run quicksort, we partition the entire array. In subsequent calls, though, this line of code partitions whatever range of elements that lies between the left_index and right_index, which may be a subsection of the original array.

Note that we assign the return value of partition to a variable called pivot_index. If you’ll recall, this value was the left_pointer which pointed to the pivot by the time the partition method was complete.

We then recursively call quicksort on the subarrays to the left and right of the pivot:

The recursion ends when we reach the base case, which is when the subarray at hand contains no more than one element:

We can take our Quicksort implementation for a test drive using the following code: