@foxkit/sort v1.1.1
Foxkit Sort
This package contains variations of the Quick Sort and Selection Sort algorithms as functions that take a sortBy argument similar to the callback paramter of Array.prototype.sort
.
Installation
yarn add -D @foxkit/sort
Usage
import { qSort } from "@foxkit/sort";
// sort by a <= b
qSort(myArr);
// sort by a.id <= b.id
qSort(myObjs, "id");
// sort using custom callback
qSort(myObjs, (a, b) => b.id - a.id); // descending order
The following algorithms are available:
qSort
: Quick SortqSortDP
: Dual-pivot Quick SortselSort
: Selection Sort
Note: Due to the nature of these algorithms duplicates may appear in random order. You can prevent this with a custom callback function if you have other properties available for comparison.
Callback Function
The callback function may return any number (such as the result of a subtraction) or boolean (return true
if a
should come before b
)
selSort(myObjs, (a, b) => a.id > b.id); // descending order
Stable Quick Sort
Stable variants of qSort
and qSortDP
are available in the /stable
import. These are generally slower by a tiny amount but take the position in the original array into consideration, leading to deterministic results:
import { qSort } from "@foxkit/sort/stable";
const myArr = [
{ v: 3, idx: 0 },
{ v: 1, idx: 1 },
{ v: 7, idx: 2 },
{ v: 3, idx: 3 }
];
qSort(myArr, "v"); /* results in:
[
{ v: 1, idx: 1 },
{ v: 3, idx: 0 },
{ v: 3, idx: 3 },
{ v: 7, idx: 2 }
] */
Benchmarks
The following benchmarks were ran on Node.js 16.15.1 on an AMD Ryzen 5 5600X:
Algorithm | Size 10 | Size 100 | Size 1000 |
---|---|---|---|
Quick Sort | 2,922,624 ops/s | 154,397 ops/s | 9,960 ops/s |
Quick Sort (stable) | 2,849,336 ops/s | 138,888 ops/s | 9,272 ops/s |
Selection Sort | 17,031,188 ops/s | 229,315 ops/s | 3,916 ops/s |
Dual-Pivot Quick Sort | 5,111,350 ops/s | 340,698 ops/s | 19,933 ops/s |
Dual-Pivot Quick Sort (stable) | 4,840,080 ops/s | 314,799 ops/s | 18,580 ops/s |