Perché l'implementazione Javascript di Bubble sort è molto più veloce di altri algoritmi di ordinamento?

Question

Ho apportato alcune informazioni su research riguardo al confronto delle prestazioni degli algoritmi di ordinamento Javascript e ho trovato risultati imprevisti. Bubble sort ha fornito prestazioni molto migliori di altri come Shell sort, Quick sort e una funzionalità Javascript nativa. Perché succede? Forse mi sbaglio nel mio metodo di test delle prestazioni?

È possibile trovare i risultati della ricerca here.

Ecco alcuni esempi di implementazione dell'algoritmo:

/** 
    * 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

Questo perché bubble sort è più veloce quando si è Ordinamento di un array che è già ordinato.

Come si ordina lo stesso array più e più volte, sarà ordinato nella prima iterazione nel primo test, dopo che si sta ordinando un array che è già ordinato.

Per verificare le prestazioni effettive di ordinamento di un array che non è già ordinato, è necessario creare un nuovo array per ogni iterazione di ordinamento.