f-sort
v1.0.3
Published
A fast, small (~0.5 KB gzipped) and dependency-free JavaScript library to sort arrays. It uses quick sort internally to sort arrays _in place_, without recursion. Simply replace JavaScript's built-in `Array.prototype.sort` with f-sort's `sort` to see ~2x
Downloads
18
Maintainers
Readme
f-sort
A fast, small (~0.5 KB gzipped) and dependency-free JavaScript library to sort arrays. It uses quick sort internally to sort arrays in place, without recursion. Simply replace JavaScript's built-in Array.prototype.sort
with f-sort's sort
to see ~2x performance. This is especially for helpful for large arrays.
The cherry on top of the cake - it sorts numbers in the increasing order of value, out of the box, something that can not be said for JavaScript's native sort method :)
Installation
npm install f-sort
#OR
yarn add f-sort
API Reference
sort()
Definition:
sort(
array: any[], // required
comparator?: function, // optional
pivotExtractor?: function // optional
) -> any[]
Parameters
array: any[]
| Required | The array that will be sorted in place.comparator: function(a: any, b: any) -> Number
| Optional | A function used to compare two elements of the array. The function is passed two elements of the array, and it should return a number denoting the comparison of the two elements -comparator(a, b) < 0
-a < b
comparator(a, b) === 0
-a === b
comparator(a, b) > 0
-a > b
Default value
(a, b) => a - b;
This default comparator sorts the array in increasing order if it comprises of numbers.
Provided comparator
f-sort
provides 2 comparators out of the box -ascNumberComparator
- Sorts numbers in ascending order (default comparator)descNumberComparator
- Sorts numbers in descending order
These can be imported as -
import { comparators } from "f-sort";
And used as
sort(arr, comparators.ascNumberComparator); // ascending order sort(arr, comparators.descNumberComparator); // descending order
pivotExtractor: function(arr: any[], left: Number, right: Number) -> Number
| Optional | A function that returns the pivot to partition the array between left (inclusive) and right (exclusive) indices. This parameter is exposed for more advance uses - the default value works for most cases. The returned pivot must be in the range in the following range -left <= pivot < right
>Default value
The default pivot extractor returns the middle element of the range between
left
andright
.// Return the index between left and right // Same as Math.floor((left + right) / 2), but faster. (arr, left, right) => (left + right) >>> 1;
The
pivotExtractor
argument can be used to implement more advanced pivot selection techniques like quick select.Provided pivotExtractors
f-sort
provides 4 pivot extractors out of the box -mid
- Returns the middle index of the range as the pivot (Default)first
- Returns the first index of the range (left) as the pivotlast
- Returns the last index of the range (right - 1) as the pivotrandom
- Returns a random index in the range left to right - 1
These can be import as -
import { pivotExtractors } from "f-sort";
And used as
sort(arr, undefined, pivotExtractors.mid); sort(arr, undefined, pivotExtractors.first); sort(arr, undefined, pivotExtractors.last); sort(arr, undefined, pivotExtractors.random);
Usage and examples
Import the sort function from f-sort, and simply pass the array to sort. The function does not create a copy of the array, and sorts it in-place, and returns the sorted array.
import { sort } from "f-sort";
const arr = [-1, 1, 100, 20000, 8];
const sortedArr = sort(arr);
console.log("sortedArr:", sortedArr);
console.log("arr:", arr);
The following code outputs -
arr: [ -1, 1, 8, 100, 20000 ]
sortedArr: [ -1, 1, 8, 100, 20000 ]
Notice, the returned array is just a reference to the array passed into the function. If you wish to make a sorted copy of the array, clone the array before passing it into sort, like so -
import { sort } from "f-sort";
const arr = [-1, 1, 100, 20000, 8];
const sortedArr = [...arr];
sort(sortedArr);
console.log(sortedArr);
console.log(arr);
The following code outputs -
arr: [ -1, 1, 100, 20000, 8 ]
sortedArr: [ -1, 1, 8, 100, 20000 ]
Using a comparator
A comparator can be passed to sort()
to help sort the array in a custom order, or to sort incomparable types, like objects.
Sorting numbers by the squares of their values
const arr = [-2, 1, 2, -3]; sort(arr, (a, b) => a * a - b * b); console.log("arr:", arr);
The following snippet outputs -
arr: [ 1, 2, -2, -3 ]
Sorting an array of objects, of the shape -
{ x: Number, y: Number };
The following snippet sorts an array of such objects by the value of their
x
property.const arr = [ { x: 100, y: 21 }, { x: -50, y: 1000 }, { x: 99, y: 100 }, { x: 200, y: -100 }, ]; sort(arr, (a, b) => a.x - b.x); console.log("arr:", arr);
The following code outputs -
arr: [ { x: -50, y: 1000 }, { x: 99, y: 100 }, { x: 100, y: 21 }, { x: 200, y: -100 } ]