Concept:

• Implement QuickSort to partition array into two parts
• Choose “Randomized pivot" (This article use left as pivot for convenience)
• Partition the array
• Divide the elements in the left part which are smaller than the pivot
• Divide the elements in the right part which are larger than the pivot
• If the order statistic is larger than the index(i-1), than desired order statistic must lays in the right part
• If the order statistic is smaller than the index(i-1), than desired order statistic must lays in the left part

Time Complexity

$O(n)$

Conclution

Randomized Selection provides a simple and a fast way to find the ith order statictic.
Otherwise, “Deterministic selection" is another solution.

Find $i$ th statistic order element $X_{i}$

```#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

void swap(int *a,int *b){
int temp;
temp = *a ;
*a = *b;
*b = temp;
}
int RSelect(int Array[],int len,int order){
int i = 0,j = 0,k;
int pivot;
int* leftHalve;
int* rightHalve;

if(len==1) return Array[0];

// Partition
pivot = Array[0]; // Always Select left most element as pivot
i = 1 ;
for(j = 1 ; j &lt; len ; j++){
if(Array[j]&lt;pivot){
swap(&amp;Array[j],&amp;Array[i]);
i++;
}
}

swap(&amp;Array[0],&amp;Array[i-1]); // Swap the pivot with division index i-1

if(i-1==order) return Array[i-1]; // After swap, the order statistic is exactly i-1

// Divide
if(i-1&gt;order){
// Order statistic index is in the left part
leftHalve = (int *)calloc(i-1+1,sizeof(int));
for(k=0;k&lt;i-1+1;k++){
leftHalve[k] = Array[k];
}
RSelect(leftHalve,i-1+1,order);
}else{
// Order statistic index is in the right part
rightHalve = (int *)calloc(len-i,sizeof(int));
for(k=0;k&lt;len-i;k++){
rightHalve[k] = Array[i+k];
}
RSelect(rightHalve,len-i,order-i);
}
}
```