Dlaczego implementacja Javascript w Bubble jest o wiele szybsza niż inne algorytmy sortowania?

Question

Zrobiłem trochę research o porównanie algorytmów sortowania JavaScript i znaleziono nieoczekiwane wyniki. Sortowanie bąbelkowe zapewnia znacznie lepszą wydajność niż inne, takie jak sortowanie według powłoki, sortowanie szybkie i natywna funkcja JavaScript. Dlaczego to się dzieje? Może się mylę w mojej metodzie testowania wydajności?

Wyniki moich badań można znaleźć pod numerem here.

Oto kilka przykładów implementacji algorytmu:

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

Answer 1

To dlatego bubble sort jest szybsza podczas sortowania tablicę, która jest już posortowana.

Podczas sortowania tej samej tablicy w kółko, zostanie ona posortowana w pierwszej iteracji w pierwszym teście, po tym jak sortujesz tablicę, która jest już posortowana.

Aby przetestować rzeczywistą wydajność sortowania tablicy, która nie jest jeszcze posortowana, należy utworzyć nową tablicę dla każdej iteracji sortowania.