J'aimerais partager une astuce que j'utilise régulièrement en C/C++ pour qsort()
.
La fonction sort() de JS permet de spécifier une fonction de comparaison. Créez un deuxième tableau de la même longueur et remplissez-le de nombres croissants à partir de 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;
Ce sont des index dans le tableau original. Nous allons trier le second tableau. Créez une fonction de comparaison personnalisée.
indicies.sort(function(a, b)) {
Elle récupère les deux éléments du second tableau : elle les utilise comme index dans les tableaux d'origine et compare les éléments.
var aValue = array[a], bValue = array[b];
var order = compareFunction(a, b);
if (order != 0)
return order;
Si des éléments se trouvent être égaux, il faut alors comparer leurs indices pour rendre l'ordre stable.
if (a < b)
return -1;
else
return 1;
});
Après le sort(), le deuxième tableau contiendra des index que vous pourrez utiliser pour accéder aux éléments du tableau original dans un ordre trié stable.
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 général, les algorithmes de tri stables ne font que mûrir et nécessitent toujours plus de mémoire supplémentaire par rapport au bon vieux qsort. Je suppose que c'est la raison pour laquelle très peu de spécifications imposent le tri stable.