Question

In QuickSelect algorithm based on the rank of the anchor value we recursively zero in on one of two sub-arrays to find the median value of the original array. Fill in the details of this algorithm.

Answer 1

This algorithms is similar to quicksort algorithm in a way but differs in what they output and way recursion is applied on both.

In quickselect algorithm we find kth(k is anchoring variable) smallest element.here we have to find median which means k=n/2 where n is size of input array.

This algorithm takes in best case O(n),average case O(nlogn) and in worst case O(n*n)

Algorithm:-

QuickSelect(a,p,q,k)/* a is array,p is its starting index and q is its ending index and k =( p+q)/2*/

{

if(p==q)

return a[q];

else

{

m = partition(a,p,q);

if(m==k)

return a[m];

else if(m>k)

QuickSelect(a,p,m-1,k);

else

QuickSelect(a,m+1,q,k);

}

}