@alvarocastro/quicksort
v1.0.5
Published
An implementation of the quicksort algorithm
Downloads
70
Readme
Quicksort
Yet another implementation of quicksort in JavaScript aimed to be flexible, lightweight and fast.
Install
npm install @alvarocastro/quicksort
Usage
const sort = require('@alvarocastro/quicksort');
const elements = [8, -1, 3, 0.5, 200];
sort(elements);
// => [-1, 0.5, 3, 8, 200]
sort(elements[, compare[, getPivot]])
Returns a new sorted array based on the compare
function criteria.
elements
Type: Array
List of elements to sort.
compare
Type: Function
Default: comparatorAscending
The function to use to compare two elements and find their sorting order. The expected return of the function is:
-1
to sort the element to the left.1
to sort the element to the right.0
when the elements are the same, no sorting is made.
A descending function is also provided in utils.js.
getPivot
Type: Function
Default: pickMiddleValue
The function to use to pick a pivot value from the array. The expected return of the function is one element from the array being sorted.
Performance
Want to test the performance?
Included is the command npm run performance
that will run a battery of profiled tests for your needs.
Here is an example of the output (YMMV depending your hardware)
Sorting random numbers generated in the range [-1,1]:
#1 - 10 numbers
> Quicksort: 1ms
> Array.sort: 0ms
#2 - 100 numbers
> Quicksort: 0ms
> Array.sort: 1ms
#3 - 1000 numbers
> Quicksort: 10ms
> Array.sort: 1ms
#4 - 10000 numbers
> Quicksort: 17ms
> Array.sort: 23ms
#5 - 100000 numbers
> Quicksort: 162ms
> Array.sort: 422ms
#6 - 1000000 numbers
> Quicksort: 1523ms
> Array.sort: 7164ms
More examples
Reverse order
const sort = require('@alvarocastro/quicksort');
const {comparatorDescending} = require('@alvarocastro/quicksort/utils');
const elements = [8, -1, 3, 0.5, 200];
sort(elements, comparatorDescending);
// => [200, 8, 3, 0.5, -1]
Custom elements
const sort = require('@alvarocastro/quicksort');
const elements = [
{name: 'Sarah Connor', firstAppearance: 'The Terminator'},
{name: 'T-800', firstAppearance: 'The Terminator'},
{name: 'Kyle Reese', firstAppearance: 'The Terminator'},
{name: 'John Connor', firstAppearance: 'Terminator 2: Judgement Day'},
{name: 'T-1000', firstAppearance: 'Terminator 2: Judgement Day'}
];
const comparator = function (a, b) {
if (a.name < b.name) {
return -1;
} else if (a.name > b.name) {
return 1;
}
return 0;
};
sort(elements, comparator);
// => [
// {name: 'John Connor', firstAppearance: 'Terminator 2: Judgement Day'},
// {name: 'Kyle Reese', firstAppearance: 'The Terminator'},
// {name: 'Sarah Connor', firstAppearance: 'The Terminator'},
// {name: 'T-800', firstAppearance: 'The Terminator'},
// {name: 'T-1000', firstAppearance: 'Terminator 2: Judgement Day'}
// ]
Contributing
Contributions are always welcome! Please run npm test
beforehand to ensure everything is ok.
Support
If you use this package please consider starring it :)