js sorting algorithms (v2)

Revision 2 of this benchmark created on September 2, 2014

Description

Preparation HTML

<script src="//ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js"></script>

Setup

// bubble-sort
    function bswap(i, f, s){
        var t = i[f];
        i[f] = i[s];
        i[s] = t;
    }
    
    function bubbleSort(items){
    
        var len = items.length,
            i, j, stop;
    
        for (i=0; i < len; i++){
            for (j=0, stop=len-i; j < stop; j++){
                if (items[j] > items[j+1]){
                    bswap(items, j, j+1);
                }
            }
        }
    
        return items;
    }
    
    
    
    // insertion-sort
    function insertionSort(items) {
    
        var len     = items.length,
            value,
            i,
            j;
        
        for (i=0; i < len; i++) {
            value = items[i];
    
            for (j=i-1; j > -1 && items[j] > value; j--) {
                items[j+1] = items[j];
            }
    
            items[j+1] = value;
        }
        
        return items;
    }
    
    
    // merge-sort-iterative
    function mergei(left, right){
        var result = [];
    
        while (left.length > 0 && right.length > 0){
            if (left[0] < right[0]){
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
    
        result = result.concat(left).concat(right);
        
        //make sure remaining arrays are empty
        left.splice(0, left.length);
        right.splice(0, right.length);
        
        return result;
    }
    
    function mergeSorti(items){
    
        // Terminal condition - don't need to do anything for arrays with 0 or 1 items
        if (items.length < 2) {
            return items;
        }
    
        var work = [],
            i,
            len;
            
            
        for (i=0, len=items.length; i < len; i++){
            work.push([items[i]]);
        }
        work.push([]);  //in case of odd number of items
    
        for (var lim=len; lim > 1; lim = Math.floor((lim+1)/2)){
            for (var j=0,k=0; k < lim; j++, k+=2){
                work[j] = mergei(work[k], work[k+1]);
            }
            work[j] = [];  //in case of odd number of items
        }
    
        return work[0];
    }
    
    
    // merge-sort-recursive
    function merge(left, right){
        var result  = [],
            il      = 0,
            ir      = 0;
    
        while (il < left.length && ir < right.length){
            if (left[il] < right[ir]){
                result.push(left[il++]);
            } else {
                result.push(right[ir++]);
            }
        }
    
        return result.concat(left.slice(il)).concat(right.slice(ir));
    }
    
    function mergeSort(items){
    
        if (items.length < 2) {
            return items;
        }
    
        var middle = Math.floor(items.length / 2),
            left    = items.slice(0, middle),
            right   = items.slice(middle);
    
        return merge(mergeSort(left), mergeSort(right));
    }
    
    
    
    
    // quicksort
    function qswap(items, firstIndex, secondIndex){
        var temp = items[firstIndex];
        items[firstIndex] = items[secondIndex];
        items[secondIndex] = temp;
    }
    
    function partition(items, left, right) {
    
        var pivot   = items[Math.floor((right + left) / 2)],  // pivot value is middle item
            i       = left,     // starts from left and goes right to pivot index
            j       = right;    // starts from right and goes left to pivot index
    
    
        // while the two indices don't match
        while (i <= j) {
    
            // if the item on the left is less than the pivot, continue right
            while (items[i] < pivot) {
                i++;
            }
    
            // if the item on the right is greater than the pivot, continue left
            while (items[j] > pivot) {
                j--;
            }
    
            // if the two indices still don't match, swap the values
            if (i <= j) {
                qswap(items, i, j);
    
                // change indices to continue loop
                i++;
                j--;
            }
        }
    
        // this value is necessary for recursion
        return i;
    }
    
    function quickSort(items, left, right) {
    
        var index;
    
        // performance - don't sort an array with zero or one items
        if (items.length > 1) {
    
            // fix left and right values - might not be provided
            left = typeof left != "number" ? 0 : left;
            right = typeof right != "number" ? items.length - 1 : right;
    
            // split up the entire array
            index = partition(items, left, right);
    
            // if the returned index
            if (left < index - 1) {
                quickSort(items, left, index - 1);
            }
    
            if (index < right) {
                quickSort(items, index, right);
            }
    
        }
    
        return items;
    }
    
    
    // selection-sort
    function swap(items, firstIndex, secondIndex){
        var temp = items[firstIndex];
        items[firstIndex] = items[secondIndex];
        items[secondIndex] = temp;
    }
     
    /**
     * A selection sort implementation in JavaScript. The array
     * is sorted in-place.
     * @param {Array} items An array of items to sort.
     * @return {Array} The sorted array.
     */
    function selectionSort(items){
    
        var len = items.length,
            min, i, j;
    
        for (i=0; i < len; i++){
        
            // set minimum to this position
            min = i;
            
            // check the rest of the array to see if anything is smaller
            for (j=i+1; j < len; j++){
                if (items[j] < items[min]){
                    min = j;
                }
            }
            
            // if the minimum isn't in the position, swap it
            if (i != min){
                swap(items, i, min);
            }
        }
        
        return items;
    }
    
    function shellSort1(a) {
      for (var h = a.length; h !== 0; h = Math.floor(h / 2)) {
        for (var i = h; i < a.length; i++) {
          var k = a[i];
          for (var j = i; j >= h && k < a[j - h]; j -= h) {
            a[j] = a[j - h];
          }
          a[j] = k;
        }
      }
      return a;
    }
    
    function shellSort2(a) {
      var h = a.length;
      while (h !== 0) {
        for (var i = h; i < a.length; i++) {
          var k = a[i];
          for (var j = i; j >= h && k < a[j - h]; j -= h) {
            a[j] = a[j - h];
          }
          a[j] = k;
        }
        h = Math.floor(h / 2);
      }
      return a;
    }
    
    function getRandomInt(min, max) {
      return Math.floor(Math.random() * (max - min)) + min;
    }
    
    function makeRandomArray(a) {
      var tmpArray = [];
      for (var i = 0; i < 5000; i++) {
        tmpArray.push(getRandomInt(1, 10000).toString());
      }
      return tmpArray;
    }
    
    function small2big(a, b) {
      return a - b;
    }
    var arr = makeRandomArray();

Teardown

    arr = makeRandomArray();
  

Test runner

bubbleSort(arr);

insertionSort(arr);

mergeSorti(arr);

mergeSort(arr);

quickSort(arr);

selectionSort(arr);

arr.sort(small2big);

shellSort1(arr);

shellSort2(arr);

Revisions

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

• Revision 1: published by Bruce Lim on August 31, 2014
• Revision 2: published on September 2, 2014