The problem is to find the i^{th} order statistic (i.e., i^{th} 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.

28.635308
77.224960

### Like this:

Like Loading...

*Related*

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