Select i th smallest element from an array
algorithm, java
Solution
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`!
Problem
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`.