Overview
Floyd-Rivest selection improves quickselect-style selection by using a sample to estimate a narrower interval around the desired rank. It then partitions only the range likely to contain the kth item.
CoreSource checked
Floyd-Rivest Selection
Selects the kth order statistic by sampling to narrow the partition range.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Searching
- Difficulty
- Intermediate
- Family
- Selection Algorithms
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
order statistic selectionselection algorithmsrandom samplingsearching
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)
When to Use
- Use when kth-element selection is needed without fully sorting.
- Use when a more sophisticated selection routine is worth the implementation complexity.
When Not to Use
- Avoid when the array is small enough that quickselect or sorting is simpler.
- Avoid when deterministic worst-case guarantees are required.
What It Does
- Samples values to estimate the kth item's location
- Narrows the active search interval
- Partitions until the kth order statistic is isolated
Use Cases
- Finding medians or percentiles in arrays
- Selection workloads where average comparison count matters
- Teaching sampling improvements over quickselect
Inputs
- Unordered comparable array A[0..n-1]
- Target order-statistic rank k (0 <= k < n)
Outputs
- The exact k-th smallest element placed at A[k]
- Partially partitioned array with elements <= A[k] on the left
Pseudocode
- 1.While the active range is large
- 2.Use a sample to estimate a subrange likely to contain k
- 3.Recursively narrow that subrange
- 4.Partition the active range around a pivot
- 5.Keep the side containing k
- 6.Return the kth element when the range is small enough to finish directly
Canonical Example
- Input
- array [9, 1, 5, 3, 7], k = 2 for zero-based order
- Output
- 5
- Explanation
- The element with two smaller values is 5, so no full sort is needed.
Implementation Notes
- Keep kth as an index in the current array coordinate system.
- Use robust three-way partitioning when duplicates are common.
- Test k at the first, middle, and last valid positions.
Common Pitfalls
- Partition bounds must continue to contain the kth index.
- Duplicate values can make naive partition loops fail to shrink.
- Sampling formulas should not be applied outside their valid range.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow sampling to choose a pivot range before partitioning on a small order statistic selection example.
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 6: While the active range is large
searching-mechanismNotes
Floyd-Rivest is a selection algorithm; it does not produce a sorted array.
Sources (1)
What each reference supports for this entry.
Floyd-Rivest Selection
PaperOriginal reference for SELECT and improved expected comparisons in order-statistic selection.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageImproves onQuickselect
Floyd-Rivest uses sampling to reduce the expected partition range.
Alternative toMedian of Medians
Median-of-medians gives deterministic worst-case bounds, while Floyd-Rivest is optimized for average behavior.
Related Algorithms
Tags
SearchRandomness