WikiGalaxy
Selection Algorithm Complexity Analysis
Introduction
Selection algorithms are used to select the k-th smallest (or largest) element from a list or array. Understanding their complexity is crucial for optimizing performance, especially in large datasets.
Example 1: Quickselect Algorithm
Quickselect Complexity
Quickselect is an efficient selection algorithm based on the quicksort partitioning method. It has an average time complexity of O(n), but its worst-case complexity is O(n²).
public 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);
}
Example 2: Median of Medians Algorithm
Median of Medians Complexity
The Median of Medians is a deterministic selection algorithm that guarantees linear time complexity O(n) even in the worst case, making it reliable for critical applications.
public int medianOfMedians(int[] arr, int low, int high, int k) {
if (low == high) return arr[low];
int pivotIndex = partitionUsingMedianOfMedians(arr, low, high);
if (k == pivotIndex) return arr[k];
else if (k < pivotIndex) return medianOfMedians(arr, low, pivotIndex - 1, k);
else return medianOfMedians(arr, pivotIndex + 1, high, k);
}
Example 3: Heap Selection
Heap Selection Complexity
Heap selection involves building a heap to extract the k-th smallest element. It has a time complexity of O(n log k), making it efficient for small k values relative to n.
public int heapSelect(int[] arr, int k) {
PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int num : arr) {
maxHeap.add(num);
if (maxHeap.size() > k) maxHeap.poll();
}
return maxHeap.peek();
}
Example 4: Sorting-based Selection
Sorting-based Selection Complexity
This method sorts the array and then selects the k-th element. Its time complexity is O(n log n), which can be inefficient compared to other methods for large datasets.
public int sortSelect(int[] arr, int k) {
Arrays.sort(arr);
return arr[k];
}
Example 5: Randomized Selection
Randomized Selection Complexity
Randomized selection improves Quickselect by randomizing the pivot choice, reducing the chance of worst-case scenarios. The average time complexity remains O(n).
public int randomizedSelect(int[] arr, int low, int high, int k) {
if (low == high) return arr[low];
int pivotIndex = randomPartition(arr, low, high);
if (k == pivotIndex) return arr[k];
else if (k < pivotIndex) return randomizedSelect(arr, low, pivotIndex - 1, k);
else return randomizedSelect(arr, pivotIndex + 1, high, k);
}
