Select i-th smallest element from array

Question

I have a divide and conquer method to find the i-th smallest element from an array. Here 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,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;
    }
}

However, when running I get the exception java.lang.ArrayIndexOutOfBoundsException.

Answer 1

I managed to fix some errors. The downside is this line:

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

Instead, you want:

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

This is because you divided it a[p..q]into three parts as follows:

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

Your source code processes arguments a[r]and a[p..r-1], but is placed in a[r+1..q]instead r-1.

---

I was also able to fix and simplify partition:

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

p++ q--. , , , . p q .

---

, Java:

. , , .

• ? ( Suns Java)
  • ,

---

, :

int x[];

, :

int[] x;

• Object[] x Object x[]?
• int[] myArray int myArray[] Java
• int[] k,i int k[],i
  • i!

Answer 2

, , , ( ), i.

public static getIthSmallest(final int[] myArray, final int i) {
    if (i < 0) {
        System.err.println("You're going to get an ArrayIndexOutOfBoundsException.");
    }
    if (i >= myArray.length) {
        System.err.println("You're going to get an ArrayIndexOutOfBoundsException.");
    }
    Arrays.sort(myArray);
    return myArray[i];
}

Answer 3

, ( Java:)

(O(n) average, O(n^2) ) qsort , , . 5 , .

, O(n + log(n)*i*log(i))):

int FindI(int[] array, int i)
{
    int[] tmp = array[0..i].dup; // copy first i elements;

    sort(tmp);                   // sort, low to high

    foreach(j in array[i..$])    // loop over the rest
       if(j < tmp[0])
       {
          tmp[0] = j;
          sort(tmp);
       }
    return tmp[0];
}

Answer 4

, , Quickselect. - .

Answer 5

public static T min (Collection coll, Compator comp) .