Quickselect.md (1322B)
1 # Quickselect 2 3 **Source:** Competitive Programmer's Handbook Ch 24.5 4 5 **Definition:** Quickselect is a Las Vegas method stochastic algorithm with O($n^2$) worst case asymptotic time complexity and O($n$) average case asymptotic time complexity used for the selection of the $k$th smallest element in an unordered collection, also referred to as the $k$th order statistic. 6 7 ## Procedure 8 9 1. Select a random pivot 10 2. Swap pivot with the righmost elment 11 3. Partition the subarray 12 4. Move the pivot into its final sorted position 13 5. Compare the pivot index with the target index 14 - if pivot index == index, return the pivot 15 - if index < pivot index, recurse left subarray 16 - if index > pivot index, recurse right subarray 17 18 ## Complexity 19 20 When we select an arbitrary element of the array as the pivot we expect to perform ~n operations because we check if each element is > or < the current element. On the next iteration, we expect to perform $\frac{n}{2}$ operations. This continues on, and we note we expect this sum to be <2n. This gives us our O(n) average case time complexity. 21 22 For the worst case asymptotic time complexity, notice we may select the highest element of the array every time, requiring n, n-1, n-2, ... operations at each step. This gives us a worst case asymptotic time complexity of O($n^2$).