public static int findKth(int[] arr, int n, int k) {
return find(arr, 0, n - 1, k);
}
public static int find(int[] arr, int low, int high, int k) {
int partition = getPartition(arr, low, high);
if (partition - low + 1 > k) {
return find(arr, low, partition - 1, k);
}
if (partition - low + 1 < k) {
return find(arr, partition + 1, high, k);
}
return arr[partition];
}
public static int getPartition(int[] arr, int low, int high) {
int key = arr[low];
while(low < high) {
while(low < high && arr[high] <= key) {
high--;
}
arr[low] = arr[high];
while(low < high && arr[low] >= key) {
low++;
}
arr[high] = arr[low];
}
arr[low] = key;
return arr[low];
}