| 110544 | var _ascendingJs = require("./ascending.js"); |
| 110545 | var _ascendingJsDefault = parcelHelpers.interopDefault(_ascendingJs); |
| 110546 | function quickselect(array, k, left = 0, right = array.length - 1, compare = (0, _ascendingJsDefault.default)) { |
| 110547 | while(right > left){ |
| 110548 | if (right - left > 600) { |
| 110549 | const n = right - left + 1; |
| 110550 | const m = k - left + 1; |
| 110551 | const z = Math.log(n); |
| 110552 | const s = 0.5 * Math.exp(2 * z / 3); |
| 110553 | const sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1); |
| 110554 | const newLeft = Math.max(left, Math.floor(k - m * s / n + sd)); |
| 110555 | const newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd)); |
| 110556 | quickselect(array, k, newLeft, newRight, compare); |
| 110557 | } |
| 110558 | const t = array[k]; |
| 110559 | let i = left; |
| 110560 | let j = right; |
| 110561 | swap(array, left, k); |
| 110562 | if (compare(array[right], t) > 0) swap(array, left, right); |
| 110563 | while(i < j){ |
| 110564 | swap(array, i, j), ++i, --j; |
| 110565 | while(compare(array[i], t) < 0)++i; |
| 110566 | while(compare(array[j], t) > 0)--j; |
| 110567 | } |
| 110568 | if (compare(array[left], t) === 0) swap(array, left, j); |
| 110569 | else ++j, swap(array, j, right); |
| 110570 | if (j <= k) left = j + 1; |
| 110571 | if (k <= j) right = j - 1; |
| 110572 | } |
| 110573 | return array; |
| 110574 | } |
| 110575 | exports.default = quickselect; |
| 110576 | function swap(array, i, j) { |
| 110577 | const t = array[i]; |