Tri en JavaScript: chaque fonction de comparaison doit-elle avoir une déclaration "retour 0"?

J'ai récemment lu de nombreuses réponses sur le tri en JavaScript et je me heurte souvent à une fonction de comparaison qui ressemble à ceci:

array.sort(function(a,b){ a > b ? 1 : -1; });

C'est donc une fonction de comparaison qui renvoie 1 si a est supérieur à b et -1 si a est inférieur à OU EQUAL TO b . Comme décrit sur MDN ( lien ), une fonction de comparaison peut également renvoyer zéro, pour s'assurer que la position relative de deux éléments reste inchangée:

Si compareFunction (a, b) renvoie 0, laissez a et b inchangés l'un par rapport à l'autre, mais triés par rapport à tous les éléments différents.

Donc, les exemples officiels ressemblent plus à ceci:

 function compare(a, b) { if (a < b) return -1; if (a > b) return 1; return 0; }

Et en ajoutant une déclaration de return 0 , l'algorithme de tri nécessite souvent moins d'itérations et s'exécute plus rapidement ( JSPerf ).

Je me demandais donc s'il y avait un avantage sur l'omission d'une déclaration de return 0 .

Je me suis rendu compte que sur MDN, il dit aussi:

Remarque: la norme ECMAscript ne garantit pas ce comportement et, par conséquent, tous les navigateurs (par exemple, les versions de Mozilla remontant à au moins 2003) respectent cela.

En se référant au comportement, a et b doivent rester inchangés si 0 est retourné. Alors peut-être, en retournant 0, nous obtenons un tableau trié légèrement différent dans différents navigateurs? Cela pourrait-il être une raison? Et y a-t-il d'autres bonnes raisons de ne pas revenir à zéro?

Je me demandais donc s'il y avait un avantage sur l'omission d'une déclaration de retour 0.

Moins de lettres à saisir. Et il pourrait être un peu plus rapide en raison de la comparaison omise. Tous les autres effets sont des inconvénients .

Je me suis rendu compte que sur MDN, il dit aussi:

Remarque: la norme ECMAscript ne garantit pas ce comportement et, par conséquent, tous les navigateurs (par exemple, les versions de Mozilla remontant à au moins 2003) respectent cela.

En se référant au comportement, a et b doivent rester inchangés si 0 est retourné.

Que la position de a et b reste inchangée n'est que l'exigence d'un tri stable . Ce n'est pas un comportement spécifié, et certains navigateurs ont implémenté un algorithme de tri non stable.

Cependant, le but réel de retourner zéro est que ni a est trié avant b (comme si moins de 0) ni que b était trié avant a (comme si c'était plus grand que 0) – essentiellement quand a est égal à b . Ceci est un incontournable pour une comparaison , et tous les algorithmes de tri l'obéissent.

Pour produire une commande valide et satisfaisante (mathématiquement: diviser les éléments en classes d'équivalence totalement ordonnées ), une comparaison doit avoir certaines propriétés. Ils sont listés dans la spécification pour sort comme des exigences pour une " fonction de comparaison cohérente ".

Le plus important est la réflexivité, exigeant qu'un élément a soit égal à a (lui-même). Une autre façon de dire ceci est:

compare(a, a) doit toujours revenir 0

Que se passe-t-il lorsqu'une fonction de comparaison ne satisfait pas cela (comme celui que vous avez rencontré évidemment)?

La spécification indique

Si comparefn […] n'est pas une fonction de comparaison cohérente pour les éléments de ce tableau, le comportement de sort est défini par la mise en œuvre.

Ce qui signifie essentiellement: si vous fournissez une fonction de comparaison invalide, le tableau ne sera probablement pas trié correctement. Il peut être permuté au hasard, ou l'appel de sort peut même ne pas se terminer.

Alors peut-être, en retournant 0, nous obtenons un tableau trié légèrement différent dans différents navigateurs? Cela pourrait-il être une raison?

Non, en renvoyant 0, vous obtenez un tableau correctement trié sur les navigateurs (ce qui pourrait être différent en raison du type instable). La raison en est que, en ne retournant pas 0, vous obtenez des tableaux permutés légèrement différents (si vous en êtes le cas), produisez peut-être même le résultat attendu, mais généralement d'une manière plus compliquée.

Alors, qu'est-ce qui pourrait arriver si vous ne renvoyez pas 0 pour des articles équivalents? Certaines implémentations n'ont aucun problème avec cela, car elles ne comparent jamais un élément à lui-même (même s'il apparaît à plusieurs positions dans le tableau) – on peut l'optimiser et omettre l'appel coûteux à la fonction de comparaison lorsqu'il est déjà connu que le résultat doit Être 0.

L'autre extrême serait une boucle sans fin. En supposant que vous aviez deux éléments équivalents l'un après l'autre, vous compareriez ce dernier avec le premier et réalisez que vous deviez les échanger. En vérifiant à nouveau, ce dernier serait encore plus petit que le premier et vous devriez les échanger à nouveau. Etc…

Cependant, un algorithme efficace ne teste en aucun cas les éléments déjà comparés, et généralement, la mise en œuvre se terminera. Pourtant, il pourrait faire plus ou moins de swaps qui n'avaient pas été nécessaires, et prendra donc plus de temps qu'avec une fonction de comparaison cohérente.

Et y a-t-il d'autres bonnes raisons de ne pas revenir à zéro?

Étant paresseux et espérant que le tableau ne contient pas de doublons.

Une méthode de comparaison devrait respecter le contrat

 Math.sign(compare(a, b)) = -Math.sign(compare(b, a))

Si vous renvoyez une réponse non nulle lorsque a == b, ce contrat est violé.