¿Cuál es la estabilidad del método Array.sort() en diferentes navegadores?
Sé que la especificación ECMA Script no especifica qué algoritmo usar para ordenar matrices, ni especifica si la clasificación debe ser estable.
Encontré esta información para Firefox que especifica que Firefox usa una clasificación estable.
¿Alguien sabe sobre IE 6/7/8, Chrome y Safari?
A partir de ES2019, sortse requiere que sea estable. Desde la primera edición de ECMAScript hasta ES2018, se permitía que fuera inestable.
Caso de prueba simple (ignore el encabezado, el segundo conjunto de números debe ser secuencial si el tipo del motor es estable). Nota: Este caso de prueba no funciona para algunas versiones de Chrome (técnicamente, de V8) que cambiaron los algoritmos de clasificación según el tamaño de la matriz, usando una clasificación estable para matrices pequeñas pero inestable para matrices más grandes. ( Detalles ). Consulte el final de la pregunta para ver una versión modificada que hace que la matriz sea lo suficientemente grande como para desencadenar el comportamiento.
El tipo de IE ha sido estable desde que lo he usado (es decir, IE6). Comprobando nuevamente en IE8 y parece que sigue siendo así.
Y aunque la página de Mozilla a la que enlaza dice que el tipo de Firefox es estable, definitivamente digo que este no siempre fue el caso antes de (e incluido) Firefox 2.0.
Algunos resultados superficiales:
- IE6+: estable
- Firefox < 3: inestable
- Firefox >= 3: estable
- Chrome < 70: inestable
- Cromo >= 70: estable
- Ópera < 10: inestable
- Ópera >= 10: estable
- Safari 4: estable
- Borde: inestable para matrices largas ( >512 elementos )
Todas las pruebas en Windows.
Ver también: Implementación de algoritmo de clasificación estable y rápido en javascript
Este caso de prueba (modificado desde aquí ) demostrará el problema en V8 (por ejemplo, Node v6, Chrome <v70) al garantizar que la matriz tenga suficientes entradas para elegir el método de clasificación "más eficiente"; esto está escrito teniendo en cuenta motores JavaScript muy antiguos, por lo que sin características modernas:
function Pair(_x, _y) {
this.x = _x;
this.y = _y;
}
function pairSort(a, b) {
return a.x - b.x;
}
var y = 0;
var check = [];
while (check.length < 100) {
check.push(new Pair(Math.floor(Math.random() * 3) + 1, ++y));
}
check.sort(pairSort);
var min = {};
var issues = 0;
for (var i = 0; i < check.length; ++i) {
var entry = check[i];
var found = min[entry.x];
if (found) {
if (found.y > entry.y) {
console.log("Unstable at " + found.i + ": " + found.y + " > " + entry.y);
++issues;
}
} else {
min[entry.x] = {x: entry.x, y: entry.y, i: i};
}
}
if (!issues) {
console.log("Sort appears to be stable");
}
Me gustaría compartir un truco que uso habitualmente en C/C++ para qsort().
sort() de JS permite especificar una función de comparación. Cree una segunda matriz de la misma longitud y rellénela con números crecientes desde 0.
function stableSorted(array, compareFunction) {
compareFunction = compareFunction || defaultCompare;
var indicies = new Array(array.length);
for (var i = 0; i < indicies.length; i++)
indicies[i] = i;
Estos son índices de la matriz original. Vamos a ordenar la segunda matriz. Cree una función de comparación personalizada.
indicies.sort(function(a, b)) {
Obtendrá los dos elementos de la segunda matriz: utilícelos como índices en las matrices originales y compare los elementos.
var aValue = array[a], bValue = array[b];
var order = compareFunction(a, b);
if (order != 0)
return order;
Si los elementos son iguales, compare sus índices para estabilizar el orden.
if (a < b)
return -1;
else
return 1;
});
Después de sort(), la segunda matriz contendría índices que puede usar para acceder a los elementos de la matriz original en un orden estable.
var sorted = new Array(array.length);
for (var i = 0; i < sorted.length; i++)
sorted[i] = array[indicies[i]];
return sorted;
}
// The default comparison logic used by Array.sort(), if compareFunction is not provided:
function defaultCompare(a, b) {
a = String(a);
b = String(b);
if (a < b) return -1;
else if (a > b) return 1;
else return 0;
}
En general, los algoritmos de clasificación estable apenas están madurando y todavía requieren más memoria adicional en comparación con el viejo qsort. Supongo que es por eso que muy pocas especificaciones exigen una clasificación estable.
A partir de V8 v7.0 y Chrome 70, nuestra Array.prototype.sortimplementación ahora es estable. 🎉
Anteriormente, V8 usaba un QuickSort inestable para matrices con más de 10 elementos . Ahora, V8 utiliza el algoritmo estable TimSort.
El único motor JavaScript importante que todavía tiene una Array#sortimplementación inestable es Chakra, como se usa en Microsoft Edge. Chakra utiliza QuickSort para matrices con más de 512 elementos . Para matrices más pequeñas, utiliza una implementación de ordenación por inserción estable.
Demostración: https://mathiasbynens.be/demo/sort-stability
