Question Describe an efficient algorithm based on Quicksort that will find the element of a set that would be at position k if the elements were sorted.

Solution:We make slight modifications to the quicksort routine to find the kth smallest element.Like in normal quicksort,we choose a pivot and partition the remaining array in to 2 sub arrays.At this stage,we have 3 possibilities.

1)the size of the first sub array is k-1 ,in which case pivot itself is the kth smallest.

2)the size of the first sub array is greater than k ,in which case kth smallest element is to be recursively searched in the first sub-array.

3)the size of the first sub array is less than k-1 ,in which case reuired element is to be recursively searched in the second sub-array.

Hence unlike quicksort where each problem gives rise to 2 subproblems,here each problem gives rise to only 1 sub problem.

Pseudo Code:

QuickSelect(Array A, n, k)

pivot = A [Random(1, n)]

X={x | x belongs to A and x <=pivot}

Y={x | x belongs to A and x >=pivot}

if size(X) = k

return pivot;

else if size(X) < k

return QuickSelect(Y,n-size(X)-1,k-size(X)-1);

else

return QuickSelect(X,size(X),k);

click here

Is it not same as recursive binary search.

ReplyDelete