We define selection problem as follows:
Input : An array of N distinct numbers and an integer i, with 1 ≤ i ≤ N.
Output : The element that is larger than exactly i – 1 other elements of the array.
You will obviously think of sorting the array and then simply finding the ith element in it, which can be done with O(N log N) time complexity using merge sort or quicksort or heapsort. But, can we do better than this? Yes, following randomized algorithm achieves this in O(N) expected running time practically.
This algorithm SELECT is modeled after the quicksort algorithm. As in quciksort, we partition the input array recursively. But unlike quicksort, which processes both sub-arrays, SELECT works on only one of these sub-arrays. This difference shows up in the analysis: whereas quicksort has an expected running time of O(N log N), the expected running time of SELECT is O(N). Explanation for the algorithm is clearly given in the code.
Solution in C
Question: Select the ith minimum element in an array with O(N) expected running time.
First line of the input contains T, number of test cases
Each test case contains an integer N ≤ 200, the number of integers in that array, followed by N distinct integers separated by N spaces with i in the next line.
Output: ith minimum element.
2 5 4 7 9 3 1 3 4 6 10 5 7 1
Explanation is given in the gist.