Selection Algorithms — Randomized-Select, Median of Medians, and Linear-Time Order Statistics | Chapter 9 of Intro to Algorithms

Not every algorithm problem requires sorting. Chapter 9 of introduction to algorithms focuses on the selection problem—finding the ith order statistic (like the minimum, maximum, or median) without fully sorting the input. By using clever randomized and deterministic approaches, it’s possible to achieve linear time selection, unlocking huge performance gains for many practical applications.

Prefer an audio breakdown? Watch the podcast summary below, and subscribe to Last Minute Lecture for more expert explanations of every chapter from introduction to algorithms.

Understanding Order Statistics

An order statistic is the ith smallest element in a set. Common examples include the minimum (1st order statistic), the maximum (nth order statistic), and the median (middle value). For an array of size n, the median is at index (n+1)/2 (odd n) or n/2 (even n, lower median by convention). The goal: find an element greater than exactly i – 1 other elements, efficiently and without full sorting.

Finding Minimum and Maximum Efficiently

You can find the minimum or maximum with exactly n – 1 comparisons, and both together using only 3 × floor(n/2) comparisons by pairing elements. This strategy—compare within pairs, then compare the smaller to min and the larger to max—is optimal for minimizing comparisons in the comparison model.

Randomized-Select: Fast Expected Linear Time

The RANDOMIZED-SELECT algorithm is modeled after quicksort but only recurses into the partition containing the desired element. At each step:

• Pick a random pivot and partition the array
• If the pivot is the ith element, return it
• Otherwise, recurse into the appropriate partition

The expected running time is Θ(n) because each partitioning step discards a constant fraction of the elements, with a high probability of a “good” pivot at every stage.

SELECT: Worst-Case Linear Time with Median of Medians

For guaranteed performance, the SELECT algorithm (often called "median of medians") divides the input into groups of five, finds the median of each group, recursively determines the median of those medians, and uses it as a pivot. Partitioning then discards a fixed proportion of elements each step. This approach leads to a recurrence that solves to Θ(n) worst-case time—optimal for the comparison model.

Comparison Model and Theoretical Bounds

Both RANDOMIZED-SELECT and SELECT work within the comparison model, where only element-to-element comparisons are allowed. Unlike sorting (with an Ω(n log n) lower bound), selection can be accomplished in Θ(n) time. SELECT is theoretically optimal, while RANDOMIZED-SELECT is often simpler and faster in practice due to lower constant factors.

Applications and Extensions

• Finding second smallest or largest efficiently
• Minimizing comparisons for elements that are neither min nor max
• Finding the median of two sorted arrays
• Selecting the i largest elements in sorted order
• Adapting selection techniques for quicksort partitioning
• Weighted medians and more

Chapter exercises also explore iterative versions of SELECT, using different group sizes, and practical use cases in algorithm design.

Key Terms and Concepts

• Order Statistic: The ith smallest element in a set
• Median: Middle element of a sorted list
• Pivot Element: Used for partitioning in selection algorithms
• Partitioning: Divides elements relative to the pivot
• Randomized Algorithm: Uses randomness for efficiency
• Expected/Worst-Case Running Time: Average vs. guaranteed performance
• Linear Time: Time grows proportionally to input size (Θ(n))
• Group of 5: SELECT’s method for reliable pivoting
• Median of Medians: The pivot chosen recursively in SELECT
• Comparison Model: Algorithm only uses relative ordering
• Weighted Median: Median determined by element weights
• k-Order Statistic: kth ranked element in the set

Conclusion: Selection Without Sorting

Chapter 9 of introduction to algorithms shows how you can find medians, percentiles, and other order statistics in optimal time, without the overhead of full sorting. With randomized and deterministic methods, these algorithms are both powerful and practical for real-world computing tasks and advanced algorithm design.

Ready for a walkthrough? Watch the full chapter summary on YouTube, and explore more textbook breakdowns at Last Minute Lecture.

Don’t miss future episodes—subscribe for clear, chapter-by-chapter guides to introduction to algorithms and beyond!

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.