Selection Rank Algorithm

Selection Rank is a well known algorithm in computer science to find the ith smallest (or largest) element in an array in expected linear time.

The basic algorithm for finding the ith smallest elements goes like this:
»»Pick a random element in the array and use it as a ‘pivot’. Move all elements smaller than that element to one side of the array, and all elements larger to the other side.
»»If there are exactly i elements on the right, then you just find the smallest element on that side.
»»Otherwise, if the right side is bigger than i, repeat the algorithm on the right. If the right side is smaller than i, repeat the algorithm on the left for i – right.size().

Given this algorithm, you can either:
»»Tweak it to use the existing partitions to find the largest i elements (where i = one million).
»»Or, once you find the ith largest element, run through the array again to return all elements greater than or equal to it.

This algorithm has expected O(n) time.

class SelectionRankAlgorithm{
public static int rank(int []a, int left, int right, int rank){
int random = random(left, right);   //random number
int pivot = a[random];

/* partition and return end of left partition */
int leftEnd = partition(a, left, right, pivot);

int leftSize = leftEnd - left + 1;
if(leftSize == rank+1)
return Math.max(a[left] , a[leftEnd]);
else if(rank < leftSize)
return rank(a, left, leftEnd, rank);
else
return rank(a, leftEnd + 1, right, rank - leftSize);
}

public static int partition(int []a, int left, int right, int pivot){
while(true){
while(left<=right && a[left]<= pivot)
left++;

while(left<=right && a[right]>pivot)
right--;

if(left > right)
return left - 1;

swap(a, left, right);
}
}

//Utility Function to generate the random number
public static int random(int lower, int higher){
return (int)(Math.random()*(higher - lower)) + lower;
}

public static void swap(int []a, int left, int right){
int temp = a[left];
a[left] = a[right];
a[right] = temp;
}

//main method
public static void main(String... args){
int []a = {1,3,4,2,10,9,7,8,0,5,};
int min = rank(a, 0, a.length - 1, 3);
System.out.println(min);
}
}