Quickselect

Let’s say you have an array in random order, and you don’t need to sort it, but you do want to know the tenth-lowest value in the array, or the fifth-highest. This can be useful if we have a lot of test grades and want to know what the 25th percentile is, or if we want to find the median grade.

One way to solve this would be to sort the entire array and then jump to the appropriate index.

However, even were we to use a fast sorting algorithm like Quicksort, this algorithm would take at least O(N log N) for average cases. And while that isn’t bad, we can do even better with a brilliant little algorithm known as Quickselect. Like Quicksort, Quickselect relies on partitioning and can be thought of as a hybrid of Quicksort and binary search.

As you’ve seen earlier in this chapter, after a partition, the pivot value ends up in the appropriate spot in the array. Quickselect takes advantage of this in the following way:

Let’s say we have an array of eight values, and we want to find the second-to-lowest value within the array.

First, we partition the entire array:

After the partition, the pivot will hopefully end up somewhere toward the middle of the array:

This pivot is now in its correct spot, and since it’s in the fifth cell, we now know which value is the fifth-lowest value within the array.

Now, we’re looking for the second-lowest value, not the fifth-lowest. But we do know that the second-lowest value is somewhere to the left of the pivot. We can now ignore everything to the right of the pivot and focus on the left subarray. It’s in this respect that Quickselect is similar to binary search: we keep dividing the array in half and focus on the half in which we know the value we’re seeking will be found.

Next, we partition the subarray to the left of the pivot:

Let’s say the new pivot of this subarray ends up the third cell:

We now know that the value in the third cell is in its correct spot, meaning it’s the third-to-lowest value in the array. By definition, then, the second-to-lowest value will be somewhere to its left. We can now partition the subarray to the left of the third cell:

After this next partition, the lowest and second-lowest values will end up in their correct spots within the array:

We can then grab the value from the second cell and know with confidence that it’s the second-lowest value in the entire array. One of the beautiful things about Quickselect is that we can find the correct value without having to sort the entire array.

With Quicksort, each time we halved the array, we needed to re-partition every single element again (in their subarray form), giving us O(N log N). With Quickselect, on the other hand, each time we cut the array in half, we only had to partition the one half we cared about—the half in which we know our value is to be found.

The Efficiency of Quickselect

When analyzing the efficiency of Quickselect, we’ll see that it’s O(N) for average scenarios. Why is this?

In our earlier example of an array of eight elements, we executed three partitions: one on an array of eight elements, one on a subarray of four elements, and one on a subarray of two elements.

Recall that each partition takes about N steps for the subarray it’s run upon. The total steps, then, for the three partitions is 8 + 4 + 2 = 14 steps. So an array of eight elements yields roughly 14 steps.

For an array of 64 elements, we run about 64 + 32 + 16 + 8 + 4 + 2 = 126 steps. For 128 elements, we would need about 254 steps. And for 256 elements, we would end up with 510 steps.

We can see that we need about 2N steps for N elements in the array.

(Another way to formulate this is to say that for N elements, we would need N + (N/2) + (N/4) + (N/8) + … 2 steps. This always turns out to be roughly 2N steps.)

Since Big O ignores constants, we drop the 2 from the 2N and say that Quickselect has an efficiency of O(N).

Code Implementation: Quickselect

Following is an implementation of a quickselect method that can be dropped into the SortableArray class described earlier. You’ll note that it’s very similar to the quicksort method:

The variable kth_lowest_value allows us to choose which value we’re searching for. We can search for the second-to-lowest value, the fifth-to-lowest value, or any other value we’d like.

If you want to find the second-to-lowest value of an unsorted array, you’d run the following code:

The first argument of the quickselect method accepts the position you’re looking for, starting at index 0. We’ve put in a 1 to represent the second-to-lowest value. The second and third values are the left and right indexes of the array, respectively.