Brunobkr/llama.cpp_AlgMor24_github

1import {ascendingDefined, compareDefined} from "./sort.js";2 3// Based on https://github.com/mourner/quickselect4// ISC license, Copyright 2018 Vladimir Agafonkin.5export default function quickselect(array, k, left = 0, right = Infinity, compare) {6  k = Math.floor(k);7  left = Math.floor(Math.max(0, left));8  right = Math.floor(Math.min(array.length - 1, right));9 10  if (!(left <= k && k <= right)) return array;11 12  compare = compare === undefined ? ascendingDefined : compareDefined(compare);13 14  while (right > left) {15    if (right - left > 600) {16      const n = right - left + 1;17      const m = k - left + 1;18      const z = Math.log(n);19      const s = 0.5 * Math.exp(2 * z / 3);20      const sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);21      const newLeft = Math.max(left, Math.floor(k - m * s / n + sd));22      const newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd));23      quickselect(array, k, newLeft, newRight, compare);24    }25 26    const t = array[k];27    let i = left;28    let j = right;29 30    swap(array, left, k);31    if (compare(array[right], t) > 0) swap(array, left, right);32 33    while (i < j) {34      swap(array, i, j), ++i, --j;35      while (compare(array[i], t) < 0) ++i;36      while (compare(array[j], t) > 0) --j;37    }38 39    if (compare(array[left], t) === 0) swap(array, left, j);40    else ++j, swap(array, j, right);41 42    if (j <= k) left = j + 1;43    if (k <= j) right = j - 1;44  }45 46  return array;47}48 49function swap(array, i, j) {50  const t = array[i];51  array[i] = array[j];52  array[j] = t;53}54