Live briefing
Everything about Quickselect
Algorithm for the kth smallest element in an array
In computer science, quickselect is a selection algorithm to find the kth smallest element in an unordered list, also known as the kth order statistic. Like the related quicksort sorting algorithm, it was developed by Tony Hoare, and thus is also known as Hoare's selection algorithm. Like quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance. Quickselect and its variants are the selection algorithms most often used in efficient real-world implementations. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: QuickselectA 5-minute orientation
- Skim a recent paper: Adaptive method for phase-field fracture using a volume weighted Quickselect algorithmInfluential work since 2022
- Pick up a classic book: Data Structures and Algorithms in JavaThe most-reprinted book on the subject
- Read the landmark paper: Quickselect and the Dickman FunctionCited 51 times
- Go sideways: QuicksortA closely related topic
- Go sideways: Median of mediansA closely related topic
đź“– Definitions
Noun A sorting algorithm related to quicksort, but with limited recursion.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Quickselect and the Dickman Function
Optimal Sampling Strategies in Quicksort and Quickselect
Analysis of quickselect : an algorithm for order statistics
Multiple Quickselect — Hoare's Find algorithm for several elements
Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
Analysis of the Expected Number of Bit Comparisons Required by Quickselect
A generating functions approach for the analysis of grand averages for multiple QUICKSELECT
Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect
🆕 Influential since 2022
đź“š Books worth reading
Data Structures and Algorithms in JavaMichael T. Goodrich, Roberto Tamassia · 2014
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- Quicksort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in…
- Median of medians In computer science, the median of medians is an approximate median selection algorithm, frequently used to supply a good pivot for an exact selection…
- Introselect In computer science, introselect (short for "introspective selection") is a selection algorithm that is a hybrid of quickselect and median of medians which…
- Partial sorting In computer science, partial sorting is a relaxed variant of the sorting problem. Total sorting is the problem of returning a list of items such that its…
- Introsort Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance…
- Selection algorithm In computer science, a selection algorithm is an algorithm for finding the kth smallest value in a collection of orderable values, such as numbers. The…
- Sorting algorithm In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order…
- Floyd–Rivest algorithm In computer science, the Floyd–Rivest algorithm is a selection algorithm developed by Robert W. Floyd and Ronald L. Rivest that has an optimal expected…