Java – select the ith smallest element from the array

I have a divide and conquer method to find the ith smallest element from the array This is the 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,r-1,i);
        }
        return Rand_partition(a,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,a.length-1,7));
    }

    public static  int partition(int a[],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;
    }
}

However, an exception occurred at runtime: Java lang.Arrayindexoutofboundsexception.

Solution

I can fix some mistakes A secondary is this line:

return Rand_partition(a,i-k);
                           ^

Instead, you want this:

return Rand_partition(a,r+1,i-k);
                           ^

That's because you have divided [p.. Q] into three parts, as follows:

a[p..r-1],a[r],a[r+1..q]

Your original code handles a [R] and [p.. R-1] well, but by using R-1 instead of a [R 1.. q]

I can also correct and simplify partitions:

public static  int partition(int a[],int q){
    int  m=a[p]; // not m[0],you want to partition m[p..q]!!!
    while ( p<q){
        while (p<q && a[p] <m){ // don't do p++ here!
            p++;
        }
        while (q>p && a[q]>m){ // don't do q-- here!
            q--;
        }
        int t=a[p];
        a[p]=a[q];
        a[q]=t;
    }
    return p; // no need to search!!!
}

Your original code has irrelevant P and Q - In addition, there is no need to search for the position of the pivot This is where P and Q meet

About naming conventions

Pay attention to Java Naming Conventions:

Related issues

> How is this statement making sense? (Sun’s naming convention for Java variables)

>Unfortunately, the naming convention document above has an obvious error

About array declarations

Also, don't get into the habit of declaring arrays like this:

int x[];

You should use type instead of identifier to place parentheses:

int[] x;

Related issues

> Is there any difference between Object[] x and Object x[] ? > Difference between int[] myArray and int myArray[] in Java > in array declaration int[] k,i and int k[],i

>These declarations lead to different types of I!