Javascript Flashsort Comparisons

JavaScript performance comparison

Revision 5 of this test case created by stacey reiman

Preparation code


      
      <script>
Benchmark.prototype.setup = function() {
              var arr = [];
              var n = 50000; //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.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
Quick Sort Due
   function quickSortNow(arr){
        quick(arr,  0, arr.length - 1);
        return arr
    };

    function partitionNow(arr, left, right) {

        var pivot = arr[Math.floor((right + left) / 2)],
            i = left,
            j = right;

        console.log('pivot is ' + pivot + '; left is ' + left + '; right is ' + right);

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
                console.log('i = ' + i);
            }

            while (arr[j] > pivot) {
                j--;
                console.log('j = ' + j);
            }

            if (i <= j) {
                console.log('swap ' + arr[i] + ' with ' + arr[j]);
                swapQuickSort(arr, i, j);
                i++;
                j--;
            }
        }

        return i;
    };

   function swapQuickSort(arr, index1, index2){
        var aux = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = aux;
    };

    function quick(arr, left, right){

        var index;

        if (arr.length > 1) {

            index = partitionNow(arr, left, right);

            if (left < index - 1) {
                quick(arr, left, index - 1);
            }

            if (index < right) {
                quick(arr, index, right);
            }
        }
        return arr;
    };
pending…
Quick Sort Tre
    function quicksort(arr, begin, end) {

     if (typeof begin == 'undefined') begin = 0
     if (typeof end == 'undefined') end = arr.length

     if (end - begin < 2) return

     var pivot = _quicksortChoosePivot(arr, begin, end)

     partition(arr, begin, end, pivot)

     quicksort(arr, begin, pivot)
     quicksort(arr, pivot + 1, end)

     return arr
 }

 function _quicksortChoosePivot(arr, begin, end) {
     return begin //+ Math.floor(Math.random() * (end - begin))
 }

 Array.prototype.swap = function(index1, index2) {

     var tmp = this[index1]

     this[index1] = this[index2]
     this[index2] = tmp

     return this
 }

 function partition(arr, begin, end, pivot) {

     var i = begin,
     pivotValue = arr[pivot]

     if (pivot != begin) arr.swap(begin, pivot)

     for (var j = i; j <= end; j++) {

       // If element > pivot do nothing...
       if (arr[j] <= pivotValue) {
           // swap element with left most element that's bigger than the pivot
           arr.swap(i, j)
           i++
       }
     }

     arr.swap(begin, i - 1)
 }
pending…
Flashsort 2
                 function flashSort(arr) {
                                var n = arr.length;
                                var i = 0, j = 0, k = 0, t;
                                var m = ~~( n * 0.125 );
                                var l = [];
    var anmin = Math.max.apply(Math, arr); 
    var nmax = Math.min.apply(Math, arr);
                                var nmove = 0;

                                for ( i = 0; i < m; i++ ) {
                                        l[ i ] = 0;
                                }


                                if ( anmin == arr[ nmax ]) return;

                                var c1 = ( m - 1 ) / ( arr[ nmax ] - anmin );

                                for ( i = 0; i < n; ++i ) {
                                        k = ~~( c1 * ( arr[ i ] - anmin ) );
                                        ++l[ k ];
                                }

                                for ( k = 1; k < m; ++k ) {
                                        l[ k ] += l[ k - 1 ];
                                }

                                var hold = arr[ nmax ];
                                arr[ nmax ] = arr[ 0 ];
                                arr[ 0 ] = hold;

                                var flash;
                                j = 0;
                                k = m - 1;
                                i = n - 1;

                                while ( nmove < i ) {
                                        while ( j > ( l[ k ] - 1 ) ) {
                                                k = ~~( c1 * ( arr[ ++j ] - anmin ) );
                                        }
                                        flash = arr[ j ];

                                        while ( j != l[ k ] ) {
                                                k = ~~( c1 * ( flash - anmin ) );
                                                hold = arr[ ( t = l[ k ]-1) ];
                                                arr[ t ] = flash;
                                                flash = hold;
                                                --l[ k ];
                                                ++nmove;
                                        }
                                }

                                for( j = 1; j < n; ++j ) {
                                        hold = arr[ j ];
                                        i = j - 1;
                                        while( i >= 0 && arr[i] > hold ) {
                                                arr[ i + 1 ] = arr[ i-- ];
                                        }
                                        arr[ i + 1 ] = hold;
                                }
                                return arr
                        }
pending…
Flashsort 3
function flashSort2(arr) {

    var lengthy = arr.length;
    var i = 0, j = 0, k = 0, t;

    var m = ~~( lengthy * 0.125 );
    var left = [];
    var anmin = Math.max.apply(Math, arr); 
    var nmax = Math.min.apply(Math, arr); 
    var nmove = 0;
    var finalSwaps = 0;
 

    while(i < m) {
            left[ i ] = 0;
        i++
    }


    if ( anmin == arr[ nmax ]) return;

    var c1 = ( m - 1 ) / ( arr[ nmax ] - anmin );

    left[0] = lengthy-1;

    for ( k = 1; k < m; ++k ) {
            left[ k ] += left[ k - 1 ];
    }

    var hold = arr[ nmax ];
    arr[ nmax ] = arr[ 0 ];
    arr[ 0 ] = hold;


    var flash;
    j = 0;
    k = m - 1;
    i = lengthy - 1;


    while ( nmove < i ) {
               flash = arr[ 0 ];
            
            while ( j != left[ k ] ) {
                    k = ~~( c1 * ( flash - anmin ) );
                    hold = arr[ ( t = left[ k ]-1) ];
                    arr[ t ] = flash;
                    flash = hold; 
                    --left[ k ];
                    ++nmove;
            }
    }

    for( j = 1; j < lengthy; ++j ) {

            hold = arr[ j ];
            i = j - 1;

            while( i >= 0 && arr[i] > hold ) {
                arr[ i + 1 ] = arr[ i-- ];
            }

            arr[ i + 1 ] = hold;
    }
    return arr
}
pending…
Flash Sort 1
                 function flashSort(arr) {
                                var n = arr.length;
                                var i = 0, j = 0, k = 0, t;
                                var m = ~~( n * 0.125 );
                                var l = [];
                                var anmin = arr[ 0 ];
                                var nmax = 0;
                                var nmove = 0;

                                for ( i = 0; i < m; i++ ) {
                                        l[ i ] = 0;
                                }

                                for ( i = 1; i < n; ++i ) {
                                        if ( arr[ i ] < anmin ) anmin = arr[ i ];
                                        if ( arr[ i ] > arr[ nmax ] ) nmax = i;
                                }

                                if ( anmin == arr[ nmax ]) return;

                                var c1 = ( m - 1 ) / ( arr[ nmax ] - anmin );

                                for ( i = 0; i < n; ++i ) {
                                        k = ~~( c1 * ( arr[ i ] - anmin ) );
                                        ++l[ k ];
                                }

                                for ( k = 1; k < m; ++k ) {
                                        l[ k ] += l[ k - 1 ];
                                }

                                var hold = arr[ nmax ];
                                arr[ nmax ] = arr[ 0 ];
                                arr[ 0 ] = hold;

                                var flash;
                                j = 0;
                                k = m - 1;
                                i = n - 1;

                                while ( nmove < i ) {
                                        while ( j > ( l[ k ] - 1 ) ) {
                                                k = ~~( c1 * ( arr[ ++j ] - anmin ) );
                                        }
                                        flash = arr[ j ];

                                        while ( j != l[ k ] ) {
                                                k = ~~( c1 * ( flash - anmin ) );
                                                hold = arr[ ( t = l[ k ]-1) ];
                                                arr[ t ] = flash;
                                                flash = hold;
                                                --l[ k ];
                                                ++nmove;
                                        }
                                }

                                for( j = 1; j < n; ++j ) {
                                        hold = arr[ j ];
                                        i = j - 1;
                                        while( i >= 0 && arr[i] > hold ) {
                                                arr[ i + 1 ] = arr[ i-- ];
                                        }
                                        arr[ i + 1 ] = hold;
                                }
                                return arr
                        }
pending…
Quicksort 6 - reverse loop
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)
}
pending…
Quicksort 7 - median pivot
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)
}
pending…
Quicksort 8 - assignment instead of push
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[left.length] = arr[x]
    }
    else {
      right[right.length] = arr[x]
    }
  }
  var leftSorted = quickSort(left)
  var rightSorted = quickSort(right)
  return leftSorted.concat(pivotNumber).concat(rightSorted)
}
pending…
Default Recursive Javascript Quicksort
StandardRecursiveQuicksort.sort(arr);
pending…
Three Way Partition Javascript Quicksort
ThreeWayPartitionQuicksort.sort(arr);
pending…
Dual Pivot Javascript Quicksort
DualPivotQuicksort.sort(arr);
pending…
Default Javascript Sort
arr.sort(function(a, b){return a-b});
pending…
Quicksort 5
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)
}
pending…

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.

0 Comments