Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why Javascript implementation of Bubble sort much faster than others sorting algorithms?

I have done some research about Javascript sorting algorithms performance comparison, and found unexpected results. Bubble sort provided much better performance than others such as Shell sort, Quick sort and a native Javascript functionality. Why does this happen? Maybe I'm wrong in my performance testing method?

You can find my research results here.

Here are some algorithm implementation examples:

  /**
   * 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);
  }

  /**
   * 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());
  }
like image 471
Dmitry Balabka Avatar asked Oct 08 '11 11:10

Dmitry Balabka


1 Answers

That's because bubble sort is faster when you are sorting an array that is already sorted.

As you are sorting the same array over and over, it will be sorted in the first iteration in the first test, after that you are sorting an array that is already sorted.

To test the actual performance of sorting an array that is not already sorted, you have to create a new array for each sort iteration.

like image 159
Guffa Avatar answered Oct 19 '22 19:10

Guffa