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.
Sería útil mantener esto actualizado. – ColBeseder
Parece que Chrome (V8) seguirá siendo así: http://code.google.com/p/v8/issues/detail?id=90 –
http://ofb.net/~sethml/is-sort-stable .html? (Lo guardé en el archivo web por si acaso) – Pierre