Notes of Introduction to Algorithm(Order Statistics)

The ith order statistic of a set of n elements is the ith smallest element. For example, the minimum of a set of elements is the first order statistic (i = 1), and the maximum is the nth order statistic (i = n). The asymptotic running time of the simple problem of finding a minimum or maximum is Θ(n). Yet select the ith smallest element appears more difficult but it also only need Θ(n) time.

Here is a divide-and-conquer algorithm for the selection problem. The procedure selection is modeled after the quicksort algorithm. As in quicksort, the idea is to partition the input array recursively. But unlike quicksort, which recursively processes both sides of the partition, selection only works on one side of the partition.

// same partition procedure as in quick sort
int partition(int a[], int p, int r)
{
int i=p,j;
for(j=p+1;j<=r;j++)
{
if(a[j]