Quick Select Algorithm
The Quick Select Algorithm is an efficient selection algorithm that is used to find the k-th smallest element in an unordered list. It is an in-place algorithm, meaning that it doesn't require any additional memory to be allocated apart from input list space. The algorithm was developed by Tony Hoare, the same computer scientist who created the Quick Sort algorithm. Similar to Quick Sort, the Quick Select Algorithm is also based on the divide-and-conquer paradigm, using the concept of partitioning the elements of the input list.
In the Quick Select Algorithm, a pivot element is chosen from the input list, and the list is partitioned around this pivot element. The partitioning step rearranges the list such that all elements smaller than the pivot are placed before the pivot, and all elements greater than the pivot are placed after it. At this point, the pivot is at its final sorted position in the list. Depending on the position of the pivot and the value of k, the algorithm may recurse on either the left partition (if k is less than the pivot position) or the right partition (if k is greater than the pivot position). This process is repeated until the k-th smallest element is found. The average-case time complexity of the Quick Select Algorithm is O(n), making it an efficient choice for finding the k-th smallest element in large datasets.
/**
* QuickSelect is an algorithm to find the kth smallest number
*
* Notes:
* -QuickSelect is related to QuickSort, thus has optimal best and average
* case (O(n)) but unlikely poor worst case (O(n^2))
* -This implementation uses randomly selected pivots for better performance
*
* @complexity: O(n) (on average )
* @complexity: O(n^2) (worst case)
* @flow
*/
function QuickSelect (items, kth) {
return RandomizedSelect(items, 0, items.length - 1, kth)
}
function RandomizedSelect (
items,
left,
right,
i
) {
if (left === right) return items[left]
const pivotIndex = RandomizedPartition(items, left, right)
const k = pivotIndex - left + 1
if (i === k) return items[pivotIndex]
if (i < k) return RandomizedSelect(items, left, pivotIndex - 1, i)
return RandomizedSelect(items, pivotIndex + 1, right, i - k)
}
function RandomizedPartition (items, left, right) {
const rand = getRandomInt(left, right)
Swap(items, rand, right)
return Partition(items, left, right)
}
function Partition (items, left, right) {
const x = items[right]
let pivotIndex = left - 1
for (let j = left; j < right; j++) {
if (items[j] <= x) {
pivotIndex++
Swap(items, pivotIndex, j)
}
}
Swap(items, pivotIndex + 1, right)
return pivotIndex + 1
}
function getRandomInt (min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min
}
function Swap (arr, x, y) {
[arr[x], arr[y]] = [arr[y], arr[x]]
}
// testing
console.log(QuickSelect([1, 4, 2, -2, 4, 5]))
