forked from TheAlgorithms/JavaScript
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSelect.js
More file actions
65 lines (51 loc) · 1.62 KB
/
QuickSelect.js
File metadata and controls
65 lines (51 loc) · 1.62 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
* [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 }