``````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;
}
}
``````