¿Cómo funciona sort () de Javascript?

¿Cómo ordena el siguiente código esta matriz para que esté en orden numérico?

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

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

Sé que si el resultado del cálculo es ...

Menos de 0 : "a" se ordena para ser un índice más bajo que "b".
Cero: "a" y "b" se consideran iguales y no se realiza ninguna clasificación.
Mayor que 0: "b" se ordena para ser un índice más bajo que "a".

¿Se llama muchas veces a la función de devolución de llamada de clasificación de matriz durante el transcurso de la clasificación?

Si es así, me gustaría saber qué dos números se pasan a la función cada vez. Supuse que primero tomó "25" (a) y "8" (b), seguido de "7" (a) y "41" (b), así que:

25 (a) - 8 (b) = 17 (mayor que cero, así que ordena "b" para que sea un índice más bajo que "a"): 8, 25

7 (a) - 41 (b) = -34 (menor que cero, así que ordena "a" para que sea un índice más bajo que "b": 7, 41

¿Cómo se ordenan los dos conjuntos de números entre sí?

¡Por favor, ayude a un novato con dificultades!

¿Se llama muchas veces a la función de devolución de llamada de clasificación de matriz durante el transcurso de la clasificación?

si

Si es así, me gustaría saber qué dos números se pasan a la función cada vez

Podrías encontrarte a ti mismo con:

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

EDITAR

Esta es la salida que tengo:

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

El intérprete de JavaScript tiene incorporado algún tipo de implementación de algoritmo . Llama a la función de comparación varias veces durante la operación de clasificación. El número de veces que se llama a la función de comparación depende del algoritmo particular, los datos que se van a clasificar y el orden en el que se encuentran antes de la clasificación.

Algunos algoritmos de clasificación funcionan mal en listas ya ordenadas porque hacen que hagan muchas más comparaciones que en el caso típico. Otros se adaptan bien a las listas previamente ordenadas, pero tienen otros casos en los que se les puede "engañar" para que rindan mal.

Hay muchos algoritmos de clasificación de uso común porque ningún algoritmo único es perfecto para todos los propósitos. Los dos que se utilizan con más frecuencia para la clasificación genérica son Quicksort y merge sort . La ordenación rápida es a menudo la más rápida de las dos, pero la ordenación por combinación tiene algunas propiedades interesantes que pueden convertirla en una mejor opción general. La ordenación por combinación es estable , mientras que la ordenación rápida no lo es. Ambos algoritmos son paralelizables, pero la forma en que funciona la ordenación por fusión hace que una implementación paralela sea más eficiente, en igualdad de condiciones.

Su intérprete de JavaScript en particular puede usar uno de esos algoritmos o algo completamente diferente. El estándar ECMAScript no especifica qué algoritmo debe utilizar una implementación conforme. Incluso niega explícitamente la necesidad de estabilidad.

Se comparan pares de valores, un par a la vez. Los pares que se comparan son un detalle de implementación; no asuma que serán los mismos en todos los navegadores. La devolución de llamada puede ser cualquier cosa (por lo que puede ordenar cadenas o números romanos o cualquier otra cosa en la que se le ocurra una función que devuelva 1,0, -1).

Una cosa a tener en cuenta con el tipo de JavaScript es que no se garantiza que sea estable.

¿Se llama muchas veces a la función de devolución de llamada de clasificación de matriz durante el transcurso de la clasificación?

Sí, eso es exactamente. La devolución de llamada se utiliza para comparar pares de elementos en la matriz según sea necesario para determinar en qué orden deben estar. Esa implementación de la función de comparación no es atípica cuando se trata de una ordenación numérica. Detalles en la especificación o en algunos otros sitios más legibles .

¿Se llama muchas veces a la función de devolución de llamada de clasificación de matriz durante el transcurso de la clasificación?

Dado que esta es una clasificación de comparación, dados N elementos, la función de devolución de llamada debe invocarse en promedio (N * Lg N) veces para una clasificación rápida como Quicksort . Si el algoritmo utilizado es algo como Bubble Sort , entonces la función de devolución de llamada se invocará en promedio (N * N) veces.

El número mínimo de invocaciones para una clasificación de comparación es (N-1) y eso es solo para detectar una lista ya ordenada (es decir, al principio de la clasificación de burbujas si no se producen intercambios).

Profundamente conocimiento

Si el resultado es negativo, a se ordena antes que b.

Si el resultado es positivo, b se ordena antes que a.

Si el resultado es 0, no se realizan cambios con el orden de clasificación de los dos valores.

NOTA:

Este código es la vista dentro del método de clasificación paso a paso.

SALIDA:

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]);
}

ejecute este código. Puede ver el proceso de clasificación exacto paso a paso desde el principio hasta el final.

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);

Para ayudar a aclarar el comportamiento de Array#sorty su comparador, considere este tipo de inserción ingenuo que se enseña en los cursos de programación para principiantes:

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);

Ignorando la elección de ordenación por inserción como algoritmo, se centran en la hardcoded comparador: arr[j-1] > arr[j]. Esto tiene dos problemas relevantes para la discusión:

1. El >operador se invoca en pares de elementos de matriz, pero muchas cosas que podría querer ordenar, como los objetos, no responden de >una manera razonable (lo mismo sería cierto si usáramos -).
2. Incluso si está trabajando con números, a menudo desea algún otro arreglo que no sea el ascendente que se ha incorporado aquí.

Podemos solucionar estos problemas agregando un comparefnargumento con el que esté familiarizado:

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));

Ahora la rutina de clasificación ingenua está generalizada. Puede ver exactamente cuándo se invoca esta devolución de llamada, respondiendo a su primer conjunto de inquietudes:

¿Se llama muchas veces a la función de devolución de llamada de clasificación de matriz durante el transcurso de la clasificación? Si es así, me gustaría saber qué dos números se pasan a la función cada vez

Ejecutar el siguiente código muestra que, sí, la función se llama muchas veces y puede usarla console.logpara ver qué números se pasaron:

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))
);

Usted pregunta:

¿Cómo se ordenan los dos conjuntos de números entre sí?

Para ser precisos con la terminología, ay bno son conjuntos de números, son objetos en la matriz (en su ejemplo, son números).

La verdad es que no importa cómo se clasifiquen porque depende de la implementación. Si hubiera usado un algoritmo de ordenación diferente al de ordenación por inserción, el comparador probablemente se invocaría en diferentes pares de números, pero al final de la llamada de ordenación, el invariante que le importa al programador de JS es que la matriz de resultados se ordena de acuerdo con el comparador, asumiendo que el comparador devuelve valores que se adhieren al contrato que estableció (<0 cuando a < b, 0 cuando a === by> 0 cuando a > b).

En el mismo sentido en que tengo la libertad de cambiar la implementación de mi clasificación siempre que no infrinja mi especificación, las implementaciones de ECMAScript son libres de elegir la implementación de clasificación dentro de los límites de la especificación del lenguaje , por Array#sortlo que probablemente producirá diferentes llamadas de comparador en diferentes motores. Uno no escribiría código donde la lógica se basa en alguna secuencia particular de comparaciones (ni el comparador debería producir efectos secundarios en primer lugar).

Por ejemplo, el motor V8 (en el momento de escribir este artículo) invoca Timsort cuando la matriz es mayor que un número precalculado de elementos y usa una ordenación de inserción binaria para fragmentos de matriz pequeños. Sin embargo, solía usar quicksort que es inestable y probablemente daría una secuencia diferente de argumentos y llamadas al comparador.

Dado que las diferentes implementaciones de ordenación utilizan el valor de retorno de la función de comparación de manera diferente, esto puede llevar a un comportamiento sorprendente cuando el comparador no se adhiere al contrato. Vea este hilo para ver un ejemplo.

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

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

SALIDA

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

en mi navegador (Google Chrome versión 70.0.3538.77 (compilación oficial) (64 bits)) en la primera iteración, el argumento a es el segundo elemento de una matriz y el argumento b es el primer elemento de una matriz.

si la función Comparar devuelve

1. El valor negativo que b se mueve hacia adelante a a.
2. Valor positivo que a se mueve hacia adelante a b.
3. 0 (cero) tanto a como b permanecerán como están.