sort-algorithms (v54)

Revision 54 of this benchmark created on

Description

Comparing native, bubble, insertion, selection, merge, adaptive merge, and quick sort algorithms on a random array.

Preparation HTML

<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/common.js"></script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/bubble-sort.js"></script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/insertion-sort.js"></script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/merge-sort.js"></script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/adaptive-sort.js"></script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/quickmiddle-sort.js"></script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/selection-sort.js"></script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/flashsort.js"></script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/heap-sort.js"></script>
<script src="https://gist.githack.com/anonymous/2ecfead8cf3023258c02/raw/a84a84c784c8ddb25c68bed23d3c5fccc72d9627/DualPivotQuicksort.js"></script>

Setup

// Generate array with random integers.
    var testArrayLength = 5000;
    var unsortedTestArray = new Array(testArrayLength);
    for (var i = 0; i < testArrayLength; i++) {
      unsortedTestArray[i] = Math.floor(Math.random() * testArrayLength);
    }
    var sortedTestArray = unsortedTestArray.clone().sort(function compareNumbers(a, b) {
      return a - b;
    });
    
    function sortLowToHigh(a, b) {
      return a - b;
    }
    
    function shellSort(a) {
      "use strict";
      var N = a.length;
      var h = 1;
      while (h < N / 3) h = 3 * h + 1;
      while (h >= 1) {
        // h-sort the array.
        for (var i = h; i < N; i++) {
          for (var j = i; j >= h && a[j] < a[j - h]; j -= h) {
            var k = a[j];
            a[j] = a[j - h];
            a[j - h] = k;
          }
        }
        h = Math.floor(h / 3);
      }
      return a;
    }
    
    function radixInsert(arr, i, j) {
      tmp = arr[i];
      arr.splice(i, 1);
      arr.splice(j, 0, tmp);
    }
    
    function radixSort(arr) {
      var bit, end, i, mask;
      bit = 0;
      while (true) {
        mask = 1 << bit;
        i = 0;
        end = arr.length;
        while (i < end) {
          if (arr[i] & mask) {
            radixInsert(arr, i, arr.length - 1);
            end--;
          } else {
            i++;
          }
        }
        bit++;
        if (end === arr.length) {
          break;
        }
      }
    }

Teardown


    if (!result.compare(sortedTestArray)) {
      throw new Error("Array was not sorted");
    }

Test runner

Ready to run.

Testing in
TestOps/sec
Native
var result = unsortedTestArray.clone().sort(function(a, b) {
  return a - b;
});
ready
InsertionSort
var result = aij.insertionSort(unsortedTestArray.clone());
ready
Heapsort
var result = aij.heapSort(unsortedTestArray.clone());
ready
AdaptiveSort
var result = aij.adaptiveSort(unsortedTestArray.clone());
ready
MergeSort
var result = aij.mergeSort(unsortedTestArray.clone());
ready
QuickSort
var result = aij.quickmiddleSort(unsortedTestArray.clone());
ready
Flashsort
var result = aij.flashSort(unsortedTestArray.clone());
ready
Shellsort
var result = shellSort(unsortedTestArray.clone());
ready
Dual Pivot QuickSort
var result = DualPivotQuicksort.sort(unsortedTestArray.clone());
ready
LSB Radix Sort
var result = unsortedTestArray.clone()
radixSort(result);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.