The ith order statistic of a set of n elements is the ith smallest element.
How can we find the ith order statistic of a set and what is the running time?
Input: A set A of n (distinct) number and a number i, with 1 <= i <= n.
Output: The element x ∊ A that is larger than exactly i–1 other elements of A.
The selection problem can be solved in O(nlogn) time. Sort the numbers using an O(nlogn)‐time algorithm, such as heapsort or merge sort.Then return the ith element in the sorted array.
In fact, selection of the ith smallest element of the array A can be done in O(n) time. So We can use a randomized version .
Randomized-Select(A, p, r, i)
if (p = r )
return A[p];
q =Randomized-Partition(A, p, r)
k=q-p+1;
if(i==k)
return A[q];
else if(i<k)
return Randomized-Select(A, p, q-1, i)
else return Randomized-Select(A, q+1, r, i - (q - p + 1))
The best case: always recurse on a subarray that has half of th elements smaller than the previous subarray.
$T(n) = T(n/2 ) + O(n) = O(n)$
The worst case: always recurse on a subarray that is only 1 element smaller than the previous subarray.
$T(n) = T(n - 1) + O(n)= O(n^{2})$.
Here we have expected running time $O(n)$ but due to bad partion worst case is $O(n^{2})$.
Even we can optimize the worst case using deterministic version. Which also takes Linear time.
Select(A,n,i):
Divide input into ⌈n/5⌉ groups of size 5.
/* Partition on median-of-medians */
medians = array of each group’s median.
pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
Left Array L and Right Array G = partition(A, pivot)
/* Find ith element in L, pivot, or G */
k = |L| + 1
If i = k, return pivot
If i < k, return Select(L, k-1, i)
If i > k, return Select(G, n-k, i-k)
Reference: Order Statistics
So The ith order statistic of a set of n elements can be found in O(n) time.
