forked from SiZapPaaiGwat/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquickselect.js
More file actions
67 lines (64 loc) · 1.64 KB
/
Copy pathquickselect.js
File metadata and controls
67 lines (64 loc) · 1.64 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
66
67
(function (exports) {
'use strict';
/**
* Returns the n-th smallest element of list within
* lo..hi inclusive (i.e. lo <= n <= hi).<br><br>
* Time complexity: O(N).
*
* @example
*
* var quickselect = require('path-to-algorithms/src/searching/'+
* 'quickselect').quickselect;
* var result = quickselect([5, 1, 2, 2, 0, 3], 1, 0, 5);
* console.log(result); // 1
*
* @public
* @module searching/quickselect
* @param {Array} arr Input array.
* @param {Number} n A number of an element.
* @param {Number} lo Low index.
* @param {Number} hi High index.
* @return Returns n-th smallest element.
*/
function quickselect(arr, n, lo, hi) {
function partition(arr, lo, hi, pivotIdx) {
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
var pivot = arr[pivotIdx];
swap(arr, pivotIdx, hi);
for (var i = lo; i < hi; i += 1) {
if (arr[i] < pivot) {
swap(arr, i, lo);
lo += 1;
}
}
swap(arr, hi, lo);
return lo;
}
if (arr.length <= n) {
return undefined;
}
lo = lo || 0;
hi = hi || arr.length - 1;
if (lo === hi) {
return arr[lo];
}
while (hi >= lo) {
var pivotIdx =
partition(arr, lo, hi, lo + Math.floor(Math.random() * (hi - lo + 1)));
if (n === pivotIdx) {
return arr[pivotIdx];
}
if (n < pivotIdx) {
hi = pivotIdx - 1;
} else {
lo = pivotIdx + 1;
}
}
return undefined;
}
exports.quickselect = quickselect;
})(typeof window === 'undefined' ? module.exports : window);