Sort Algorithms implementation in javascript with ability to use a comparison callback similar to javascript .sort
.
Implemented Algorithms
Table of Contents
Install
npm install --save sort-algorithms-js
API
require
const {
bubbleSort,
selectionSort,
insertionSort,
radixSort,
heapSort,
quickSort,
mergeSort
} = require('sort-algorithms-js');
import
import {
bubbleSort,
selectionSort,
insertionSort,
radixSort,
heapSort,
quickSort,
mergeSort
} from 'sort-algorithms-js';
Usage
default order is ascending. all algorithms accept a comparison callback as the second param except radix sort which accepts the order as a string "asc" or "desc" and a second param callback to obtain a number value from an object.
Examples
const numbers = [4, 1, 8, 6, -3, -1, 0, 7, -6, 9];
const strings = ['a', 'y', 'i', 'r', 'o', 'w', 'u', 'd', 'e', 'm'];
const objects = [
{ id: 4 }, { id: 1 }, { id: 8 }, { id: 6 }, { id: 3 },
{ id: 2 }, { id: 0 },{ id: 7 }, { id: 5 }, { id: 9 }
];
mergeSort
console.log(mergeSort(numbers));
console.log(mergeSort(strings));
console.log(mergeSort(objects, (a, b) => a.id - b.id));
console.log(mergeSort(numbers, (a, b) => b - a));
console.log(mergeSort(strings, (a, b) => a < b ? 1 : -1));
console.log(mergeSort(objects, (a, b) => b.id - a.id));
radixSort
console.log(radixSort(numbers));
console.log(radixSort(objects, 'asc', (a) => a.id));
console.log(radixSort(numbers, 'desc'));
console.log(radixSort(objects, 'desc', (a) => a.id));
Benchmark
I built a small cmd tool to generate a benchmark for each algorithm on a randomly generated list of numbers.
it takes 3 options:
-s
for the size of the list-a
for the algorithm name-i
the number of iterations. default is 1.
To try it, first install dev deps.
npm install
then, run it for an n randomly generated numbers with the targeted algorithm and an optional number of iterations.
Example
node test/benchmark.js -s 1000 -a bubbleSort -i 5
bubbleSort: 0 seconds 28 ms
bubbleSort: 0 seconds 32 ms
bubbleSort: 0 seconds 17 ms
bubbleSort: 0 seconds 13 ms
bubbleSort: 0 seconds 14 ms
I also generated a benchmark of a larger samples in Node v12, with 10 iterations for each algorithm. Each iteration re-generates a list of numbers with size s.
node test/benchmark.js -s [s] -a [name] -i 10
and I took the best and worst recorded time of each 10 iterations. the result was:
10k numbers |
algorithm | best time | worst time |
quick sort | 0 seconds 2 ms | 0 seconds 11 ms |
javascript .sort() | 0 seconds 4 ms | 0 seconds 13 ms |
merge sort | 0 seconds 3 ms | 0 seconds 20 ms |
radix sort | 0 seconds 3 ms | 0 seconds 44 ms |
selection sort | 5 seconds 316 ms | 14 seconds 836 ms |
insertion sort | 4 seconds 397 ms | 15 seconds 918 ms |
bubble sort | 7 seconds 304 ms | 20 seconds 666 ms |
50k numbers |
algorithm | best time | worst time |
javascript .sort() | 0 seconds 18 ms | 0 seconds 22 ms |
quick sort | 0 seconds 13 ms | 0 seconds 27 ms |
merge sort | 0 seconds 19 ms | 0 seconds 48 ms |
radix sort | 0 seconds 40 ms | 0 seconds 84 ms |
selection sort | 5 seconds 316 ms | 14 seconds 836 ms |
insertion sort | 4 seconds 397 ms | 15 seconds 918 ms |
bubble sort | 7 seconds 304 ms | 20 seconds 666 ms |
100k numbers |
algorithm | best time | worst time |
quick sort | 0 seconds 29 ms | 0 seconds 40 ms |
javascript .sort() | 0 seconds 41 ms | 0 seconds 46 ms |
merge sort | 0 seconds 43 ms | 0 seconds 74 ms |
radix sort | 0 seconds 84 ms | 0 seconds 124 ms |
selection sort | 11 seconds 604 ms | 63 seconds 19 ms |
insertion sort | 19 seconds 370 ms | 70 seconds 463 ms |
bubble sort | 33 seconds 793 ms | 80 seconds 753 ms |
1 million numbers |
algorithm | best time | worst time |
quick sort | 0 seconds 203 ms | 0 seconds 440 ms |
javascript .sort() | 0 seconds 598 ms | 1 seconds 23 ms |
merge sort | 0 seconds 674 ms | 1 seconds 205 ms |
heap sort | 0 seconds 728 ms | 1 seconds 379 ms |
radix sort | 1 seconds 117 ms | 1 seconds 493 ms |
10 million numbers |
algorithm | best time | worst time |
javascript .sort() | 6 seconds 656 ms | 8 seconds 226 ms |
quick sort | 2 seconds 212 ms | 11 seconds 236 ms |
merge sort | 6 seconds 795 ms | 12 seconds 164 ms |
heap sort | 5 seconds 194 ms | 17 seconds 663 ms |
radix sort | 18 seconds 134 ms | 27 seconds 387 ms |
50 million numbers |
algorithm | best time | worst time |
javascript .sort() | 38 seconds 83 ms | 41 seconds 859 ms |
heap sort | 34 seconds 950 ms | 48 seconds 458 ms |
merge sort | 36 seconds 718 ms | 49 seconds 947 ms |
quick sort | 12 seconds 641 ms | 54 seconds 845 ms |
radix sort | ❌ JavaScript heap out of memory |
100 million numbers |
algorithm | best time | worst time |
quick sort | 24 seconds 689 ms | 28 seconds 106 ms |
heap sort | 79 seconds 480 ms | 97 seconds 688 ms |
javascript .sort() | ❌ JavaScript heap out of memory |
merge sort | ❌ JavaScript heap out of memory |
radix sort | ❌ JavaScript heap out of memory |
Build
grunt build
License
The MIT License. Full License is here