Comment fonctionne sort () de Javascript?

Comment le code suivant trie-t-il ce tableau dans l'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 index inférieur à "b".
Zéro: "a" et "b" sont considérés comme égaux et aucun tri n'est effectué.
Supérieur à 0: "b" est trié pour être un indice inférieur à "a".

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

Si tel est le cas, j'aimerais savoir quels deux nombres sont passés à chaque fois dans la fonction. J'ai supposé qu'il fallait d'abord "25" (a) et "8" (b), suivis de "7" (a) et "41" (b), donc:

25 (a) - 8 (b) = 17 (supérieur à zéro, donc trier "b" comme un indice inférieur à "a"): 8, 25

7 (a) - 41 (b) = -34 (inférieur à zéro, donc trier "a" comme un indice inférieur à "b": 7, 41

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

Veuillez aider un débutant en difficulté!

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

Oui

Si tel est le cas, j'aimerais savoir quels sont les deux nombres passés dans la fonction à chaque fois

Vous pourriez vous découvrir avec:

array.sort((a,b) => {
  console.log(`comparing ${a},${b}`);
  return a > b ? 1
               : a === b ? 0 
                         : -1;
});

ÉDITER

Voici le résultat que j'ai:

25,8
25,7
8,7
25,41

L'interpréteur JavaScript a une sorte d' algorithme de tri implémentation d' intégrée. Il appelle la fonction de comparaison un certain nombre de fois pendant l'opération de tri. Le nombre d'appels de la fonction de comparaison dépend de l'algorithme particulier, des données à trier et de l'ordre dans lequel elle se trouve avant le tri.

Certains algorithmes de tri fonctionnent mal sur des listes déjà triées car cela les amène à faire beaucoup plus de comparaisons que dans le cas typique. D'autres se débrouillent bien avec des listes pré-triées, mais ont d'autres cas où ils peuvent être "amenés" à avoir de mauvaises performances.

Il existe de nombreux algorithmes de tri couramment utilisés car aucun algorithme n'est parfait pour tous les usages. Les deux types les plus souvent utilisés pour le tri générique sont le tri rapide et le tri par fusion . Quicksort est souvent le plus rapide des deux, mais le tri par fusion a quelques propriétés intéressantes qui peuvent en faire un meilleur choix global. Le tri par fusion est stable , contrairement à Quicksort. Les deux algorithmes sont parallélisables, mais le fonctionnement du tri par fusion rend une implémentation parallèle plus efficace, toutes choses étant égales par ailleurs.

Votre interpréteur JavaScript particulier peut utiliser l'un de ces algorithmes ou tout autre chose. La norme ECMAScript ne spécifie pas quel algorithme une implémentation conforme doit utiliser. Il nie même explicitement le besoin de stabilité.

Les paires de valeurs sont comparées, une paire à la fois. Les paires comparées sont un détail d'implémentation - ne supposez pas qu'elles seront identiques sur tous les navigateurs. Le rappel peut être n'importe quoi (vous pouvez donc trier des chaînes ou des chiffres romains ou tout autre élément où vous pouvez trouver une fonction qui renvoie 1,0, -1).

Une chose à garder à l'esprit avec le tri de JavaScript est qu'il n'est pas garanti qu'il soit stable.

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

Oui, c'est exactement ça. Le rappel est utilisé pour comparer des paires d'éléments dans le tableau selon les besoins pour déterminer dans quel ordre ils doivent être. Cette implémentation de la fonction de comparaison n'est pas atypique lorsqu'il s'agit d'un tri numérique. Détails dans la spécification ou sur certains autres plus lisibles sites.

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

Puisqu'il s'agit d'un tri de comparaison, étant donné N éléments, la fonction de rappel doit être appelée en moyenne (N * Lg N) fois pour un tri rapide comme Quicksort . Si l'algorithme utilisé est quelque chose comme Bubble Sort , alors la fonction de rappel sera appelée en moyenne (N * N) fois.

Le nombre minimum d'appels pour un tri de comparaison est (N-1) et c'est uniquement pour détecter une liste déjà triée (c'est-à-dire au début dans Bubble Sort si aucun échange ne se produit).

Connaissance approfondie

Si le résultat est négatif, a est trié avant b.

Si le résultat est positif, b est trié avant a.

Si le résultat est 0, aucune modification n'est effectuée avec l'ordre de tri des deux valeurs.

REMARQUE:

Ce code est la vue à l'intérieur de la méthode de tri étape par étape.

PRODUCTION:

let arr = [90, 1, 20, 14, 3, 55];
var sortRes = [];
var copy = arr.slice();		//create duplicate array
var inc = 0;	//inc meant increment
copy.sort((a, b) => {
	sortRes[inc] = [ a, b, a-b ];
	inc += 1;
	return a - b;
});
var p = 0;
for (var i = 0; i < inc; i++) {
	copy = arr.slice();
	copy.sort((a, b) => {
		p += 1;
		if (p <= i ) {
			return a - b;
		}
		else{
			return false;
		}
	});
	p = 0;
	console.log(copy +' \t a: '+ sortRes[i][0] +' \tb: '+ sortRes[i][1] +'\tTotal: '+ sortRes[i][2]);
}

exécutez ce code. Vous pouvez voir le processus de tri étape par étape exact du début à la fin.

var array=[25, 8, 7, 41]
var count = 1;
array.sort( (a,b) => { 
console.log(`${count++}). a: ${a} | b: ${b}`);
return a-b;
});
console.log(array);

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

array.sort(function(a,b){
  console.log(`a = ${a} , b = ${b}`);
  return a - b
});

PRODUCTION

• a = 8, b = 25
• a = 7, b = 8
• a = 41, b = 7
• a = 41, b = 8
• a = 41, b = 25

dans mon navigateur (version 70.0.3538.77 de Google Chrome (version officielle) (64 bits)) dans la première itération, l'argument a est le deuxième élément d'un tableau et l'argument b est le premier élément d'un tableau.

si la fonction Compare renvoie

1. La valeur négative supérieure à b est déplacée vers a.
2. La valeur positive supérieure à a est déplacée vers b.
3. 0 (Zéro) les deux a et b resteront tels quels.