Почему реализация Jubascript Bubble сортирует намного быстрее, чем другие алгоритмы сортировки? - PullRequest
Новая
       9

Почему реализация Jubascript Bubble сортирует намного быстрее, чем другие алгоритмы сортировки?

8 голосов
/ 08 октября 2011

Я провел исследование о сравнении производительности алгоритмов сортировки Javascript и нашел неожиданные результаты.Bubble sort обеспечивает намного лучшую производительность, чем другие, такие как Shell sort, Quick sort и встроенная функциональность Javascript.Почему это происходит?Может быть, я ошибаюсь в своем методе тестирования производительности?

Вы можете найти результаты моего исследования здесь .

Вот несколько примеров реализации алгоритма: 

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

1 Ответ

13 голосов
/ 08 октября 2011

Это потому, что сортировка пузырьков происходит быстрее, когда вы сортируете массив, который уже отсортирован.

Поскольку вы сортируете один и тот же массив снова и снова, он будет отсортирован на первой итерации в первом тесте,после этого вы сортируете массив, который уже отсортирован.

Чтобы проверить фактическую производительность сортировки массива, который еще не отсортирован, вы должны создать новый массив для каждой итерации сортировки.

...