import java.util.Arrays;
public class QuickSelect {
// The ideal time complexity is n + n/2 + n/4 + ...=O(n)
// The worst case is n + n-1 + n-2 + ...n - k=O(n * k)
// But in the majority of cases, its efficiency outperform quick sort because it just works
// on certain partitions meanwhile quick sort sorts all the partitions. This reduces the expected
// complexity from O(n log n) to O(n), with a worst case of O(n * k).
public static void main(String[] args) {
int[] a = {90, 90, 67, 3, 3, 8, 43, 89, 90, 90, 1, 4, 5, 7, 5};
a = new int[]{1,2,3,4,5,6};
System.out.println("Before: " + Arrays.toString(a));
int k = 4;
quickSelect(a, 0, a.length - 1, k);
System.out.println("After: " + Arrays.toString(a));
System.out.println("Find " + k + "th smallest " + a[k-1]);
}
private static void quickSelect(int[] a, int left, int right, int k) {
// Narrow down the search scope only stop when it reaches a range only with one element.
if (left == right && left == k - 1) {
return;
}
int pivot = (left + right) / 2;
int i = left;
int j = right;
while (i < j) {
while (i < j && a[i] <= a[pivot]) {
i++;
}
while (i < j && a[j] > a[pivot]) {
j--;
}
// literally, i can not be greater than j
if (i >= j) {
break;
}
swap(a, i, j);
i++;
j--;
}
// k in the left section
if (i > k) {
quickSelect(a, left, i - 1, k);
}
// k in the right section
if (i < k) {
quickSelect(a, i + 1, right, k);
}
}
private static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}