| 1 | {"version":3,"file":"sort-b8702761.cjs","sources":["../sort.js"],"sourcesContent":["/**\n * Efficient sort implementations.\n *\n * Note: These sort implementations were created to compare different sorting algorithms in JavaScript.\n * Don't use them if you don't know what you are doing. Native Array.sort is almost always a better choice.\n *\n * @module sort\n */\n\nimport * as math from './math.js'\n\n/**\n * @template T\n * @param {Array<T>} arr\n * @param {number} lo\n * @param {number} hi\n * @param {function(T,T):number} compare\n */\nexport const _insertionSort = (arr, lo, hi, compare) => {\n for (let i = lo + 1; i <= hi; i++) {\n for (let j = i; j > 0 && compare(arr[j - 1], arr[j]) > 0; j--) {\n const tmp = arr[j]\n arr[j] = arr[j - 1]\n arr[j - 1] = tmp\n }\n }\n}\n\n/**\n * @template T\n * @param {Array<T>} arr\n * @param {function(T,T):number} compare\n * @return {void}\n */\nexport const insertionSort = (arr, compare) => {\n _insertionSort(arr, 0, arr.length - 1, compare)\n}\n\n/**\n * @template T\n * @param {Array<T>} arr\n * @param {number} lo\n * @param {number} hi\n * @param {function(T,T):number} compare\n */\nconst _quickSort = (arr, lo, hi, compare) => {\n if (hi - lo < 42) {\n _insertionSort(arr, lo, hi, compare)\n } else {\n const pivot = arr[math.floor((lo + hi) / 2)]\n let i = lo\n let j = hi\n while (true) {\n while (compare(pivot, arr[i]) > 0) {\n i++\n }\n while (compare(arr[j], pivot) > 0) {\n j--\n }\n if (i >= j) {\n break\n }\n // swap arr[i] with arr[j]\n // and increment i and j\n const arri = arr[i]\n arr[i++] = arr[j]\n arr[j--] = arri\n }\n _quickSort(arr, lo, j, compare)\n _quickSort(arr, j + 1, hi, compare)\n }\n}\n\n/**\n * This algorithm beats Array.prototype.sort in Chrome only with arrays with 10 million entries.\n * In most cases [].sort will do just fine. Make sure to performance test your use-case before you\n * integrate this algorithm.\n *\n * Note that Chrome's sort is now a stable algorithm (Timsort). Quicksort is not stable.\n *\n * @template T\n * @param {Array<T>} arr\n * @param {function(T,T):number} compare\n * @return {void}\n */\nexport const quicksort = (arr, compare) => {\n _quickSort(arr, 0, arr.length - 1, compare)\n}\n"],"names":["math.floor"],"mappings":";;;;AAAA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AAGA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACY,MAAC,cAAc,GAAG,CAAC,GAAG,EAAE,EAAE,EAAE,EAAE,EAAE,OAAO,KAAK;AACxD,EAAE,KAAK,IAAI,CAAC,GAAG,EAAE,GAAG,CAAC,EAAE,CAAC,IAAI,EAAE,EAAE,CAAC,EAAE,EAAE;AACrC,IAAI,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,IAAI,OAAO,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,EAAE,GAAG,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE,EAAE;AACnE,MAAM,MAAM,GAAG,GAAG,GAAG,CAAC,CAAC,EAAC;AACxB,MAAM,GAAG,CAAC,CAAC,CAAC,GAAG,GAAG,CAAC,CAAC,GAAG,CAAC,EAAC;AACzB,MAAM,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,IAAG;AACtB,KAAK;AACL,GAAG;AACH,EAAC;AACD;AACA;AACA;AACA;AACA;AACA;AACA;AACY,MAAC,aAAa,GAAG,CAAC,GAAG,EAAE,OAAO,KAAK;AAC/C,EAAE,cAAc,CAAC,GAAG,EAAE,CAAC,EAAE,GAAG,CAAC,MAAM,GAAG,CAAC,EAAE,OAAO,EAAC;AACjD,EAAC;AACD;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA,MAAM,UAAU,GAAG,CAAC,GAAG,EAAE,EAAE,EAAE,EAAE,EAAE,OAAO,KAAK;AAC7C,EAAE,IAAI,EAAE,GAAG,EAAE,GAAG,EAAE,EAAE;AACpB,IAAI,cAAc,CAAC,GAAG,EAAE,EAAE,EAAE,EAAE,EAAE,OAAO,EAAC;AACxC,GAAG,MAAM;AACT,IAAI,MAAM,KAAK,GAAG,GAAG,CAACA,UAAU,CAAC,CAAC,EAAE,GAAG,EAAE,IAAI,CAAC,CAAC,EAAC;AAChD,IAAI,IAAI,CAAC,GAAG,GAAE;AACd,IAAI,IAAI,CAAC,GAAG,GAAE;AACd,IAAI,OAAO,IAAI,EAAE;AACjB,MAAM,OAAO,OAAO,CAAC,KAAK,EAAE,GAAG,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,EAAE;AACzC,QAAQ,CAAC,GAAE;AACX,OAAO;AACP,MAAM,OAAO,OAAO,CAAC,GAAG,CAAC,CAAC,CAAC,EAAE,KAAK,CAAC,GAAG,CAAC,EAAE;AACzC,QAAQ,CAAC,GAAE;AACX,OAAO;AACP,MAAM,IAAI,CAAC,IAAI,CAAC,EAAE;AAClB,QAAQ,KAAK;AACb,OAAO;AACP;AACA;AACA,MAAM,MAAM,IAAI,GAAG,GAAG,CAAC,CAAC,EAAC;AACzB,MAAM,GAAG,CAAC,CAAC,EAAE,CAAC,GAAG,GAAG,CAAC,CAAC,EAAC;AACvB,MAAM,GAAG,CAAC,CAAC,EAAE,CAAC,GAAG,KAAI;AACrB,KAAK;AACL,IAAI,UAAU,CAAC,GAAG,EAAE,EAAE,EAAE,CAAC,EAAE,OAAO,EAAC;AACnC,IAAI,UAAU,CAAC,GAAG,EAAE,CAAC,GAAG,CAAC,EAAE,EAAE,EAAE,OAAO,EAAC;AACvC,GAAG;AACH,EAAC;AACD;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACY,MAAC,SAAS,GAAG,CAAC,GAAG,EAAE,OAAO,KAAK;AAC3C,EAAE,UAAU,CAAC,GAAG,EAAE,CAAC,EAAE,GAAG,CAAC,MAAM,GAAG,CAAC,EAAE,OAAO,EAAC;AAC7C;;;;;;;;;;;;;;"} |