Javascript Girl
  1. Javascript Girl
  3. L'implémentation Javascript Array.sort?
Intereting Posts
Meteor: Erreur d'appel API basique de Facebook: jeton d'accès Comment supprimer l'iframe de la page parent en utilisant une fonction à l'intérieur de l'iframe? Comment implémenter une recherche en direct dans Meteor sans que l'entrée de texte soit floue après chaque lettre? Retarder l'exécution de la fonction JavaScript Combinez deux tableaux en JavaScript Existe-t-il des dictionnaires en javascript comme python? Comment obtenir la clé json et la valeur en javascript? L'espace de noms de l'événement ne s'affiche pas avec jquery Bibliothèques Javascript AOP Avertissement: setState (…): Impossible de mettre à jour pendant une transition d'état existante avec redux / immuable Json.Parse échappe aux nouveaux caractères Théorie du double contour de base Comment passer ces chaînes de php à javascript Comment supprimer les éléments DOM sans fuite de mémoire? Comment trier le tableau dans ng-options par clé?

L'implémentation Javascript Array.sort?

Quel algorithme utilise la fonction JavaScript Array#sort() ? Je comprends qu'il peut prendre toutes sortes d'arguments et de fonctions pour effectuer différentes sortes de sortes, je m'interesse simplement à quel algorithme utilise le type de vanille.

    Si vous regardez ce bug 224128 , il semble que MergeSort soit utilisé par Mozilla.

    Je viens d'examiner la source WebKit (Chrome, Safari …). Selon le type de tableau, différentes méthodes de tri sont utilisées:

    Les tableaux numériques (ou les tableaux de type primitif) sont triés en utilisant la fonction de bibliothèque standard C ++ std::qsort qui implémente une certaine variation de quicksort (généralement introsort ).

    Les tableaux contigus de type non numérique sont stringifiés et triés en utilisant fusion, si disponible (pour obtenir un tri stable) ou qsort si aucun type de fusion n'est disponible.

    Pour d'autres types (tableaux non contigus et vraisemblablement pour les tableaux associatifs) WebKit utilise soit le tri de sélection (qu'ils appellent le type "min" ), soit, dans certains cas, il sort via un arbre AVL. Malheureusement, la documentation ici est assez vague, donc vous devriez tracer les chemins de code pour voir réellement les types de méthode de tri utilisés.

    Et puis il y a des gemmes 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 que quiconque répare "cela" a une meilleure compréhension de l'exécution asymptotique que l'auteur de ce commentaire, et se rend compte que le type radix a une description d'exécution légèrement plus complexe que simplement O (N).

    (Merci à phsource pour indiquer l'erreur dans la réponse originale.)

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

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

    https://github.com/v8/v8/blob/master/src/js/array.js

    Des 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; } } };

    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épendra de la mise en œuvre du navigateur auquel vous vous référez.

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

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