Nascent Personality Manifestation
    Wondering what’s next for npm?Check out our public roadmap! »

    sort-algorithms-js

    3.10.1 • Public • Published

    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 Sort Source Code Wikipedia
    Selection Sort Source Code Wikipedia
    Insertion Sort Source Code Wikipedia
    Radix Sort Source Code Wikipedia
    Heap Sort Source Code Wikipedia
    Quick Sort Source Code Wikipedia
    Merge Sort Source Code Wikipedia

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

    Install

    npm i sort-algorithms-js

    DownloadsWeekly Downloads

    11

    Version

    3.10.1

    License

    MIT

    Unpacked Size

    25.1 kB

    Total Files

    14

    Last publish

    Collaborators

    • avatar