| xenop |
Nov 3rd, 2006 11:50 PM |
Kth smallest array element
Im trying to write a program to find the smalles interger that belongs in the kth element of an array. Im having trouble seeing what im doing wrong and was hoping some one could help me out.Thank You
:
public int kSmallest(int k) {
return kSmallest(k-1, 0, num.length-1);
}
private int kSmallest(int k, int left, int right){
int rtn;
int pivot;
int pivotIndex;
if (right <= left)
rtn = num[left];
else {//partition
pivot = num[(int) Math.random()*(right-left)+left];
pivotIndex = partition(pivot, left, right);
System.out.println("pivot = "+ pivot);
if (k < pivotIndex)
kSmallest(k, left, pivotIndex-1);
else
kSmallest(k, pivotIndex+1, right );
rtn = num[k];
}
return rtn;
}
private int partition(int pivot, int left, int right){
while (left < right){
while (num[left] < pivot) left++;
while (num[right] > pivot) right--;
exch(left,right);
}
return left;
}
private void exch( int i, int j) {
int swap = num[i];
num[i] = num[j];
num[j] = swap;
}
|
