Array.sort Clasificación de la estabilidad en diferentes navegadores

Question

¿Cuál es la estabilidad de Array.sort en diferentes navegadores? Sé que la especificación de ECMA Script no especifica qué algoritmo usar, ni especifica si el género debe ser estable.

He encontrado esta información para Firefox en https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array/sort que especifica que firefox usa un tipo estable.

¿Alguien sabe acerca de IE 6/7/8, Chrome, Safari?

Answer 1

Simple test case (ignore el encabezado, el segundo conjunto de números debe ser secuencial si la clasificación del motor es estable).

El tipo de IE ha sido estable mientras lo haya usado (así que IE6). Comprobando nuevamente en IE8 y parece ser el caso.

Y aunque esa página de Mozilla con la que enlazas dice que el género de Firefox es estable, definitivamente digo que esto no fue siempre el caso antes (e incluido) de Firefox 2.0.

Algunos resultados superficiales:

• IE6 +: estable
• Firefox < 3: inestable
• Firefox> = 3: estables
• Chrome < = 5 (es decir, todas las versiones hasta la fecha): inestable
• Opera < 10: inestable
• Opera> = 10: estable
• Safari 4: estable

Todas las pruebas en Windows.

Consulte también:

• Fast stable sorting algorithm implementation in javascript

Answer 2

Si está buscando una lista de navegadores donde debe utilizar un algoritmo de clasificación no nativo, mi sugerencia es no.

En su lugar haga una especie de comprobación de cordura cuando se carga el script y tome una decisión al respecto.

Como la especificación no requiere un comportamiento particular en ese sentido, no es inmune a cambios posteriores, incluso dentro de la misma línea de navegador.

Puede enviar un parche a http://www.browserscope.org/ para incluir dichas pruebas en su suite. Pero, una vez más, la detección de funciones es superior a la detección del navegador.

Answer 3

Me gustaría compartir un truco que utilizo rutinariamente en C/C++ para qsort().

JS 'sort() permite especificar una función de comparación. Cree una segunda matriz de la misma longitud y llé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 en la matriz original. Vamos a ordenar el segundo conjunto. Haga una función de comparación personalizada.

indicies.sort(function(a, b)) { 

Se obtendrá los dos elementos de la segunda matriz: usarlos como índices de las matrices originales y comparar 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 hacer que la orden sea estable.

if (a < b) 
    return -1; 
    else 
    return 1; 
    }); 

Después de la especie(), la segunda matriz contendría índices que se pueden utilizar para acceder a los elementos de la matriz original en el establo de manera ordenada.

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 ordenación estable sólo están madurando y todavía requieren más memoria adicional en comparación con el bien qsort ol'. Supongo que es por eso que muy pocas especificaciones ordenan un orden estable.