Finding the median of a set doesn’t require us to completely sort the array.
Operation of finding the median is a special case of the operation of selection : finding the kth smallest of a set of numbers. Since we cannot say that a item is kth smallest without examining k-1 elements that are smaller and N-k elements that are larger, most selection algorithms can return all the k smallest elements of a file without a great deal of extra calculations.
template <class Item>
void select(Item a[], int l, int r ,int k ){
if (r<= l) return;
int i = partition(a,l,r);
if(i>k) select(a,l,i-1,k);
if(i<k) select(a,i+1,r,k);
}
Non-Recursive Selection
template <class Item>
void select(Item a[],int l,int r , int k){
while(r>l){
int i = partition(a,l,r);
if(i >= k) r = i - 1;
if(i <= k) l = i + 1;
}
}