What is the Quickselect algorithm?

Quickselect is a selection algorithm to find the k-th smallest element in an unordered list. It is related to the Quick Sort sorting algorithm. Its average case time complexity is O(n), with a worst-case of O(n^2).

How is Quickselect different from Quick Sort?

While both use a partitioning strategy, Quick Sort recursively sorts both sides of the pivot. Quickselect, on the other hand, only recurses into the side of the pivot that contains the k-th smallest element, which is why it's more efficient for selection problems.

Selection Algorithms

Quickselect Algorithm

An efficient O(n) average time algorithm for finding the Kth smallest element in an array, based on the same partitioning principle as Quick Sort.

Find Kth Smallest Element

Quickselect uses a recursive approach to find the Kth smallest element by partitioning the array and only processing the part that contains the desired element.

                            function findKthSmallest(nums, k) {
                            return quickselect(nums, 0, nums.length - 1, k - 1);
                            }
                            
                            function quickselect(nums, left, right, k) { /* ... recursive helper ... */ }
                            function partition(nums, left, right) { /* ... partition helper ... */ }
                        

AI Coach Hint: The efficiency of Quickselect heavily depends on the choice of the pivot. A good pivot (like the median) ensures balanced partitions. A consistently bad pivot (always the smallest or largest element) can degrade performance to O(n^2).