JavaScript/Data-Structures/Array/QuickSelect.js at master · DrxcoDev/JavaScript · GitHub

History

65 lines (51 loc) · 1.62 KB

Raw

/**

* [QuickSelect](https://www.geeksforgeeks.org/quickselect-algorithm/) 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) {

// eslint-disable-line no-unused-vars

if (kth < 1 || kth > items.length) {

throw new RangeError('Index Out of Bound')

}

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]]

}

export { QuickSelect }

JavaScript/Data-Structures/Array/QuickSelect.js at master · DrxcoDev/JavaScript · GitHub

Expand file tree

Breadcrumbs

QuickSelect.js

Latest commit

History

Breadcrumbs

QuickSelect.js

File metadata and controls