1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
/** * Rearrange items in `arr` so that all items in `[left, k]` range are the smallest. * The `k`-th element will have the `(k - left + 1)`-th smallest value in `[left, right]`. * * Implements Floyd-Rivest selection algorithm https://en.wikipedia.org/wiki/Floyd-Rivest_algorithm * * @param {Array<number>} arr input array * @param {number} k pivot index * @param {number} [left] left index * @param {number} [right] right index * @returns {void} mutates input array * @example * var arr = [65, 28, 59, 33, 21, 56, 22, 95, 50, 12, 90, 53, 28, 77, 39]; * quickselect(arr, 8); * // = [39, 28, 28, 33, 21, 12, 22, 50, 53, 56, 59, 65, 90, 77, 95] */function quickselect(arr, k, left, right) {    left = left || 0;    right = right || arr.length - 1;
    while (right > left) {        // 600 and 0.5 are arbitrary constants chosen in the original paper to minimize execution time        if (right - left > 600) {            const n = right - left + 1;            const m = k - left + 1;            const z = Math.log(n);            const s = 0.5 * Math.exp((2 * z) / 3);            let sd = 0.5 * Math.sqrt((z * s * (n - s)) / n);            if (m - n / 2 < 0) sd *= -1;            const newLeft = Math.max(left, Math.floor(k - (m * s) / n + sd));            const newRight = Math.min(                right,                Math.floor(k + ((n - m) * s) / n + sd)            );            quickselect(arr, k, newLeft, newRight);        }
        const t = arr[k];        let i = left;        let j = right;
        swap(arr, left, k);        if (arr[right] > t) swap(arr, left, right);
        while (i < j) {            swap(arr, i, j);            i++;            j--;            while (arr[i] < t) i++;            while (arr[j] > t) j--;        }
        if (arr[left] === t) swap(arr, left, j);        else {            j++;            swap(arr, j, right);        }
        if (j <= k) left = j + 1;        if (k <= j) right = j - 1;    }}
function swap(arr, i, j) {    const tmp = arr[i];    arr[i] = arr[j];    arr[j] = tmp;}
export default quickselect;