Comment fonctionne la fonction sort() de Javascript ?

Question

Comment le code suivant permet-il de trier ce tableau par ordre numérique ?

var array=[25, 8, 7, 41]

array.sort(function(a,b){
  return a - b
})

Je sais que si le résultat du calcul est...

Inférieur à 0 : "a" est trié pour être un indice inférieur à "b".
Zéro : "a" et "b" sont considérés comme égaux et aucun tri n'est effectué.
Supérieure à 0 : "b" est trié pour être un indice inférieur à "a".

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. J'ai supposé qu'elle prenait d'abord "25"(a) et "8"(b), puis "7"(a) et "41"(b), donc.. :

25(a) - 8(b) = 17 (supérieur à zéro, donc trier "b" pour qu'il soit un indice inférieur à "a") : 8, 25

7(a) - 41(b) = -34 (inférieur à zéro, donc trier "a" pour qu'il soit un indice inférieur à "b" : 7, 41

Comment les deux ensembles de nombres sont-ils ensuite triés l'un par rapport à l'autre ?

Aidez un débutant qui a du mal à s'y retrouver !

Answer 1

La fonction de rappel du tri de tableaux est-elle appelée plusieurs fois au cours du tri ?

Oui, c'est exactement cela. Le rappel est utilisé pour comparer les paires d'éléments du tableau afin de déterminer l'ordre dans lequel ils doivent être placés. Cette implémentation de la fonction de comparaison n'est pas atypique lorsqu'il s'agit d'un tri numérique. Détails dans le cahier des charges ou sur certains autres plus lisible sites.

Answer 2

La fonction de rappel du tri de tableaux est-elle appelée plusieurs fois au cours du tri ?

Comme il s'agit d'un tri par comparaison, étant donné N éléments, la fonction de rappel devrait être invoquée en moyenne (N * Lg N) fois pour un tri rapide tel que Tri sélectif . Si l'algorithme utilisé est du type Tri à bulles alors la fonction de rappel sera invoquée en moyenne (N * N) fois.

Le nombre minimum d'invocations pour un tri par comparaison est de (N-1), et ce uniquement pour détecter une liste déjà triée (c'est-à-dire au début du tri à bulles s'il n'y a pas de permutation).

Answer 3

La fonction de rappel du tri de tableaux est-elle appelée plusieurs fois au cours du tri ?

Oui

Si c'est le cas, j'aimerais savoir quels sont les deux nombres qui sont transmis à la fonction à chaque fois.

a : Le premier élément de comparaison.

b : Le deuxième élément de comparaison.

Dans l'exemple suivant, a sera "2" et b sera "3" lors de la première itération

Comment les deux ensembles de nombres sont-ils ensuite triés l'un par rapport à l'autre ?

Les éléments sont triés en fonction de la valeur de retour de la fonction de comparaison.

supérieur à 0 : trier a après b

inférieur à 0 : trier a avant b

égal à 0 : maintien de l'ordre initial de a et b

En voici un exemple

var arr = [3, 2, 1, 5, 4, 6, 7, 9, 8, 10];
console.log(arr.sort((a, b) => {
  console.log(a - b, a, b);
  //b-a if sorting in decending order
  return a - b; 
}));