sort-algorithms-js

production-ready sort algorithms implementation in javascript.

Usage no npm install needed!

<script type="module">
  import sortAlgorithmsJs from 'https://cdn.skypack.dev/sort-algorithms-js';
</script>

README

aljs

build:? npm npm npm

Sort Algorithms implementation in javascript with ability to use a comparison callback similar to javascript .sort.

sort

Implemented Algorithms

Bubble SortSource CodeWikipedia
Selection SortSource CodeWikipedia
Insertion SortSource CodeWikipedia
Radix SortSource CodeWikipedia
Heap SortSource CodeWikipedia
Quick SortSource CodeWikipedia
Merge SortSource CodeWikipedia

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
  • asc
console.log(mergeSort(numbers));
// [-6, -3, -1, 0, 1, 4, 6, 7, 8, 9]

console.log(mergeSort(strings));
// ['a', 'd', 'e', 'i', 'm', 'o', 'r', 'u', 'w', 'y']

console.log(mergeSort(objects, (a, b) => a.id - b.id));
// [{ id: 0 }, { id: 1 }, { id: 2 }, { id: 3 }, { id: 4 }, { id: 5 }, { id: 6 }, { id: 7 }, { id: 8 }, { id: 9 }]
  • desc
console.log(mergeSort(numbers, (a, b) => b - a));
// [9, 8, 7, 6, 4, 1, 0, -1, -3, -6]

console.log(mergeSort(strings, (a, b) => a < b ? 1 : -1));
// ['y', 'w', 'u', 'r', 'o', 'm', 'i', 'e', 'd', 'a']

console.log(mergeSort(objects, (a, b) => b.id - a.id));
// [{ id: 9 }, { id: 8 }, { id: 7 }, { id: 6 }, { id: 5 }, { id: 4 }, { id: 3 }, { id: 2 }, { id: 1 }, { id: 0 }]
radixSort
  • asc
console.log(radixSort(numbers));
// [-6, -3, -1, 0, 1, 4, 6, 7, 8, 9]

console.log(radixSort(objects, 'asc', (a) => a.id));
// [{ id: 0 }, { id: 1 }, { id: 2 }, { id: 3 }, { id: 4 }, { id: 5 }, { id: 6 }, { id: 7 }, { id: 8 }, { id: 9 }]
  • desc
console.log(radixSort(numbers, 'desc'));
// [9, 8, 7, 6, 4, 1, 0, -1, -3, -6]

console.log(radixSort(objects, 'desc', (a) => a.id));
// [{ id: 9 }, { id: 8 }, { id: 7 }, { id: 6 }, { id: 5 }, { id: 4 }, { id: 3 }, { id: 2 }, { id: 1 }, { id: 0 }]

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
algorithmbest timeworst time
quick sort0 seconds 2 ms0 seconds 11 ms
javascript .sort()0 seconds 4 ms0 seconds 13 ms
merge sort0 seconds 3 ms0 seconds 20 ms
radix sort0 seconds 3 ms0 seconds 44 ms
selection sort5 seconds 316 ms14 seconds 836 ms
insertion sort4 seconds 397 ms15 seconds 918 ms
bubble sort7 seconds 304 ms20 seconds 666 ms
50k numbers
algorithmbest timeworst time
javascript .sort()0 seconds 18 ms0 seconds 22 ms
quick sort0 seconds 13 ms0 seconds 27 ms
merge sort0 seconds 19 ms0 seconds 48 ms
radix sort0 seconds 40 ms0 seconds 84 ms
selection sort5 seconds 316 ms14 seconds 836 ms
insertion sort4 seconds 397 ms15 seconds 918 ms
bubble sort7 seconds 304 ms20 seconds 666 ms
100k numbers
algorithmbest timeworst time
quick sort0 seconds 29 ms0 seconds 40 ms
javascript .sort()0 seconds 41 ms0 seconds 46 ms
merge sort0 seconds 43 ms0 seconds 74 ms
radix sort0 seconds 84 ms0 seconds 124 ms
selection sort11 seconds 604 ms63 seconds 19 ms
insertion sort19 seconds 370 ms70 seconds 463 ms
bubble sort33 seconds 793 ms80 seconds 753 ms
1 million numbers
algorithmbest timeworst time
quick sort0 seconds 203 ms0 seconds 440 ms
javascript .sort()0 seconds 598 ms1 seconds 23 ms
merge sort0 seconds 674 ms1 seconds 205 ms
heap sort0 seconds 728 ms1 seconds 379 ms
radix sort1 seconds 117 ms1 seconds 493 ms
10 million numbers
algorithmbest timeworst time
javascript .sort()6 seconds 656 ms8 seconds 226 ms
quick sort2 seconds 212 ms11 seconds 236 ms
merge sort6 seconds 795 ms12 seconds 164 ms
heap sort5 seconds 194 ms17 seconds 663 ms
radix sort18 seconds 134 ms27 seconds 387 ms
50 million numbers
algorithmbest timeworst time
javascript .sort()38 seconds 83 ms41 seconds 859 ms
heap sort34 seconds 950 ms48 seconds 458 ms
merge sort36 seconds 718 ms49 seconds 947 ms
quick sort12 seconds 641 ms54 seconds 845 ms
radix sort❌ JavaScript heap out of memory
100 million numbers
algorithmbest timeworst time
quick sort24 seconds 689 ms28 seconds 106 ms
heap sort79 seconds 480 ms97 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