Comment bien trier un tableau en Javascript
La documentation sur internet concernant le sort est assez complète (ici par exemple), mais commençons malgré tout par un petit rappel.
Tri simple
Pour trier un tableau en JS, il suffit d'utiliser la méthode sort définie dans le prototype de Array.
Le fonctionnement par défaut de cette méthode est de faire un tri alphanumérique. Donc, si vous avez un tableau de chaines de caractères, un simple myArray.sort() devrait faire le job...
Vraiment ? Enfin, seulement si la casse est identique pour toutes vos chaines. Sinon, le résultat risque de ne pas vous plaire.
Que faire alors ?
Que vous ayez autre chose qu'un tableau de string, ou bien que vous souhaitiez que votre tri soit insensible à la casse, vous devrez alors passer à la méthode sort une fonction de tri.
Et la magie opère
const mySortFunction = (prev, next) => {
if (prev > next) return 1; // Or any positive number
if (prev < next) return -1; // Or any negative number
return 0;
};
myArray.sort( mySortFunction );
Voici l'exemple type pour définir une fonction de tri croissant. Pour un tri décroissant, il suffit de retourner -1 au lieu de 1 et 1 au lieu de -1.
C'est simple et cette syntaxe peut vous permettre de gérer tout type de contenu dans votre array (objets par exemple).
Et pour les string ?
Pour trier des chaines en ignorant la casse, vous pouvez vous en sortir seul avec la fonction de tri, en appliquant un .toLowerCase() sur prev et next par exemple. Ce n'est pas très élégant, ni très performant, mais ca fait le job.
Alors on s'arrête là ?
Ce serait dommage, vu qu'il existe une méthode dédiée à la comparaison de chaines de caractères dans le prototype de String : localeCompare !
const mySortFunction = (prev, next) => prev.localeCompare(next); myArray.sort( mySortFunction );
A propos du tri stable
On dit qu'un algorithme de tri est stable s'il ne modifie pas l'ordre initial des clés identiques (si vous n'êtes pas à l'aise avec cette notion, je vous encourage à aller lire ce très bon article sur le sujet).
Les premières versions de JS n'indiquaient pas clairement que la méthode sort devait retourner un tri stable, et donc, c'était un peu la foire, certains navigateurs l'ayant fait, d'autres non. Heureusement ES2019 a enfin levé le doute et imposé le tri stable.
Petit état des lieux :
- IE6+: stable
- Firefox 3+: stable
- Chrome 70+: stable
- Opera 10+: stable
- Safari 4+: stable
- Node 12+ : stable
En 2021, Node et tous les navigateurs à jour utilisent donc bien un algorithme de tri stable. Pour l'utiliser, il suffit de bien retourner 1, -1 ou 0 dans votre fonction de tri, comme spécifié dans la documentation.
Et avec le temps...
Je fais passer des tests techniques de recrutement dans ma nouvelle boite, et je vois très régulièrement des candidats qui utilisent ce genre de fonction de tri :
array.sort( (a, b) => a > b ? 1 : -1 );
Ou est passé le return 0 ? Pourquoi se contenter de retourner 1 ou -1 ? a ne peut-il donc jamais être égal à b ?
La plupart des devs me répondent qu'ils font toujours comme ca (mode copier/coller) et que "ca marche".
Les plus filous iront même jusqu'à prétendre que leur tri est "optimisé" puisqu'il fait 1 comparaison de moins, alors qu'en fait ils avaient juste la flemme d'écrire quelques caractères de plus.
Alors oui, ca marche. Mais le tri ne sera pas stable !
En effet, seul le fait de préciser un return 0 permet à l'algorithme de tri de savoir que vos 2 éléments sont identiques sur les critères de tri considérés.
Mais non ce n'est pas plus performant, c'est même généralement l'inverse, et pas qu'un peu !
La plupart des algorithmes de tri utilisent l'information d'égalité (le fameux return 0) pour optimiser leur traitement et ainsi réduire le nombre d'itérations nécessaire pour arriver à trier l'ensemble du tableau.
Lecture de notes
Combattez les piranhas !