Pourquoi l'implémentation Javascript de Bubble sort beaucoup plus vite que les autres algorithmes de tri?

Question

J'ai fait quelques research sur la comparaison des performances des algorithmes de tri Javascript, et j'ai trouvé des résultats inattendus. Le tri par bulles a fourni de bien meilleures performances que d'autres, tels que le tri Shell, le tri rapide et une fonctionnalité JavaScript native. Pourquoi cela arrive-t-il? Peut-être que je me trompe dans ma méthode de test de performance?

Vous pouvez trouver mes résultats de recherche here.

Voici quelques exemples de mise en œuvre de l'algorithme:

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

C'est parce que la bulle tri est plus rapide lorsque vous triez un tableau qui est déjà triée. Lorsque vous triez le même tableau encore et encore, il est trié à la première itération du premier test, après le tri d'un tableau déjà trié.

Pour tester les performances réelles du tri d'un tableau qui n'est pas déjà trié, vous devez créer un nouveau tableau pour chaque itération de tri.