1 | /**
|
2 | * Efficient sort implementations.
|
3 | *
|
4 | * Note: These sort implementations were created to compare different sorting algorithms in JavaScript.
|
5 | * Don't use them if you don't know what you are doing. Native Array.sort is almost always a better choice.
|
6 | *
|
7 | * @module sort
|
8 | */
|
9 |
|
10 | import * as math from './math.js'
|
11 |
|
12 | /**
|
13 | * @template T
|
14 | * @param {Array<T>} arr
|
15 | * @param {number} lo
|
16 | * @param {number} hi
|
17 | * @param {function(T,T):number} compare
|
18 | */
|
19 | export const _insertionSort = (arr, lo, hi, compare) => {
|
20 | for (let i = lo + 1; i <= hi; i++) {
|
21 | for (let j = i; j > 0 && compare(arr[j - 1], arr[j]) > 0; j--) {
|
22 | const tmp = arr[j]
|
23 | arr[j] = arr[j - 1]
|
24 | arr[j - 1] = tmp
|
25 | }
|
26 | }
|
27 | }
|
28 |
|
29 | /**
|
30 | * @template T
|
31 | * @param {Array<T>} arr
|
32 | * @param {function(T,T):number} compare
|
33 | * @return {void}
|
34 | */
|
35 | export const insertionSort = (arr, compare) => {
|
36 | _insertionSort(arr, 0, arr.length - 1, compare)
|
37 | }
|
38 |
|
39 | /**
|
40 | * @template T
|
41 | * @param {Array<T>} arr
|
42 | * @param {number} lo
|
43 | * @param {number} hi
|
44 | * @param {function(T,T):number} compare
|
45 | */
|
46 | const _quickSort = (arr, lo, hi, compare) => {
|
47 | if (hi - lo < 42) {
|
48 | _insertionSort(arr, lo, hi, compare)
|
49 | } else {
|
50 | const pivot = arr[math.floor((lo + hi) / 2)]
|
51 | let i = lo
|
52 | let j = hi
|
53 | while (true) {
|
54 | while (compare(pivot, arr[i]) > 0) {
|
55 | i++
|
56 | }
|
57 | while (compare(arr[j], pivot) > 0) {
|
58 | j--
|
59 | }
|
60 | if (i >= j) {
|
61 | break
|
62 | }
|
63 | // swap arr[i] with arr[j]
|
64 | // and increment i and j
|
65 | const arri = arr[i]
|
66 | arr[i++] = arr[j]
|
67 | arr[j--] = arri
|
68 | }
|
69 | _quickSort(arr, lo, j, compare)
|
70 | _quickSort(arr, j + 1, hi, compare)
|
71 | }
|
72 | }
|
73 |
|
74 | /**
|
75 | * This algorithm beats Array.prototype.sort in Chrome only with arrays with 10 million entries.
|
76 | * In most cases [].sort will do just fine. Make sure to performance test your use-case before you
|
77 | * integrate this algorithm.
|
78 | *
|
79 | * Note that Chrome's sort is now a stable algorithm (Timsort). Quicksort is not stable.
|
80 | *
|
81 | * @template T
|
82 | * @param {Array<T>} arr
|
83 | * @param {function(T,T):number} compare
|
84 | * @return {void}
|
85 | */
|
86 | export const quicksort = (arr, compare) => {
|
87 | _quickSort(arr, 0, arr.length - 1, compare)
|
88 | }
|