WikiGalaxy
WikiGalaxy💙Blue💛🌹
Personalize
Quick Select Algorithm
Introduction
The Quick Select algorithm is a selection algorithm to find the k-th smallest element in an unordered list. It is related to the Quick Sort sorting algorithm, utilizing the partitioning method to efficiently locate the desired element without fully sorting the list.
Algorithm Steps
Step 1: Choose a pivot element from the array.
Step 2: Partition the array into two halves. Elements less than the pivot are moved to its left, and elements greater than the pivot to its right.
Step 3: Recursively apply the process to the half that contains the k-th smallest element.
Example 1: Finding the 3rd Smallest Element
Consider the array [7, 10, 4, 3, 20, 15]. We want to find the 3rd smallest element.
import java.util.Random;
class QuickSelect {
public static int quickSelect(int[] arr, int low, int high, int k) {
if (low == high) return arr[low];
Random rand = new Random();
int pivotIndex = low + rand.nextInt(high - low + 1);
pivotIndex = partition(arr, low, high, pivotIndex);
if (k == pivotIndex) return arr[k];
else if (k < pivotIndex) return quickSelect(arr, low, pivotIndex - 1, k);
else return quickSelect(arr, pivotIndex + 1, high, k);
}
private static int partition(int[] arr, int low, int high, int pivotIndex) {
int pivotValue = arr[pivotIndex];
swap(arr, pivotIndex, high);
int storeIndex = low;
for (int i = low; i < high; i++) {
if (arr[i] < pivotValue) {
swap(arr, storeIndex, i);
storeIndex++;
}
}
swap(arr, high, storeIndex);
return storeIndex;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {7, 10, 4, 3, 20, 15};
int k = 2; // 3rd smallest, index 2
System.out.println("3rd smallest element is " + quickSelect(arr, 0, arr.length - 1, k));
}
}
Console Output:
3rd smallest element is 7
Example 2: Finding the Largest Element
In the array [3, 2, 1, 5, 6, 4], find the largest element.
public class QuickSelectLargest {
public static int findLargest(int[] nums) {
int n = nums.length;
return quickSelect(nums, 0, n - 1, n - 1);
}
// Quick Select implementation
private static int quickSelect(int[] nums, int low, int high, int k) {
if (low == high) return nums[low];
Random rand = new Random();
int pivotIndex = low + rand.nextInt(high - low + 1);
pivotIndex = partition(nums, low, high, pivotIndex);
if (k == pivotIndex) return nums[k];
else if (k < pivotIndex) return quickSelect(nums, low, pivotIndex - 1, k);
else return quickSelect(nums, pivotIndex + 1, high, k);
}
private static int partition(int[] nums, int low, int high, int pivotIndex) {
int pivotValue = nums[pivotIndex];
swap(nums, pivotIndex, high);
int storeIndex = low;
for (int i = low; i < high; i++) {
if (nums[i] < pivotValue) {
swap(nums, storeIndex, i);
storeIndex++;
}
}
swap(nums, high, storeIndex);
return storeIndex;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
int[] nums = {3, 2, 1, 5, 6, 4};
System.out.println("Largest element is " + findLargest(nums));
}
}
Console Output:
Largest element is 6
Example 3: Finding the Median
To find the median of an array [12, 3, 5, 7, 4, 19, 26], use the Quick Select algorithm.
public class QuickSelectMedian {
public static int findMedian(int[] nums) {
int n = nums.length;
int mid = n / 2;
if (n % 2 == 1) {
return quickSelect(nums, 0, n - 1, mid);
} else {
return (quickSelect(nums, 0, n - 1, mid - 1) + quickSelect(nums, 0, n - 1, mid)) / 2;
}
}
// Quick Select implementation
private static int quickSelect(int[] nums, int low, int high, int k) {
if (low == high) return nums[low];
Random rand = new Random();
int pivotIndex = low + rand.nextInt(high - low + 1);
pivotIndex = partition(nums, low, high, pivotIndex);
if (k == pivotIndex) return nums[k];
else if (k < pivotIndex) return quickSelect(nums, low, pivotIndex - 1, k);
else return quickSelect(nums, pivotIndex + 1, high, k);
}
private static int partition(int[] nums, int low, int high, int pivotIndex) {
int pivotValue = nums[pivotIndex];
swap(nums, pivotIndex, high);
int storeIndex = low;
for (int i = low; i < high; i++) {
if (nums[i] < pivotValue) {
swap(nums, storeIndex, i);
storeIndex++;
}
}
swap(nums, high, storeIndex);
return storeIndex;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
int[] nums = {12, 3, 5, 7, 4, 19, 26};
System.out.println("Median is " + findMedian(nums));
}
}
Console Output:
Median is 7
Example 4: Finding the 2nd Largest Element
In the array [7, 10, 4, 3, 20, 15], find the 2nd largest element.
public class QuickSelectSecondLargest {
public static int findSecondLargest(int[] nums) {
int n = nums.length;
return quickSelect(nums, 0, n - 1, n - 2);
}
// Quick Select implementation
private static int quickSelect(int[] nums, int low, int high, int k) {
if (low == high) return nums[low];
Random rand = new Random();
int pivotIndex = low + rand.nextInt(high - low + 1);
pivotIndex = partition(nums, low, high, pivotIndex);
if (k == pivotIndex) return nums[k];
else if (k < pivotIndex) return quickSelect(nums, low, pivotIndex - 1, k);
else return quickSelect(nums, pivotIndex + 1, high, k);
}
private static int partition(int[] nums, int low, int high, int pivotIndex) {
int pivotValue = nums[pivotIndex];
swap(nums, pivotIndex, high);
int storeIndex = low;
for (int i = low; i < high; i++) {
if (nums[i] < pivotValue) {
swap(nums, storeIndex, i);
storeIndex++;
}
}
swap(nums, high, storeIndex);
return storeIndex;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
int[] nums = {7, 10, 4, 3, 20, 15};
System.out.println("2nd largest element is " + findSecondLargest(nums));
}
}
Console Output:
2nd largest element is 15
Example 5: Finding the 5th Smallest Element
For the array [10, 4, 5, 8, 6, 11, 26], determine the 5th smallest element using Quick Select.
public class QuickSelectFifthSmallest {
public static int findFifthSmallest(int[] nums) {
return quickSelect(nums, 0, nums.length - 1, 4);
}
// Quick Select implementation
private static int quickSelect(int[] nums, int low, int high, int k) {
if (low == high) return nums[low];
Random rand = new Random();
int pivotIndex = low + rand.nextInt(high - low + 1);
pivotIndex = partition(nums, low, high, pivotIndex);
if (k == pivotIndex) return nums[k];
else if (k < pivotIndex) return quickSelect(nums, low, pivotIndex - 1, k);
else return quickSelect(nums, pivotIndex + 1, high, k);
}
private static int partition(int[] nums, int low, int high, int pivotIndex) {
int pivotValue = nums[pivotIndex];
swap(nums, pivotIndex, high);
int storeIndex = low;
for (int i = low; i < high; i++) {
if (nums[i] < pivotValue) {
swap(nums, storeIndex, i);
storeIndex++;
}
}
swap(nums, high, storeIndex);
return storeIndex;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
int[] nums = {10, 4, 5, 8, 6, 11, 26};
System.out.println("5th smallest element is " + findFifthSmallest(nums));
}
}
Console Output:
5th smallest element is 10
