forked from thuva4/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquickselect-javascript.js
More file actions
45 lines (37 loc) · 1.09 KB
/
quickselect-javascript.js
File metadata and controls
45 lines (37 loc) · 1.09 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
//Source: https://stackoverflow.com/questions/38988384/quickselect-into-javascript
function swap(array, idxA, idxB) {
var temp = array[idxA]
array[idxA] = array[idxB]
array[idxB] = temp
}
function partitionStart(arr, left, right) {
var pivotIdx = Math.floor(Math.random() * (right - left + 1)) + left;
var storeIdx = left, pivotVal = arr[pivotIdx]
for (var i = left; i <= right; i++) {
if (arr[i] < pivotVal) {
swap(arr, storeIdx, i)
storeIdx++
}
}
return storeIdx;
}
function quickSelectLoop(arr, k) {
var pivotDist;
var left = 0, right = arr.length - 1;
while(right !== left) {
pivotDist = partitionStart(arr, left, right)
if (k < pivotDist) {
right = pivotDist - 1;
} else {
left = pivotDist;
}
}
return arr[k]
}
//Test
var test2 = [87,32,55,23,389,123,555,657,12378, 12312,3332]
var tmp = [].concat(test2)
tmp.sort(function(a,b) { return a==b ? 0: (a< b? -1: 1)});
for(var x=0;x<test2.length;x++) {
console.log(quickSelectLoop([].concat(test2), x), tmp[x])
}