Pour aider à clarifier le comportement des Array#sort et son comparateur, considérez ce naïf tri par insertion enseignés dans les cours de programmation débutants :
const sort = arr => {
for (let i = 1; i < arr.length; i++) {
for (let j = i; j && arr[j-1] > arr[j]; j--) {
[arr[j], arr[j-1]] = [arr[j-1], arr[j]];
}
}
};
const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array);
console.log("" + array);
Sans tenir compte du choix de l'algorithme de tri par insertion, il convient de se concentrer sur l'algorithme de tri par insertion. codé en dur comparateur : arr[j-1] > arr[j] . Cela pose deux problèmes pertinents pour la discussion :
- Les
> est invoqué sur des paires d'éléments de tableau, mais de nombreux éléments que vous pourriez vouloir trier, tels que les objets, ne répondent pas à l'opérateur > de manière raisonnable (il en irait de même si l'on utilisait des - ).
- Même si vous travaillez avec des nombres, vous avez souvent besoin d'un autre arrangement que le tri ascendant qui a été intégré ici.
Nous pouvons résoudre ces problèmes en ajoutant un comparefn que vous connaissez bien :
const sort = (arr, comparefn) => {
for (let i = 1; i < arr.length; i++) {
for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
[arr[j], arr[j-1]] = [arr[j-1], arr[j]];
}
}
};
const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array, (a, b) => a - b);
console.log("" + array);
sort(array, (a, b) => b - a);
console.log("" + array);
const objArray = [{id: "c"}, {id: "a"}, {id: "d"}, {id: "b"}];
sort(objArray, (a, b) => a.id.localeCompare(b.id));
console.log(JSON.stringify(objArray, null, 2));
La routine de tri naïf est maintenant généralisée. Vous pouvez voir exactement quand ce rappel est invoqué, ce qui répond à votre première préoccupation :
La fonction de rappel du tri de tableaux est-elle appelée plusieurs fois au cours du tri ? Si c'est le cas, j'aimerais savoir quels sont les deux nombres qui sont transmis à la fonction à chaque fois
L'exécution du code ci-dessous montre que, oui, la fonction est appelée plusieurs fois et que vous pouvez utiliser console.log pour voir quels numéros ont été transmis :
const sort = (arr, comparefn) => {
for (let i = 1; i < arr.length; i++) {
for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
[arr[j], arr[j-1]] = [arr[j-1], arr[j]];
}
}
};
console.log("on our version:");
const array = [3, 0, 4, 5];
sort(array, (a, b) => console.log(a, b) || (a - b));
console.log("" + array);
console.log("on the builtin:");
console.log("" +
[3, 0, 4, 5].sort((a, b) => console.log(a, b) || (a - b))
);
Vous demandez :
Comment les deux ensembles de nombres sont-ils ensuite triés l'un par rapport à l'autre ?
Pour être précis dans la terminologie, a y b ne sont pas ensembles de nombres - ce sont des objets dans le tableau (dans votre exemple, ce sont des nombres).
La vérité est que cela n'a pas d'importance comment ils sont triés parce qu'ils dépendent de la mise en œuvre. Si j'avais utilisé un algorithme de tri différent du tri par insertion, le comparateur serait probablement invoqué sur différentes paires de nombres, mais à la fin de l'appel au tri, l'invariant qui importe au programmeur JS est que le tableau de résultats est trié selon le comparateur, en supposant que le comparateur renvoie des valeurs qui adhèrent au contrat que vous avez énoncé (< 0 quand a < b , 0 lorsque a === b et > 0 lorsque a > b ).
De même que je suis libre de modifier l'implémentation de mon tri tant que je n'enfreins pas ma spécification, les implémentations d'ECMAScript sont libres de choisir l'implémentation du tri dans les limites de la norme spécification de la langue Ainsi Array#sort produira probablement des appels de comparateurs différents sur des moteurs différents. On n'écrirait pas un code dont la logique repose sur une séquence particulière de comparaisons (et le comparateur ne devrait pas non plus produire d'effets secondaires).
Par exemple, le moteur V8 (au moment de la rédaction) invoque Timsort lorsque le tableau est plus grand qu'un certain nombre d'éléments calculés à l'avance et utilise une fonction tri par insertion binaire pour les petits morceaux de tableau. Cependant, il a l'habitude d'utiliser tri sélectif qui est instable et qui donnerait probablement une séquence différente d'arguments et d'appels au comparateur.
Étant donné que les différentes implémentations de tri utilisent différemment la valeur de retour de la fonction de comparaison, cela peut conduire à un comportement surprenant lorsque le comparateur ne respecte pas le contrat. Voir ce fil à titre d'exemple.
