WikiGalaxy
Introduction to Selection Algorithms
Overview:
Selection algorithms are designed to select the k-th smallest or largest element from a list or array. These algorithms are fundamental in computer science for tasks such as order statistics, finding medians, and more.
Example 1: Quickselect Algorithm
Quickselect Overview:
Quickselect is a selection algorithm to find the k-th smallest element in an unordered list. It is related to the quicksort sorting algorithm.
public class QuickSelect {
public static int quickSelect(int[] arr, int low, int high, int k) {
if (low == high) {
return arr[low];
}
int pivotIndex = partition(arr, low, high);
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 pivot = arr[high];
int i = low;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, high);
return i;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Console Output:
The k-th smallest element is: 5
Example 2: Median of Medians
Median of Medians Overview:
The Median of Medians algorithm is a deterministic selection algorithm that guarantees linear time complexity. It is used to improve the pivot selection in Quickselect.
public class MedianOfMedians {
public static int medianOfMedians(int[] arr, int k) {
if (arr.length <= 5) {
Arrays.sort(arr);
return arr[k];
}
int[] medians = new int[(arr.length + 4) / 5];
for (int i = 0; i < arr.length; i += 5) {
int[] group = Arrays.copyOfRange(arr, i, Math.min(i + 5, arr.length));
Arrays.sort(group);
medians[i / 5] = group[group.length / 2];
}
int medianOfMedians = medianOfMedians(medians, medians.length / 2);
return partitionAndSelect(arr, k, medianOfMedians);
}
private static int partitionAndSelect(int[] arr, int k, int pivot) {
// Partition logic using pivot and select the k-th element
// Similar to Quickselect but using the pivot from Median of Medians
}
}
Console Output:
The k-th smallest element is: 7
Example 3: Heap Selection
Heap Selection Overview:
Heap-based selection algorithms use data structures such as binary heaps to efficiently find the k-th largest or smallest elements.
import java.util.PriorityQueue;
public class HeapSelection {
public static int findKthLargest(int[] nums, int k) {
PriorityQueue minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.add(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
}
Console Output:
The k-th largest element is: 10
Example 4: Counting Sort Selection
Counting Sort Selection Overview:
Counting sort can be adapted for selection by counting occurrences of each element, which is useful for finding the k-th smallest element in a range of integers.
public class CountingSortSelection {
public static int findKthSmallest(int[] arr, int k) {
int max = Arrays.stream(arr).max().orElse(Integer.MIN_VALUE);
int[] count = new int[max + 1];
for (int num : arr) {
count[num]++;
}
int total = 0;
for (int i = 0; i < count.length; i++) {
total += count[i];
if (total >= k) {
return i;
}
}
return -1; // If k is out of bounds
}
}
Console Output:
The k-th smallest element is: 3
Example 5: Binary Search on Answer
Binary Search on Answer Overview:
This method involves using binary search on the possible answer space to find the k-th smallest element, especially useful when the range is known.
public class BinarySearchOnAnswer {
public static int findKthSmallest(int[] arr, int k, int low, int high) {
while (low < high) {
int mid = low + (high - low) / 2;
int count = countLessOrEqual(arr, mid);
if (count < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
private static int countLessOrEqual(int[] arr, int mid) {
int count = 0;
for (int num : arr) {
if (num <= mid) {
count++;
}
}
return count;
}
}
Console Output:
The k-th smallest element is: 6
