Quickselect
Let’s say that 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 wanted to know what the 25th percentile was, or 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 ...
Get A Common-Sense Guide to Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
