package sorttest; //expected and worst running time is O(n),asuming that the elements are distinct
import java.util.Random;
public class random_select {
public static int select(int[] b,int lo,int hi,int i){
int[] a = merge.copy(b);
if(lo == hi){
return a[lo];
}
int mid = random_partiton(a,lo,hi);
int rank = mid + 1;
if(i == rank){
return a[mid];
}
else if(i < rank){
return select(a,lo,mid -1,i); //will not null point because i is in the range
}
else {
return select(a,mid + 1,hi,i);
}
}
public static int random_partiton(int[] a,int lo,int hi){
Random random = new Random();
int r = random.nextInt(hi)%(hi-lo+1) + lo; // a random number between lo to hi
exch(a,hi,r);
return quicksort.partition(a, lo, hi);
}
private static void exch(int[] a,int i,int j)
{ int t = a[i]; a[i] = a[j] ; a[j] = t;}
}