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 **i**th 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 **i**th minimum element in an array with O(N) expected running time.

**Input:**

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:** **i**th minimum element.

**Sample Input**

2 5 4 7 9 3 1 3 4 6 10 5 7 1

**Sample Output**

4 5

**Code**

Explanation is given in the gist.