Quicksort

Yet another implementation of quicksort in JavaScript aimed to be flexible, lightweight and fast.

• Install
• Usage
• Performance
• More examples
• Contributing
• Support

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 :)