开发者

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

开发者 https://www.devze.com 2023-04-11 09:50 出处:网络
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 s

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:

  /**
   *开发者_StackOverflow中文版 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());
  }


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.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号