Example: FindKthElementQuickSelect in Java

// FindKthElementQuickSelect
import java.util.Arrays;
import java.util.Random;

public class Main {

    // Helper method to swap two elements in an array
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Partition method (similar to QuickSort's partition)
    private static int partition(int[] arr, int low, int high, Random rand) {
        // Choose a random pivot to improve average-case performance
        int pivotIndex = low + rand.nextInt(high - low + 1);
        int pivotValue = arr[pivotIndex];
        swap(arr, pivotIndex, high); // Move pivot to end

        int i = low;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivotValue) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, high); // Move pivot to its final sorted position
        return i;
    }

    // QuickSelect algorithm to find the k-th smallest element
    public static int quickSelect(int[] arr, int low, int high, int k, Random rand) {
        if (low == high) {
            return arr[low];
        }

        int pivotIndex = partition(arr, low, high, rand);

        // If pivot is at the k-th position
        if (k == pivotIndex) {
            return arr[k];
        } else if (k < pivotIndex) {
            // Search in the left partition
            return quickSelect(arr, low, pivotIndex - 1, k, rand);
        } else {
            // Search in the right partition
            return quickSelect(arr, pivotIndex + 1, high, k, rand);
        }
    }

    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 3; // For 3rd smallest

        System.out.println("Original Array: " + Arrays.toString(arr));

        // Find Kth Smallest Element
        int[] arrSmallest = Arrays.copyOf(arr, arr.length); // Use a copy
        Random rand = new Random();
        // k-th smallest element means element at index k-1 in a 0-indexed sorted array
        int kthSmallest = quickSelect(arrSmallest, 0, arrSmallest.length - 1, k - 1, rand);
        System.out.println(k + "th Smallest Element (via QuickSelect): " + kthSmallest);

        // Find Kth Largest Element
        int[] arrLargest = Arrays.copyOf(arr, arr.length); // Use a copy
        // k-th largest element means element at index arr.length - k in a 0-indexed sorted array
        int kthLargest = quickSelect(arrLargest, 0, arrLargest.length - 1, arrLargest.length - k, rand);
        System.out.println(k + "th Largest Element (via QuickSelect): " + kthLargest);
    }
}