select k th mimimum from array a[0..n-1]
- by davit-datuashvili
i have done folloing code from progrmming pearls here is code
import java.util.*;
public class select {
public static int select1(int x[],int l,int u,int k){
//pre l<=k<=u
//post x[l..k-1]<=x[k]<=x[k+1..u]
Random r=new Random();
int t=r.nextInt(u-1-l)+l;
if (l>=u) return -1 ;
swap(l,t);
int s=x[l];
int i=l;
int j=u+1;
while (true){
do
{
i++;
}while (i<=u && x[i]<t);
do
{
j--;
}while (x[j]>t);
if (i>j) break;
int temp=x[i]; x[i]=x[j];x[j]=t;
swap(l,j);
if (j<k){
return select1(x,j+1,u,k);
}
}
return select1(x,l,j-1,k);
}
public static void main(String[] args) {
int x[]=new int[]{4,7,9,3,2,12,13,10,20};
select1(x,0,x.length-1,5);
}
public static void swap(int i,int j){
int c=i;
i=j;
j=c;
}
}
but here is mistake
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at select.select1(select.java:21)
at select.main(select.java:36)
Java Result: 1
please help
