Randomized selection algorithm

The problem is to find the ith order statistic (i.e., ith smallest element) in an input array. This algorithm is a modification of quicksort and takes time O(n), on average, on an input array of size n.

The key idea is to partition the array around a pivot element such that each element less than the pivot lies on its left and each element greater than the pivot lies on its right. This puts the pivot in its rightful position. This step is similar to quicksort. But unlike quicksort, we don’t recurse on both parts of the array. We choose to recurse on either the first part or the second depending on the pivot position and the order i.

If i equals the pivot position, we simply return the pivot. If i is greater than the pivot position, we recurse on the right side of the array with the order being set to (i – pivot position). Otherwise, we recurse on the left side of the array with order i. This approach cuts down the running time to an expected linear time for random pivot choices.

Take a look at the C++ implementation.

One thought on “Randomized selection algorithm

  1. Pingback: Problem of the day: Matrix median | Everything Under The Sun

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s