A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

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 ...