Course contentsShow
← Computer Science
Lesson 823 of 2,87219. Searching and SelectionFree lesson

Randomized QuickSelect Algorithm

Using randomized partitioning to find the k-th element with expected O(n) time, similar to quicksort's partition step.

Randomized QuickSelect Algorithm

What you'll learn: How to find the k-th smallest element in an unsorted array in expected linear time using a randomized partition strategy.


The Core Idea

Remember how Quicksort uses partitioning to divide an array around a pivot? QuickSelect applies the same idea, but with a brilliant insight: you only need to recurse into one side of the partition.

When you partition an array around a randomly chosen pivot, you know exactly where that pivot belongs in sorted order. If you're looking for the k-th smallest element:

  • If the pivot lands at position k, you're done!
  • If k is less than the pivot's position, search the left side
  • If k is greater, search the right side

By choosing a random pivot each time, you avoid worst-case scenarios and achieve expected O(n) time.

Why This Works

Think of it like a binary search through the problem space. Each partition eliminates roughly half the remaining elements from consideration. Unlike sorting (which needs O(n log n) time), you only follow one path down:

  • First partition: ~n comparisons
  • Second partition: ~n/2 comparisons
  • Third partition: ~n/4 comparisons
  • And so on...

The series n + n/2 + n/4 + n/8 + ... converges to approximately 2n, which is O(n) in expectation.

The Randomization Advantage

Just like randomized Quicksort, picking a random pivot makes it extremely unlikely you'll consistently hit bad partitions. Even if your input is sorted or has other patterns, randomization breaks those patterns.

Key Takeaway: Randomized QuickSelect finds the k-th smallest element in expected O(n) time by recursively partitioning around random pivots and only searching the side that must contain your target element.