Select i th smallest element from an 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, I get an exception when run: java.lang.ArrayIndexOutOfBoundsException.

Answer 1

No clue what your bug is (I dislike Java :)

The simple solution (O(n) average, O(n^2) worst case) to this problem is copy the source to a nice simple implementation of qsort and make it only recurse on the side that contains the position you care about. It should be about 5 lines of code different so it should be easy to do.

If i is small there is a O(n + log(n)*i*log(i)) solution):

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 2

Assuming this isn't homework where you need do it this way, and it's not in the critical path (which is a likely guess), just sort the array and grab the value at index 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

You can use public static T min(Collection coll, Comparator comp) in Collections.

Answer 4

I was able to fix a few bugs. A minor one is this line:

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

Instead, you want this:

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

That's because you have partitioned a[p..q] into three parts as follows:

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

Your original code handles the a[r] and a[p..r-1] case fine, but messes up on the a[r+1..q] by using r-1 instead.

---

I was also able to correct 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!!!
}

Your original code had extraneous p++ and q--. Also, the search for where the pivot is is unnecessary. It's where p and q meet.

---

On naming conventions

Please follow Java naming conventions:

Class names should be nouns, in mixed case with the first letter of each internal word capitalized. Methods should be verbs, in mixed case with the first letter lowercase, with the first letter of each internal word capitalized.

Related questions

• How is this statement making sense? (Sun’s naming convention for Java variables)
  • Unfortunately the naming convention document above has one glaring error

---

On array declarations

Also, do not make a habit of declaring arrays like this:

int x[];

You should instead put the brackets with the type, rather than with the identifier:

int[] x;

Related questions

• 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 result in different types for i!

Answer 5

The algorithm you're attempting to implement is called Quickselect. Here is a link to working code using a median-of-three partitioning strategy.