72 votes

Quelle est la stabilité de la méthode Array.sort() dans les différents navigateurs ?

Je sais que la spécification ECMA script ne précise pas quel algorithme utiliser pour trier les tableaux, ni si le tri doit être stable.

J'ai trouvé ces informations pour Firefox qui spécifie que firefox utilise un tri stable.

Quelqu'un connaît-il IE 6/7/8, Chrome et Safari ?

74voto

Crescent Fresh Points 54070

A partir de l'ES2019, sort doit être stable. Dans ECMAScript 1ère édition jusqu'à ES2018, il était autorisé d'être instable.

Cas de test simple (ignorez l'intitulé, la deuxième série de chiffres devrait être séquentielle si le tri du moteur est stable). Note : Ce scénario de test ne fonctionne pas pour certaines versions de Chrome (techniquement, de V8) qui changent d'algorithme de tri en fonction de la taille du tableau, utilisant un tri stable pour les petits tableaux mais un tri instable pour les tableaux plus grands. ( Détails .) Voir la fin de la question pour une version modifiée qui rend le tableau suffisamment grand pour déclencher le comportement.

Le tri d'IE a été stable aussi longtemps que je l'ai utilisé (donc IE6). Je vérifie à nouveau dans IE8 et il semble que ce soit toujours le cas.

Et bien que la page de Mozilla dont vous donnez le lien indique que le tri de Firefox est stable, je suis certain que ce n'était pas toujours le cas avant (et y compris) Firefox 2.0.

Quelques résultats rapides :

  • IE6+ : stable
  • Firefox < 3 : instable
  • Firefox >= 3 : stable
  • Chrome < 70 : instable
  • Chrome >= 70 : stable
  • Opera < 10 : instable
  • Opera >= 10 : stable
  • Safari 4 : stable
  • Bord : instable pour les longs tableaux ( >512 éléments )

Tous les tests ont été effectués sous Windows.

Voir aussi : Implémentation d'un algorithme de tri rapide et stable en javascript

Ce scénario de test (modifié à partir de aquí ) démontrera le problème dans V8 (par exemple, Node v6, Chrome < v70) en s'assurant que le tableau a suffisamment d'entrées pour choisir la méthode de tri "plus efficace" ; ceci est écrit avec de très vieux moteurs JavaScript en tête, donc sans fonctionnalités modernes :

function Pair(_x, _y) {
    this.x = _x;
    this.y = _y;
}
function pairSort(a, b) {
    return a.x - b.x;
}
var y = 0;
var check = [];
while (check.length < 100) {
    check.push(new Pair(Math.floor(Math.random() * 3) + 1, ++y));
}
check.sort(pairSort);
var min = {};
var issues = 0;
for (var i = 0; i < check.length; ++i) {
    var entry = check[i];
    var found = min[entry.x];
    if (found) {
        if (found.y > entry.y) {
            console.log("Unstable at " + found.i + ": " + found.y + " > " + entry.y);
            ++issues;
        }
    } else {
        min[entry.x] = {x: entry.x, y: entry.y, i: i};
    }
}
if (!issues) {
    console.log("Sort appears to be stable");
}

0 votes

Il semble que Chrome (V8) restera ainsi : code.google.com/p/v8/issues/detail?id=90

1 votes

ofb.net/~sethml/est-sort-stable.html ? (Je l'ai sauvegardé sur l'archive web au cas où)

1 votes

À partir d'IE9, le triage d'IE n'est plus stable. Chrome est stable pour les tableaux <10 éléments (c'est un effet secondaire de l'utilisation du tri par insertion comme cas de base pour leur quicksort).

15voto

Dummy00001 Points 6088

J'aimerais partager une astuce que j'utilise régulièrement en C/C++ pour qsort() .

La fonction sort() de JS permet de spécifier une fonction de comparaison. Créez un deuxième tableau de la même longueur et remplissez-le de nombres croissants à partir de 0.

function stableSorted(array, compareFunction) {
  compareFunction = compareFunction || defaultCompare;
  var indicies = new Array(array.length);
  for (var i = 0; i < indicies.length; i++)
    indicies[i] = i;

Ce sont des index dans le tableau original. Nous allons trier le second tableau. Créez une fonction de comparaison personnalisée.

  indicies.sort(function(a, b)) {

Elle récupère les deux éléments du second tableau : elle les utilise comme index dans les tableaux d'origine et compare les éléments.

    var aValue = array[a], bValue = array[b];
    var order = compareFunction(a, b);
    if (order != 0)
      return order;

Si des éléments se trouvent être égaux, il faut alors comparer leurs indices pour rendre l'ordre stable.

   if (a < b)
     return -1;
   else
     return 1;
  });

Après le sort(), le deuxième tableau contiendra des index que vous pourrez utiliser pour accéder aux éléments du tableau original dans un ordre trié stable.

  var sorted = new Array(array.length);
  for (var i = 0; i < sorted.length; i++)
    sorted[i] = array[indicies[i]];
  return sorted;
}

// The default comparison logic used by Array.sort(), if compareFunction is not provided:
function defaultCompare(a, b) {
  a = String(a);
  b = String(b);
  if (a < b) return -1;
  else if (a > b) return 1;
  else return 0;
}

En général, les algorithmes de tri stables ne font que mûrir et nécessitent toujours plus de mémoire supplémentaire par rapport au bon vieux qsort. Je suppose que c'est la raison pour laquelle très peu de spécifications imposent le tri stable.

10voto

Mathias Bynens Points 41065

À partir de V8 v7.0 et Chrome 70, nos Array.prototype.sort est maintenant stable.

0voto

dongryphon Points 655

Au cas où quelqu'un trouverait cela utile, j'avais un polyfill pour cela que je supprime maintenant :

const stable = (count => {
    const
        array = new Array(count),
        buckets = {};

    let i, k, v;

    for (i = 0; i < count; ++i) {
        array[i] = [Math.floor(Math.random() * 3) + 1, i + 1];  // [1..3, 1..count]
    }

    array.sort((a, b) => a[0] - b[0]);

    for (i = 0; i < count; ++i) {
        [k, v] = array[i];

        if (buckets[k] > v) {
            return false;
        }

        buckets[k] = v;
    }

    return true;
// Edge's JS engine has a threshold of 512 before it goes unstable, so use a number beyond that:
})(600);

if (!stable) {
    const
        { prototype } = Array,
        { sort } = prototype;

    Object.defineProperty(prototype, 'sort', {
        configurable : true,

        value(sortFn) {
            const
                array = this,
                len = array.length,
                temp = new Array(len);

            let i;

            for (i = len; i-- > 0; /* empty */) {
                temp[i] = i;
            }

            sortFn = sortFn || defaultSort;

            sort.call(temp, (index1, index2) => sortFn(array[index1], array[index2]) || index1 - index2);

            // we cannot do this directly into array since we may overwrite an element before putting it into the
            // correct spot:
            for (i = len; i-- > 0; /* empty */) {
                temp[i] = array[temp[i]];
            }

            for (i = len; i-- > 0; /* empty */) {
                array[i] = temp[i];
            }

            return array;
        }
    });
}

-2voto

unomi Points 1846

Si vous cherchez une liste de navigateurs dans lesquels vous devriez utiliser un algorithme de tri non natif, je vous suggère les suivants Ne le fais pas. .

Au lieu de cela, faites une sorte de sanity check lorsque le script se charge et prenez votre décision à partir de là.

Comme la spécification n'exige pas un comportement particulier à cet égard, elle n'est pas à l'abri d'une modification ultérieure, même au sein de la même ligne de navigateur.

Vous pouvez soumettre un correctif à http://www.browserscope.org/ d'inclure de tels tests dans leur suite. Mais encore une fois, la détection des fonctionnalités est supérieure à la détection des navigateurs.

10 votes

Je ne suis pas sûr que vous puissiez écrire un contrôle d'intégrité qui garantirait un tri stable. Il pourrait sembler stable à un moment donné, mais devenir instable le moment suivant. Cela pourrait se produire, par exemple, si le tri dépendait d'une manière ou d'une autre de l'emplacement des objets JavaScript en mémoire - ce qui peut être imprévisible.

1 votes

@RichDougherty -- Je suis sûr que vous ne pouvait pas . Vous ne pouvez pas prouver qu'un algorithme de tri est stable en l'exécutant ! Ce serait comme essayer de prouver qu'une voiture est fiable en la conduisant une fois autour du pâté de maisons. Vous devez analyser l'algorithme et son implémentation.

0 votes

@Malvolio, je pense que nous sommes d'accord. Je disais que si un test réussit maintenant, il n'est certainement pas garanti qu'il réussisse à l'avenir, d'où la futilité de faire une vérification de la stabilité au moment du chargement.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X