Tengo una matriz de objetos como:

var arr = [{index: 1, key: undefined}, {index: 2, key: undefined},{index: 3, key: undefined},{index: 4, key: undefined},{index: 5, key: undefined},{index: 6, key: undefined},{index: 7, key: undefined},{index: 8, key: undefined},{index: 9, key: undefined},{index: 10, key: undefined},{index: 11, key: undefined},{index: 12, key: undefined},{index: 13, key: undefined},{index: 14, key: undefined},{index: 15, key: undefined},{index: 16, key: undefined},{index: 17, key: undefined},{index: 18, key: undefined},{index: 19, key: undefined} ]

Quiero ordenar el arreglo arr por clave: aquí hay un valor indefinido. El valor de retorno debe ser el mismo que arr. Pero cuando ejecuto:

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

El resultado no es el mismo que esperaba, se cambia el orden de la matriz. ¿Alguna idea sobre este problema?

Mi resultado: https://imgur.com/a/4NyDq

Actualización: Probado con otra matriz:

var b = [{index: 1, key: 10}, {index: 2, key: 10},{index: 3, key: 10},{index: 4, key: 10},{index: 5, key: 10},{index: 6, key: 10},{index: 7, key: 10},{index: 8, key: 10},{index: 9, key: 10},{index: 10, key: 10},{index: 11, key: 10},{index: 12, key: 10},{index: 13, key: 10},{index: 14, key: 10},{index: 15, key: 10},{index: 16, key: 10},{index: 17, key: 10},{index: 18, key: 10},{index: 19, key: 10} ]

Cada clave tiene el mismo valor, pero cuando la función de clasificación es call: https://imgur.com/a/I7kiI

IE y Firefox funcionan bien, el problema ocurre en Chrome. Supongo que algo sale mal con el caso devuelve 0.

0
vicnoob 2 mar. 2018 a las 06:16

3 respuestas

La mejor respuesta

El problema está relacionado con la estabilidad de los algoritmos utilizados dentro de la implementación array.sort que depende del motor utilizado para ejecutar su código javascript.

Chrome utiliza el motor V8 de Google. El algoritmo de ordenación de V8 utiliza una combinación de inserción-clasificación y clasificación rápida . Compruebe la implementación real aquí.

Insertion-sort se usa cuando la matriz es pequeña (array.length <= 10), de lo contrario se usa quick-sort . El segundo algoritmo de clasificación es inestable y no ofrece ninguna garantía sobre la preservación del orden de elementos equivalentes.

Como conclusión, incluyo dos pruebas (ambas usando su función de comparación inicial). Resultados de Chrome:

  • el primer tipo se realiza en una matriz de 10 elementos (por lo tanto, se conserva el orden original)
  • el segundo tipo se realiza en su matriz original con 19 elementos (en este caso no hay certeza de mantener el orden original, y es por eso que se cambia el orden de la matriz)
const small = [
  {index: 1, key: undefined}, 
  {index: 2, key: undefined},
  {index: 3, key: undefined},
  {index: 4, key: undefined},
  {index: 5, key: undefined},
  {index: 6, key: undefined},
  {index: 7, key: undefined},
  {index: 8, key: undefined},
  {index: 9, key: undefined},
  {index: 10, key: undefined}
];

// stable sort
small.sort(function(a,b){return a.key - b.key});
console.log(small);

var arr = [
  ...small,
  {index: 11, key: undefined},
  {index: 12, key: undefined},
  {index: 13, key: undefined},
  {index: 14, key: undefined},
  {index: 15, key: undefined},
  {index: 16, key: undefined},
  {index: 17, key: undefined},
  {index: 18, key: undefined},
  {index: 19, key: undefined}
];

// unstable sort
arr.sort(function(a,b){return a.key - b.key});
console.log(arr);

Probablemente necesite implementar un algoritmo de clasificación estable para asegurarse de que su código se comportará igual a pesar del entorno en el que se ejecutará. Los algoritmos estables más comunes son bubble-sort, insertion-sort y merge-sort.

Lea más sobre estabilidad en algoritmos de clasificación

Compruebe el error de cromo: V8 no ordena de forma estable

motores Javascript. Más.

2
Carloluis 2 mar. 2018 a las 05:36

Haz lo siguiente....

arr.sort(function(a,b){return (!a || !b)? 0 : (a.key - b.key) })
0
Rohit Tirmanwar 2 mar. 2018 a las 03:41

Lo que está intentando hacer es restar undefined de undefined, y el resultado es NaN.

NaN < 0
> false

NaN > 0
> false

NaN no es -1 ni 1, y no es mayor ni menor que 0, por lo que parece tratarse como 0.

No estoy segura de si la oración anterior es cierta.

De acuerdo con MDN:

Si compareFunction (a, b) devuelve 0, deje a y b sin cambios entre sí, pero ordenados con respecto a todos los elementos diferentes. Nota: el estándar ECMAscript no garantiza este comportamiento y, por lo tanto, no todos los navegadores (por ejemplo, las versiones de Mozilla que datan de al menos 2003) lo respetan.

Así que lo probé en Firefox y el pedido no se modificó. Pero hacer lo mismo en Chrome reprodujo su problema.

1
Roomy 2 mar. 2018 a las 04:04