@@ -0,0 +1,1729 @@
+/**%0A * Find the kth smallest element in an unordered array.%0A * %0A * @author Atom%0A * @see %3Ca href=%22https://en.wikipedia.org/wiki/Quickselect%22%3EQuickselect%3C/a%3E%0A */%0Apublic class QuickSelect %7B%0A%09%0A%09/**%0A%09 * Lomuto partition scheme%0A%09 * %0A%09 * @param arr%0A%09 * @param low%0A%09 * @param high%0A%09 * @return the pivot's final location%0A%09 */%0A%09private static %3CT extends Comparable%3C? super T%3E%3E int partition(final T%5B%5D arr, final int low, final int high) %7B%0A%09%09T pivot = arr%5Bhigh%5D;%0A%09%09int index = low;%0A%09%09for (int i = low; i %3C high; i++) %7B%0A%09%09%09if (arr%5Bi%5D.compareTo(pivot) %3C= 0) %7B%0A%09%09%09%09swap(arr, i, index);%0A%09%09%09%09index++;%0A%09%09%09%7D%0A%09%09%7D%0A%09%09swap(arr, index, high);%0A%09%09return index;%0A%09%7D%0A%09%0A%09/**%0A%09 * Find the kth smallest element in an unordered array.%0A%09 * %0A%09 * @param arr%0A%09 * @param kth from 0 to arr.length - 1%0A%09 * @return kth smallest element%0A%09 */%0A%09public static %3CT extends Comparable%3C? super T%3E%3E T select(final T%5B%5D arr, final int kth) %7B%0A%09%09if (kth %3C 0 %7C%7C kth %3E arr.length - 1) throw new IllegalArgumentException(%22elements in the array = %22 + arr.length + %22, kth(0..length-1) = %22 + kth);%0A%09%09%0A%09%09int left = 0;%0A%09%09int right = arr.length - 1;%0A%09%09while (right %3E= left) %7B%0A%09%09%09int pivotIndex = partition(arr, left, right);%0A%09%09%09if (kth == pivotIndex) %7B%0A%09%09%09%09return arr%5BpivotIndex%5D;%0A%09%09%09%7D else if (kth %3C pivotIndex) %7B%0A%09%09%09%09right = pivotIndex - 1;%0A%09%09%09%7D else %7B%0A%09%09%09%09left = pivotIndex + 1;%0A%09%09%09%7D%0A%09%09%7D%0A%09%09return null;%0A%09%7D%0A%09%0A%09private static void swap(Object arr%5B%5D, int i1, int i2) %7B%0A%09%09if (i1 == i2) %7B return; %7D%0A%09%09%0A%09%09Object temp = arr%5Bi1%5D;%0A%09%09arr%5Bi1%5D = arr%5Bi2%5D;%0A%09%09arr%5Bi2%5D = temp;%0A%09%7D%0A%09%0A%09public static void main(String%5B%5D args) %7B%0A%09%09for (int kth = 0; kth %3C 10; kth++) %7B%0A%09%09%09Integer%5B%5D a = %7B 1, 4, 2, 5, 0, 3, 9, 7, 6, 8 %7D;%0A%09%09%09System.out.println(%22kth(%22 + kth + %22) smallest element = %22 + select(a, kth));%0A%09%09%7D%0A%09%7D%0A%0A%7D%0A

Add QuickSelect for Java