Sort Algorithm Sandbox (js)

sort-algorithm-sandbox.js

/**
 * A Quick Set of Sort Algorithms Expirements
 * @author Tim Perez <[email protected]>
 */

// Pre-cache Sample Sets
var sampleSet = [
  [7,0,2,8,3,1,5,6,9,4],        // Small Random Set
  [9,8,7,6,5,4,3,2,1,0],        // Reversed Small Set
  shuffleArr(genSeqArr(1000)),  // 1000 Random
  shuffleArr(genSeqArr(10000))  // 10,000 Random*/
];

/**
 * Verbose Algorithm Counter Object
 * @returns {Object} self
 */
var sortCounter = function () {
  this.iters = 0;
  this.comparisons = 0;
  this.access = 0;
};

/**
 * Collection of Sort Algorithms
 * @description - Each method args expects an array of random numbers
 */
var sortAlgorithms = {
  bubble: function (arr) {
    //var sc = new sortCounter();
    function bubbleSort(arr){
      var len = arr.length;
       for (var i = len-1; i>=0; i--){
         for(var j = 1; j<=i; j++){
           if(arr[j-1]>arr[j]){
               var temp = arr[j-1];
               arr[j-1] = arr[j];
               arr[j] = temp;
            }
         }
       }
       return arr;
    }

    return bubbleSort(arr);
  },
  selection: function (arr) {
    function selectionSort(arr){
      var minIdx, temp,
          len = arr.length;
      for(var i = 0; i < len; i++){
        minIdx = i;
        for(var  j = i+1; j<len; j++){
           if(arr[j]<arr[minIdx]){
              minIdx = j;
           }
        }
        temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
      }
      return arr;
    }

    return selectionSort(arr);
  },
  insertion: function (arr) {
    function insertionSort(arr){
      for (var i = 0; i < arr.length; i++) {
        var k = arr[i];
        for (var j = i; j > 0 && k < arr[j - 1]; j--){
          arr[j] = arr[j - 1];
        }
        arr[j] = k;
      }
      return arr;
    }
    return insertionSort(arr);
  },
  merge: function (arr) {
    function mergeSort(arr){
       var len = arr.length;
       if(len <2)
          return arr;
       var mid = Math.floor(len/2),
           left = arr.slice(0,mid),
           right =arr.slice(mid);
       //send left and right to the mergeSort to broke it down into pieces
       //then merge those
       return merge(mergeSort(left),mergeSort(right));
    }
    function merge(left, right){
      var result = [],
          lLen = left.length,
          rLen = right.length,
          l = 0,
          r = 0;
      while(l < lLen && r < rLen){
         if(left[l] < right[r]){
           result.push(left[l++]);
         }
         else{
           result.push(right[r++]);
        }
      }
      //remaining part needs to be addred to the result
      return result.concat(left.slice(l)).concat(right.slice(r));
    }

    return mergeSort(arr);
  },
  quick: function (arr) {
    var right = arr.length - 1;
    var left = 0;

    function quickSort(arr, left, right){
       var len = arr.length,
       pivot,
       partitionIndex;


      if(left < right){
        pivot = right;
        partitionIndex = partition(arr, pivot, left, right);

       //sort left and right
       quickSort(arr, left, partitionIndex - 1);
       quickSort(arr, partitionIndex + 1, right);
      }
      return arr;
    }
    function partition(arr, pivot, left, right){
       var pivotValue = arr[pivot],
           partitionIndex = left;

       for(var i = left; i < right; i++){
        if(arr[i] < pivotValue){
          swap(arr, i, partitionIndex);
          partitionIndex++;
        }
      }
      swap(arr, right, partitionIndex);
      return partitionIndex;
    }
    function swap(arr, i, j){
       var temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
    }

    return quickSort(arr, left, right);
  },
  heap: function (arr) {
    function heapSort(arr){
      var len = arr.length,
          end = len-1;

      heapify(arr, len);

      while(end > 0){
       swap(arr, end--, 0);
       siftDown(arr, 0, end);
      }
      return arr;
    }
    function heapify(arr, len){
       // break the array into root + two sides, to create tree (heap)
       var mid = Math.floor((len-2)/2);
       while(mid >= 0){
        siftDown(arr, mid--, len-1);
      }
    }
    function siftDown(arr, start, end){
       var root = start,
           child = root*2 + 1,
           toSwap = root;
       while(child <= end){
          if(arr[toSwap] < arr[child]){
            swap(arr, toSwap, child);
          }
          if(child+1 <= end && arr[toSwap] < arr[child+1]){
            swap(arr, toSwap, child+1)
          }
          if(toSwap != root){
             swap(arr, root, toSwap);
             root = toSwap;
          }
          else{
             return;
          }
          toSwap = root;
          child = root*2+1
      }
    }
    function swap(arr, i, j){
      var temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }

    return heapSort(arr);
  },
  // My Custom Sort :)
  hack: function (arr) {
    var sortedArr = [];

    // Filter to Only Return Defined Values
    function filterEmptyNodes (value) {
      return typeof value !== "undefined";
    }

    // Pre-allocate size of array (v8 perf +)
    sortedArr.length = arr.length;

    // Iterate Keys and copy values to holder array
    for (var i = 0, len = arr.length; i < len; i++) {
      sortedArr[arr[i]] = arr[i];
    }
    return sortedArr.filter(filterEmptyNodes);
  }
};

/**
 * Create a sequential array of numbers
 * @param {Number} len - Length of sequence array to be returned
 * @returns {Array} arr - Sequence array
 */
function genSeqArr (len) {
  var min = 0;
  var i;
  var arr = [];
  for (i = min; i<len; i++) {
    arr.push(i);
  }
  return arr;
}

/**
 * Shuffles Provided Array
 * @param {Array} arr - preshuffled array
 * @returns {Array} arr - shuffled array
 */
function shuffleArr (arr) {
  for(var j, x, i = arr.length; i; j = Math.floor(Math.random() * i), x = arr[--i], arr[i] = arr[j], arr[j] = x);
  return arr;
}

/**
 * Benchmark Sort Algorithms
 * @description Test performance of sorting against provided data (shuffled arrays)
 * @param {String} sortName - Name of sort method
 * @see sortAlgorithm Object
 * @param {Array} sampleSet - Array of Randomized Arrays to Sort Against
 * @param {Bool} displaySortedResult - Flag to output actual sorted returned result
 */
function benchmarkSort(sortName, sampleSet, displaySortedResult) {
  console.debug('\n Benchmarking %s', sortName);

  sampleSet.forEach(function (testArr, i) {
    // Sort against copy, instead of ref obj
    var unsortedArr = JSON.parse(JSON.stringify(testArr));
    var t0 = performance.now();
    var sorted = sortAlgorithms[sortName](unsortedArr);
    var t1 = performance.now();
    console.debug("  Test %d: %f ms", (i + 1), (t1 - t0));
    if (displaySortedResult) {
      console.debug('Sorted Result', sorted);
    }
  });
}

// Run all Benchmarks
benchmarkSort('hack', sampleSet);
benchmarkSort('quick', sampleSet);
benchmarkSort('bubble', sampleSet);
benchmarkSort('insertion', sampleSet);
benchmarkSort('merge', sampleSet);
benchmarkSort('heap', sampleSet);
benchmarkSort('selection', sampleSet);