Quickselect

Let’s say you have an array in random order, and you do not 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 had a lot of test grades and want to know what the 25th percentile was, 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 ...

Get A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.