Implémentation de Javascript Array.sort?

Quel algorithme la Array#sort()fonction JavaScript utilise-t-elle? Je comprends que cela peut prendre toutes sortes d'arguments et de fonctions pour effectuer différents types de sortes, je suis simplement intéressé par l'algorithme utilisé par le tri vanilla.

Si vous regardez ce bogue 224128 , il semble que MergeSort est utilisé par Mozilla.

Je viens de jeter un œil à la source WebKit (Chrome, Safari…) . Selon le type de tableau, différentes méthodes de tri sont utilisées:

Les tableaux numériques (ou tableaux de type primitif) sont triés à l'aide de la fonction de bibliothèque standard C ++ std::qsortqui implémente une certaine variation de tri rapide (généralement introsort ).

Les tableaux contigus de type non numérique sont chaîne et triés en utilisant mergesort, si disponible (pour obtenir un tri stable) ou qsortsi aucun tri par fusion n'est disponible.

Pour d'autres types (tableaux non contigus et vraisemblablement pour les tableaux associatifs) WebKit utilise soit le tri par sélection (qu'ils appellent le tri «min» ), soit, dans certains cas, il trie via une arborescence AVL. Malheureusement, la documentation ici est assez vague, vous devrez donc suivre les chemins de code pour voir pour quels types quelle méthode de tri est utilisée.

Et puis il y a des joyaux comme ce commentaire :

// FIXME: Since we sort by string value, a fast algorithm might be to use a
// radix sort. That would be O(N) rather than O(N log N).

- Espérons simplement que quiconque «corrige» cela a une meilleure compréhension de l'exécution asymptotique que l'auteur de ce commentaire, et se rend compte que le tri radix a une description d'exécution légèrement plus complexe que simplement O (N).

(Merci à phsource d'avoir signalé l'erreur dans la réponse d'origine.)

Il n'y a pas de projet d'exigence pour JS d'utiliser un algorthim de tri spécifique. Comme beaucoup l'ont mentionné ici, Mozilla utilise le tri par fusion.Cependant, dans le code source de Chrome v8, à partir d'aujourd'hui, il utilise QuickSort et InsertionSort, pour les tableaux plus petits.

Source de moteur V8

Depuis les lignes 807 - 891

  var QuickSort = function QuickSort(a, from, to) {
    var third_index = 0;
    while (true) {
      // Insertion sort is faster for short arrays.
      if (to - from <= 10) {
        InsertionSort(a, from, to);
        return;
      }
      if (to - from > 1000) {
        third_index = GetThirdIndex(a, from, to);
      } else {
        third_index = from + ((to - from) >> 1);
      }
      // Find a pivot as the median of first, last and middle element.
      var v0 = a[from];
      var v1 = a[to - 1];
      var v2 = a[third_index];
      var c01 = comparefn(v0, v1);
      if (c01 > 0) {
        // v1 < v0, so swap them.
        var tmp = v0;
        v0 = v1;
        v1 = tmp;
      } // v0 <= v1.
      var c02 = comparefn(v0, v2);
      if (c02 >= 0) {
        // v2 <= v0 <= v1.
        var tmp = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
      } else {
        // v0 <= v1 && v0 < v2
        var c12 = comparefn(v1, v2);
        if (c12 > 0) {
          // v0 <= v2 < v1
          var tmp = v1;
          v1 = v2;
          v2 = tmp;
        }
      }
      // v0 <= v1 <= v2
      a[from] = v0;
      a[to - 1] = v2;
      var pivot = v1;
      var low_end = from + 1;   // Upper bound of elements lower than pivot.
      var high_start = to - 1;  // Lower bound of elements greater than pivot.
      a[third_index] = a[low_end];
      a[low_end] = pivot;

      // From low_end to i are elements equal to pivot.
      // From i to high_start are elements that haven't been compared yet.
      partition: for (var i = low_end + 1; i < high_start; i++) {
        var element = a[i];
        var order = comparefn(element, pivot);
        if (order < 0) {
          a[i] = a[low_end];
          a[low_end] = element;
          low_end++;
        } else if (order > 0) {
          do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
            order = comparefn(top_elem, pivot);
          } while (order > 0);
          a[i] = a[high_start];
          a[high_start] = element;
          if (order < 0) {
            element = a[i];
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
          }
        }
      }
      if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from = high_start;
      }
    }
  };

Mise à jour À partir de 2018, V8 utilise TimSort, merci @celwell. La source

La norme ECMAscript ne spécifie pas quel algorithme de tri doit être utilisé. En effet, différents navigateurs proposent différents algorithmes de tri. Par exemple, sort () de Mozilla / Firefox n'est pas stable (dans le sens de tri du mot) lors du tri d'une carte. Sort () d'IE est stable.

Après quelques recherches supplémentaires, il apparaît, pour Mozilla / Firefox, que Array.sort () utilise mergesort. Voir le code ici .

Je pense que cela dépend de l'implémentation du navigateur auquel vous faites référence.

Chaque type de navigateur possède sa propre implémentation de moteur javascript, cela dépend donc. Vous pouvez vérifier les dépôts de code source pour Mozilla et Webkit / Khtml pour différentes implémentations.

Cependant, IE est une source fermée, vous devrez donc peut-être demander à quelqu'un de Microsoft.

Depuis V8 v7.0 / Chrome 70, V8 utilise TimSort , l'algorithme de tri de Python. Chrome 70 est sorti le 13 septembre 2018.

Voir le post sur le blog de développement V8 pour plus de détails sur ce changement. Vous pouvez également lire le code source ou le patch 1186801 .

La fonction Array.sort () de JavaScript possède des mécanismes internes pour sélectionner le meilleur algorithme de tri (QuickSort, MergeSort, etc.) sur la base du type de données des éléments du tableau.

essayez ceci avec un tri rapide:

function sort(arr, compareFn = (a, b) => a <= b) {

    if (!arr instanceof Array || arr.length === 0) {
        return arr;
    }

    if (typeof compareFn !== 'function') {
        throw new Error('compareFn is not a function!');
    }

    const partition = (arr, low, high) => {
        const pivot = arr[low];
        while (low < high) {
            while (low < high && compareFn(pivot, arr[high])) {
                --high;
            }
            arr[low] = arr[high];
            while (low < high && compareFn(arr[low], pivot)) {
                ++low;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    };

    const quickSort = (arr, low, high) => {
        if (low < high) {
            let pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
        return arr;
    };

    return quickSort(arr, 0, arr.length - 1);
}