sort-algorithms (v19)

Revision 19 of this benchmark created by Eugene Scherba on

Description

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

Preparation HTML

<script>
/**
 * Define "aij" as the global namespace.
 */
var aij = {
    /**
     * Swap the item in index i with the item in index j.
     * @param {Array.<number>} arr The array containing the items.
     * @param {number} i The index of the first swapped item.
     * @param {number} j The index of the second swapped item.
     */
    swap: function(arr, i, j) {
      var swapped = arr[i];
      arr[i] = arr[j];
      arr[j] = swapped;
    },

    /**
     * Verify that an object is an array with more than one element.
     * @param {*} obj The object to verify.
     * @return {boolean} True if the verified object is an array with at least
     *     one element.
     */
    isSortable: function(obj) {
      return obj && toString.call(obj) === '[object Array]' && obj.length > 1;
    }
};
</script>
<script src="https://raw.github.com/escherba/algorithms-in-javascript/master/src/bubble-sort.js">
</script>
<script src="https://raw.github.com/escherba/algorithms-in-javascript/master/src/insertion-sort.js">
</script>
<script src="https://raw.github.com/escherba/algorithms-in-javascript/master/src/merge-sort.js">
</script>
<script src="https://raw.github.com/escherba/algorithms-in-javascript/master/src/adaptive-sort.js">
</script>
<script src="https://raw.github.com/escherba/algorithms-in-javascript/master/src/quick-sort.js">
</script>
<script src="https://raw.github.com/escherba/algorithms-in-javascript/master/src/selection-sort.js">
</script>

Setup

Array.prototype.compare = function (array) {
        // if the other array is a falsy value, return
        if (!array)
            return false;
    
        // compare lengths - can save a lot of time
        if (this.length != array.length)
            return false;
    
        for (var i = 0; i < this.length; i++) {
            // Check if we have nested arrays
            if (this[i] instanceof Array && array[i] instanceof Array) {
                // recurse into the nested arrays
                if (!this[i].compare(array[i]))
                    return false;
            }
            else if (this[i] != array[i]) {
                // Warning - two different object instances will never be equal: {x:20} != {x:20}
                return false;
            }
        }
        return true;
    };
    Array.prototype.clone = function() {
        return this.slice(0);
    };
    
    // Generate array with 10,000 random integers.
    testArrayLength = 10000;
    var unsortedTestArray = new Array(testArrayLength);
    for (var i = 0; i < testArrayLength; i++) {
      unsortedTestArray[i] = Math.floor(Math.random()*100000);
    }
    var sortedTestArray = unsortedTestArray.clone().sort(function compareNumbers(a, b) {
      return a - b;
    });

Teardown


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

Test runner

Ready to run.

Testing in
TestOps/sec
Native
unsortedTestArray.sort(function compareNumbers(a, b) {
  return a - b;
});
ready
BubbleSort
aij.bubbleSort(unsortedTestArray);
ready
InsertionSort
aij.insertionSort(unsortedTestArray);
ready
SelectionSort
aij.selectionSort(unsortedTestArray);
ready
QuickSort
aij.quickSort(unsortedTestArray);
ready
AdaptiveSort
unsortedTestArray = aij.adaptiveSort(unsortedTestArray);
ready
MergeSort
unsortedTestArray = aij.mergeSort(unsortedTestArray);
ready

Revisions

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