J'ai vu cette fonction de tri fonctionne bien: mais je ne comprends pas vraiment la mécanique de cette petite fonction. Quand il s'agit de comparer a et b , quel nombre de tableau est-il vraiment comparatif? Si disait, il a ramassé les deux premiers numéros 1 et 5 , la fonction retournera -4 . Qu'est-ce que cela signifie pour l'ordre de tri? Ou est-ce juste la valeur booléenne négative? Même si c'est, comment se passe-t-il vraiment?
3 Réponses :
Vous avez 3 options moins (-), égale (==) et plus (+):
a - b <0 ALORS a avant B
-
est égal à : Peu importe
- plus : si
a - b> 0 puis b avant a
Voir ce fil pour plus d'informations: Mise en œuvre JavaScript Array.sort?
Fondamentalement, le tri fonctionne en comparant deux éléments à la fois. Une comparaison est plus qu'un booléen - vous avez trois options: moins que, égales et supérieures à. En JavaScript, ces trois valeurs sont représentées par N <0, 0 et N> 0 respectivement.
En d'autres termes, les numéros négatifs signifient Pour répondre à la question plus large: il existe des algorithmes relativement rapides pour trier une liste en comparant ses éléments. Le plus populaire est Quicksort ; Cependant, Quicksort n'est pas stable, donc certains moteurs (Firefox's à coup sûr) utilisent un algorithme différent. Un type simple stable est Mergesort .
Les algorithmes de tri sont souvent certains des premiers algorithmes analysés dans des classes d'introduction en CS car elles sont simples mais toujours intéressantes et non attrayantes pour illustrer comment analyser les algorithmes en général. Vous devriez lire à leur sujet pour cette raison et simplement parce qu'ils sont assez cool.
Légèrement aléatoire de côté:
Vous pouvez également imaginer d'utiliser un type spécial (comme un énorme) pour ce genre de chose. La fonction de comparaison pourrait renvoyer a ; 0 signifie a = b et moyen positif a> b . .
lt , gt ou eq selon le cas, par exemple. Cependant, dans une langue dynamique comme JavaScript, il est beaucoup plus facile d'utiliser des chiffres. Dans des langues plus obsédées par des types (comme Haskell :)), l'utilisation d'un type de commande spécial a plus de sens.
D'accord, parcouru l'entrée de Mergesort Wikipedia et cela a du sens (largement). Mais si je voulais examiner la manière dont la mise en œuvre de la fonction de tri a été écrite dans JavaScript, comment puis-je?
@Capex - JavaScript n'utilise aucun algorithme de tri, c'est-à-dire qu'il n'y a aucune spécification qui dit "doit utiliser la tri des bulles" ou quoi que ce soit. Différentes implémentations JavaScript (dans différents navigateurs) peuvent utiliser différents algorithmes de tri. Mais la méthode de tri des matrices avec les paramètres A et B sera toujours la même pour les programmeurs JavaScript, car il fournit simplement un moyen de comparer l'algorithme sous-jacent de comparer deux valeurs données.
Je pense que la question ici est que la fonction de tri intégrée est probablement pas écrite dans JavaScript - je soupçonne que la plupart des moteurs le mettent en œuvre dans un code natif pour des raisons de performance. Vous pouvez voir le tri ici si vous Faites défiler un peu. Si vous voulez juste un algorithme de tri en JavaScript, ici alphabétisé qui a beaucoup de commentaire.
Lorsque vous passez une fonction à si Au fait, quel algorithme array.sort , il sera utilisé pour comparer A et B . Comment ils seront triés dépend de la fonction de la fonction:
résultat <0 , alors A est livré avant B ;
résultat == 0 , puis A et b est déjà dans le bon ordre;
résultat> 0 , puis A est après B .
trier est appelé sans argument, les éléments sont convertis en cordes et comparé alfabétiquement.
tri dépend entièrement de la mise en œuvre du navigateur. Il pourrait être rapide de trier, fusionner un tri ou autre chose. La norme ECMAScript ne spécifie aucune exigence à cet égard.