Sorting Algorithm Comparison

Benchmark created by torinaki on October 7, 2011

Preparation HTML

<script>
  /**
   * Bubble sort(optimized)
   */
  Array.prototype.bubbleSort = function ()
  {
     var n = this.length;
     do {
        var swapped = false;
        for (var i = 1; i < n; i++ ) {
           if (this[i - 1] > this[i]) {
              var tmp = this[i-1];
              this[i-1] = this[i];
              this[i] = tmp;
              swapped = true;
           }
        }
     } while (swapped);
  }
  /**
   * Shell sort
   */
  Array.prototype.shellSort = function ()
  {
      var lastKey = this.length -1,
          inc = Math.round(this.length / 2),
          temp, j, i;
      while (inc > 0) {
          for (i = inc; i <= lastKey; i++) {
              temp = this[i];
              j = i;
              while (j >= inc && this[j - inc] > temp) {
                  this[j] = this[j - inc];
                  j = j - inc;
              }
              this[j] = temp;
          }
          inc = Math.round(inc / 2.2);
      }
  }
  /**
   * Quick sort
   */
  Array.prototype.quickSort = function ()
  {
      if (this.length <= 1)
          return this;
  
      var pivot = this[Math.round(this.length / 2)];
  
      return this.filter(function (x) { return x <  pivot }).quickSort().concat(
             this.filter(function (x) { return x == pivot })).concat(
             this.filter(function (x) { return x >  pivot }).quickSort());
  }
  
  
  /**
   * Common function
   */
  var Common = {};
  Common.randomNumber = function (min, max) {
      var argc = arguments.length;
      if (argc === 0) {
          min = 0;
          max = 2147483647;
      } else if (argc === 1) {
          throw new Error('Common.prototype.randomNumber expects exactly 2 parameters, 1 given');
      }
      return Math.floor(Math.random() * (max - min + 1)) + min;
  }
  Common.arrayRandom = function (min, max, size, startIndex) {
      if (typeof(startIndex) != 'number') {
          startIndex = 0;
      }
      var arr = [], i = startIndex;
      size += startIndex;
      while (i < size) {
          arr[i] = this.randomNumber(min, max);
          i++;
      }
      return arr;
  }
  
  
  var arr = Common.arrayRandom(1, 10000, 10000);
</script>

Test runner

arr.bubbleSort();

arr.shellSort()

arr.sort(function(i, j){
    return i-j;
})

arr.quickSort();

Revisions

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

• Revision 1: published by torinaki on October 7, 2011
• Revision 3: published on October 8, 2011