Overview
Quickselect partitions an array around a pivot and keeps only the side that contains the desired rank. It is related to quicksort but recurses into one partition instead of both.
CoreSource checked
Quickselect
Finds the kth smallest item by partitioning around pivots without fully sorting.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Searching
- Difficulty
- Intermediate
- Family
- Selection
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Hoare Selection
Core Concepts
candidate searchrank selectiondivide and conquerin-place updateselectioncandidate spacematch testsearch interval
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n^2)
Space
O(1)
When to Use
- Use when one order statistic is needed and average linear time is acceptable.
- Use when mutating or partially rearranging the input is acceptable.
When Not to Use
- Avoid when deterministic worst-case linear time is required.
- Avoid when the input order must remain unchanged and copying is too expensive.
What It Does
- Partitions items around a pivot
- Compares the pivot rank with k
- Continues only in the partition containing k
Use Cases
- Finding medians or percentiles
- Top-k preprocessing
- Selection without full sorting
Inputs
- Array of comparable values
- Target rank
Outputs
- Value with the requested rank
Pseudocode
- 1.Choose a pivot in the active range
- 2.Partition values less than, equal to, and greater than the pivot
- 3.If k lies in the equal range, return the pivot value
- 4.Otherwise continue in the side that contains k
- 5.Repeat until the active range has one item
Canonical Example
- Input
- array [9, 1, 5, 3, 7], k = 2 zero-based
- Output
- 5
- Explanation
- The value 5 would appear at index 2 in sorted order.
Implementation Notes
- Define whether k is zero-based or one-based.
- Use randomized pivots or median-of-three to reduce adversarial behavior.
- Consider three-way partitioning when duplicates are common.
Common Pitfalls
- Bad pivot choices can degrade to quadratic time.
- Duplicates require careful partition semantics.
- Confusing kth index with kth value creates off-by-one errors.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow partitions being discarded until the desired rank remains.
Target key: 41low=0, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
Step 1 of 5: Choose a pivot in the active range
selection-partitionNotes
Quickselect is usually destructive because partitioning rearranges the array.
Sources (2)
What each reference supports for this entry.
Hoare FIND
PaperOriginal selection algorithm reference for partition-based order statistic search.
Open sourceIntroduction to Algorithms (CLRS)
BookAlgorithms textbook support for Quickselect's invariant, correctness argument, and asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborQuick Sort
Both use partitioning around pivots, but quickselect follows only one side.
Alternative toFloyd-Rivest Selection
Floyd-Rivest adds sampling to reduce expected comparisons.
Related Algorithms
Tags
SearchOrder StatisticDivide and ConquerIn Place