1 | /**
|
2 | * Rearrange items in `arr` so that all items in `[left, k]` range are the smallest.
|
3 | * The `k`-th element will have the `(k - left + 1)`-th smallest value in `[left, right]`.
|
4 | *
|
5 | * Implements Floyd-Rivest selection algorithm https://en.wikipedia.org/wiki/Floyd-Rivest_algorithm
|
6 | *
|
7 | * @param {Array<number>} arr input array
|
8 | * @param {number} k pivot index
|
9 | * @param {number} [left] left index
|
10 | * @param {number} [right] right index
|
11 | * @returns {void} mutates input array
|
12 | * @example
|
13 | * var arr = [65, 28, 59, 33, 21, 56, 22, 95, 50, 12, 90, 53, 28, 77, 39];
|
14 | * quickselect(arr, 8);
|
15 | * // = [39, 28, 28, 33, 21, 12, 22, 50, 53, 56, 59, 65, 90, 77, 95]
|
16 | */
|
17 | function quickselect(arr, k, left, right) {
|
18 | left = left || 0;
|
19 | right = right || arr.length - 1;
|
20 |
|
21 | while (right > left) {
|
22 | // 600 and 0.5 are arbitrary constants chosen in the original paper to minimize execution time
|
23 | if (right - left > 600) {
|
24 | const n = right - left + 1;
|
25 | const m = k - left + 1;
|
26 | const z = Math.log(n);
|
27 | const s = 0.5 * Math.exp((2 * z) / 3);
|
28 | let sd = 0.5 * Math.sqrt((z * s * (n - s)) / n);
|
29 | if (m - n / 2 < 0) sd *= -1;
|
30 | const newLeft = Math.max(left, Math.floor(k - (m * s) / n + sd));
|
31 | const newRight = Math.min(
|
32 | right,
|
33 | Math.floor(k + ((n - m) * s) / n + sd)
|
34 | );
|
35 | quickselect(arr, k, newLeft, newRight);
|
36 | }
|
37 |
|
38 | const t = arr[k];
|
39 | let i = left;
|
40 | let j = right;
|
41 |
|
42 | swap(arr, left, k);
|
43 | if (arr[right] > t) swap(arr, left, right);
|
44 |
|
45 | while (i < j) {
|
46 | swap(arr, i, j);
|
47 | i++;
|
48 | j--;
|
49 | while (arr[i] < t) i++;
|
50 | while (arr[j] > t) j--;
|
51 | }
|
52 |
|
53 | if (arr[left] === t) swap(arr, left, j);
|
54 | else {
|
55 | j++;
|
56 | swap(arr, j, right);
|
57 | }
|
58 |
|
59 | if (j <= k) left = j + 1;
|
60 | if (k <= j) right = j - 1;
|
61 | }
|
62 | }
|
63 |
|
64 | function swap(arr, i, j) {
|
65 | const tmp = arr[i];
|
66 | arr[i] = arr[j];
|
67 | arr[j] = tmp;
|
68 | }
|
69 |
|
70 | export default quickselect;
|