A Common-Sense Guide to Data Structures and Algorithms

if we wanted to find the median grade. The obvious way to solve this would be to sort the entire array and then jump to the appropriate cell. 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. Quickselect relies on partitioning just like Quicksort, and can be thought of as a hybrid of Quicksort and binary search. As we’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 that we have an array of eight values, and we want to find the secondto-lowest value within the array. First, we partition the entire array: After the partition, the pivot will hopefully end up somewhere towards 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. But we also now 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 is 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 for will be found.