Quick Sort routine to find the kth smallest element in an array

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