Java Online Compiler
Example: FindKthElementQuickSelect in Java
C
C++
C#
Java
Python
PHP
Main.java
STDIN
Run
// 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); } }
Output
Clear
ADVERTISEMENTS