Preparation code

      
      <script>

        Benchmark.prototype.setup = function() {

          
              var arr = [];
              var n = 200000; //array size we are sorting
  
              for (var i = 0; i < n; i++) {
                  arr.push(parseInt(Math.random() * 10000));
              }
  
  /********************************************* SHUFFLE *****************************************************************/
  //Fisher-Yates...aka..Knuth Shuffle
              function shuffle(arr) {
  
                  var currentIndex = arr.length;
                  var temporaryValue;
                  var randomIndex;
  
                  // While there remain elements to shuffle...
                  while (0 !== currentIndex) {
  
                      // Pick a remaining element...
                      randomIndex = Math.floor(Math.random() * currentIndex);
                      currentIndex -= 1;
  
                      // And swap it with the current element.
                      temporaryValue = arr[currentIndex];
                      arr[currentIndex] = arr[randomIndex];
                      arr[randomIndex] = temporaryValue;
                  }
  
                  return arr;
              }
  /*********************************** RECURSIVE QUICK SORT *************************************************************/
  var StandardRecursiveQuicksort = (function() {
  
      var standardRecursiveQS = {};
  
      standardRecursiveQS.sort = function(arr) {
          if (arr.length <= 1) {
              return arr;
          }
          return recursiveQuickSort(arr, 0, arr.length - 1);
      }
  
      function recursiveQuickSort(arr, left, right) { //partition arrays so that everything to the left of pivot is less then pivot, and everything to the right is greater then pivot
          var i = left;
          var j = right;
          var tmp;
          var pivotidx = (left + right) / 2;
          var pivot = parseInt(arr[pivotidx.toFixed()]);
          /* partition */
          while (i <= j) {
              while (parseInt(arr[i]) < pivot)
                  i++;
              while (parseInt(arr[j]) > pivot)
                  j--;
              if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
              }
          }
  
          /* recursion */
          if (left < j)
              recursiveQuickSort(arr, left, j);
          if (i < right)
              recursiveQuickSort(arr, i, right);
          return arr;
      }
      return standardRecursiveQS;
  }());
  
  /**********************************************************************************************************************/
  /*************************************** Three Way Partition Quicksort ************************************************/
  var ThreeWayPartitionQuicksort = (function() {
  
      var ThreeWayPartionQuicksortModule = {};
  
      //Private Variables
      var CUTOFF = 8;  // cutoff to insertion sort, must be >= 1
  
      ThreeWayPartionQuicksortModule.sort = function( a, lo, hi) { //Public function
  
          if(typeof lo == "undefined" && typeof hi === "undefined"){
              this.sort(a, 0, a.length - 1);
          } else{
              var N = hi - lo + 1;
  
              // cutoff to insertion sort
              if (N <= CUTOFF) {
                  insertionSort(a, lo, hi);
                  return;
              }
  
              // use median-of-3 as partitioning element
              else if (N <= 40) {
                  var m = median3(a, lo, lo + N/2, hi);
                  exch(a, m, lo);
              }
  
              // use Tukey ninther as partitioning element
              else  {
                  var eps = N/8; //TODO: verify these come out as integers
                  var mid = lo + N/2;
                  var m1 = median3(a, lo, lo + eps, lo + eps + eps);
                  var m2 = median3(a, mid - eps, mid, mid + eps);
                  var m3 = median3(a, hi - eps - eps, hi - eps, hi);
                  var ninther = median3(a, m1, m2, m3);
                  exch(a, ninther, lo);
              }
  
              // Bentley-McIlroy 3-way partitioning
              var i = lo, j = hi+1;
              var p = lo, q = hi+1;
              var v = a[lo];
              while (true) {
                  while (less(a[++i], v))
                      if (i == hi) break;
                  while (less(v, a[--j]))
                      if (j == lo) break;
  
                  // pointers cross
                  if (i == j && eq(a[i], v))
                      exch(a, ++p, i);
                  if (i >= j) break;
  
                  exch(a, i, j);
                  if (eq(a[i], v)) exch(a, ++p, i);
                  if (eq(a[j], v)) exch(a, --q, j);
              }
  
  
              i = j + 1;
              for (var k = lo; k <= p; k++) exch(a, k, j--);
              for (var k = hi; k >= q; k--) exch(a, k, i++);
  
              this.sort(a, lo, j);
              this.sort(a, i, hi);
          }
  
      }
  
  
      // sort from a[lo] to a[hi] using insertion sort
      function insertionSort( a, lo, hi) {
          for (var i = lo; i <= hi; i++)
              for (var j = i; j > lo && less(a[j], a[j-1]); j--)
                  exch(a, j, j-1);
      }
  
  
      // return the index of the median element among a[i], a[j], and a[k]
      function median3( a, i, j, k) {
          return (less(a[i], a[j]) ?
              (less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) :
              (less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i));
      }
  
      /***********************************************************************
       *  Helper sorting functions
       ***********************************************************************/
  
          // is v < w ?
      function less(v, w) {
          return (v < w); //java version uses compareto
      }
  
      // does v == w ?
      function eq(v, w) {
          return (v == w); //java version uses compareto
      }
  
      // exchange a[i] and a[j]
      function exch(a, i, j) {
          var  swap = a[i];
          a[i] = a[j];
          a[j] = swap;
      }
  
      return ThreeWayPartionQuicksortModule;
  }());
  
  /**********************************************************************************************************************/
  /*************************************** Dual Pivot QuickSort *********************************************************/
  
  var DualPivotQuicksort = (function() {
  
      var dualPivotQS = {};
  
      dualPivotQS.sort = function(arr, fromIndex, toIndex) {
          if(fromIndex === undefined && toIndex === undefined){
              this.sort(arr, 0, arr.length);
          } else{
              rangeCheck(arr.length, fromIndex, toIndex);
              dualPivotQuicksort(arr, fromIndex, toIndex - 1, 3);
          }
          return arr;
      }
  
      function rangeCheck(length, fromIndex, toIndex) {
          if (fromIndex > toIndex) {
              console.error("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
          }
          if (fromIndex < 0) {
              console.error(fromIndex);
          }
          if (toIndex > length) {
              console.error(toIndex);
          }
      }
  
      function swap(arr, i, j) {
          var temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
      }
  
      function dualPivotQuicksort( arr, left, right, div) {
          var len = right - left;
  
          if (len < 27) { // insertion sort for tiny array
              for (var i = left + 1; i <= right; i++) {
                  for (var j = i; j > left && arr[j] < arr[j - 1]; j--) {
                      swap(arr, j, j - 1);
                  }
              }
              return;
          }
          var third = Math.floor(len / div); //TODO: check if we need to round up or down or just nearest
  
          // "medians"
          var m1 = left  + third;
          var m2 = right - third;
  
          if (m1 <= left) {
              m1 = left + 1;
          }
          if (m2 >= right) {
              m2 = right - 1;
          }
          if (arr[m1] < arr[m2]) {
              swap(arr, m1, left);
              swap(arr, m2, right);
          }
          else {
              swap(arr, m1, right);
              swap(arr, m2, left);
          }
          // pivots
          var pivot1 = arr[left];
          var pivot2 = arr[right];
  
          // pointers
          var less  = left  + 1;
          var great = right - 1;
  
          // sorting
          for (var k = less; k <= great; k++) {
              if (arr[k] < pivot1) {
                  swap(arr, k, less++);
              }
              else if (arr[k] > pivot2) {
                  while (k < great && arr[great] > pivot2) {
                      great--;
                  }
                  swap(arr, k, great--);
  
                  if (arr[k] < pivot1) {
                      swap(arr, k, less++);
                  }
              }
          }
          // swaps
          var dist = great - less;
  
          if (dist < 13) {
              div++;
          }
          swap(arr, less  - 1, left);
          swap(arr, great + 1, right);
  
          // subarrays
          dualPivotQuicksort(arr, left,   less - 2, div);
          dualPivotQuicksort(arr, great + 2, right, div);
  
          // equal elements
          if (dist > len - 13 && pivot1 != pivot2) {
              for (var k = less; k <= great; k++) {
                  if (arr[k] == pivot1) {
                      swap(arr, k, less++);
                  }
                  else if (arr[k] == pivot2) {
                      swap(arr, k, great--);
  
                      if (arr[k] == pivot1) {
                          swap(arr, k, less++);
                      }
                  }
              }
          }
          // subarray
          if (pivot1 < pivot2) {
              dualPivotQuicksort(arr, less, great, div);
          }
      }
      return dualPivotQS;
  }());
  
  /**********************************************************************************************************************/
  
        
  };
          



        Benchmark.prototype.teardown = function() {

          
  shuffle(arr);
        
  };

      
</script>
    

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

function quickSort(arr) {

  if (arr.length <= 1) {
    return arr
  }
  var randomNumber = Math.floor(Math.random()* arr.length)
  var medianArray = [
    arr[0],
    arr[Math.floor((arr.length)/2)],
    arr[(arr.length)-1]
  ]

/* here we run a 2 pass bubble sort to find the median number...*/
    var temp;
    if (medianArray[0] > medianArray[1]) {
      temp = medianArray[1]
      medianArray[1] = medianArray[0]
      medianArray[0] = temp
    }
        if (medianArray[1] > medianArray[2]) {
      temp = medianArray[2]
      medianArray[2] = medianArray[1]
      medianArray[1] = temp
    }

/* now we take the median number and grab the actual value of that 
number in our current arr */

    median = medianArray[1]
    median = arr[median]
  var pivotNumber =  arr.splice(median, 1)
  var left = []
  var right = []
  var x = arr.length;

    while (x--) { 

    if (arr[x] <= pivotNumber) {
      left[left.length] = arr[x]
    }
    else {
      right[right.length] = arr[x]
    }
  }
  var leftSorted = quickSort(left)
  var rightSorted = quickSort(right)
  return leftSorted.concat(pivotNumber).concat(rightSorted)
}

function quickSort(arr) {
  
  if (arr.length <= 1) {
    return arr
  }

  var medianArray = [
    arr[0],
    arr[Math.floor((arr.length)/2)],
    arr[(arr.length)-1]
  ]

/* here we run a 2 pass bubble sort to find the median number...*/
    var temp;
    if (medianArray[0] > medianArray[1]) {
      temp = medianArray[1]
      medianArray[1] = medianArray[0]
      medianArray[0] = temp
    }
        if (medianArray[1] > medianArray[2]) {
      temp = medianArray[2]
      medianArray[2] = medianArray[1]
      medianArray[1] = temp
    }

/* now we take the median number and grab the actual value of that 
number in our current arr */

    median = medianArray[1]
    median = arr[median]
  var pivotNumber =  arr.splice(median, 1)
  var left = []
  var right = []
  var x = arr.length;

    while (x--) { 

    if (arr[x] <= pivotNumber) {
      left.push(arr[x])
    }
    else {
      right.push(arr[x])
    }
  }
  var leftSorted = quickSort(left)
  var rightSorted = quickSort(right)
  return leftSorted.concat(pivotNumber).concat(rightSorted)
}

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  var randomNumber = Math.floor(Math.random()* arr.length)
  var pivotNumber = arr.splice(randomNumber, 1)
  var left = []
  var right = []
  var x = arr.length;

    while (x--) { 

    if (arr[x] <= pivotNumber) {
      left.push(arr[x])
    }
    else {
      right.push(arr[x])
    }
  }
  var leftSorted = quickSort(left)
  var rightSorted = quickSort(right)
  return leftSorted.concat(pivotNumber).concat(rightSorted)
}

StandardRecursiveQuicksort.sort(arr);

ThreeWayPartitionQuicksort.sort(arr);

DualPivotQuicksort.sort(arr);

arr.sort(function(a, b){return a-b});

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  var randomNumber = Math.floor(Math.random()* arr.length)
  var pivotNumber = arr.splice(randomNumber, 1)
  var left = []
  var right = []
  
  for (var x=0;x<arr.length;x++) {
    if (arr[x] <= pivotNumber) {
      left.push(arr[x])
    }
    else {
      right.push(arr[x])
    }
  }
  var leftSorted = quickSort(left)
  var rightSorted = quickSort(right)
  return leftSorted.concat(pivotNumber).concat(rightSorted)
}

Compare results of other browsers

Revisions

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

• Revision 1: published Stan on 2014-8-16
• Revision 2: published stacey reiman on 2014-10-29
• Revision 3: published stacey reiman on 2014-10-29
• Revision 4: published stacey reiman on 2014-10-31
• Revision 5: published stacey reiman on 2014-10-31
• Revision 6: published Mark on 2014-11-6

0 Comments