select i th smallest element from array
- by davit-datuashvili
i have divide and conqurer method to find i th smalles element from array here is code
public class rand_select{
public static int Rand_partition( int a[],int p,int q,int i){
//smallest in a[p..q]
if ( p==q) return a[p];
int r=partition (a,p,q);
int k=r-p+1;
if (i==k) return a[r];
if (i<k){
return Rand_partition(a,p,r-1,i);
}
return Rand_partition(a,r-1,q,i-k);
}
public static void main(String[]args){
int a[]=new int []{6,10,13,15,8,3,2,12};
System.out.println(Rand_partition(a,0,a.length-1,7));
}
public static int partition(int a[],int p,int q){
int m=a[0];
while ( p<q){
while (p<q && a[p++] <m){
p++;
}
while (q>p && a[q--]>m){
q--;
}
int t=a[p];
a[p]=a[q];
a[q]=t;
}
int k=0;
for (int i=0;i<a.length;i++){
if ( a[i]==m){
k=i;
}
}
return k;
}
}
but here is problem
java.lang.ArrayIndexOutOfBoundsException
please help me
