Trier du texte n'est pas une seule opération : quatre ordres qui se disent tous alphabétiques

Quatre choses appelées alphabétique

Un bouton de tri propose une option et sous-entend qu'il existe une réponse. Il en existe au moins quatre, et ce ne sont pas des raffinements les unes des autres : ce sont des ordres différents qui rendent des listes différentes à partir de la même entrée. L'ordre des unités de code compare les valeurs numériques des unités UTF-16 qui composent la chaîne. L'ordre naturel lit les suites de chiffres comme des nombres. La collation par locale applique les règles propres à une langue sur les lettres qui comptent comme une même lettre. Les variantes de collation découpent ensuite une même langue en plusieurs ordres défendables, parce que les dictionnaires allemands et les annuaires allemands n'ont jamais été d'accord.

Tout ce qui suit a été exécuté, pas mémorisé. Chaque liste est imprimée exactement telle que Node 26.3 l'a rendue, et les scripts sont assez courts pour être retapés : un tableau, un tri, un console.log.

L'ordre des unités de code : ce que fait vraiment .sort()

Appelée sans comparateur, Array.prototype.sort convertit chaque élément en chaîne et compare ces chaînes par unité de code UTF-16. C'est une règle documentée, pas un accident, et elle produit deux symptômes visibles. Les majuscules occupent la plage 0x41–0x5A et les minuscules 0x61–0x7A : toute majuscule passe donc avant toute minuscule. Et les chiffres sont comparés comme des caractères : ["chapitre10","chapitre9","chapitre2"] rend chapitre10, chapitre2, chapitre9, car « 1 » vaut 0x31 et « 9 » vaut 0x39, et la comparaison s'arrête à la première différence.

Le troisième symptôme est celui qui atteint les lecteurs. Toute lettre portant un signe diacritique vit au-dessus de 0x7A : l'ordre des unités de code rejette donc tout l'alphabet accentué derrière le z. ["étage","effet","zèbre","Île"] rend effet, zèbre, Île, étage. ["Öl","Ohr","Zebra","Ähre"] rend Ohr, Zebra, Ähre, Öl. ["ñu","nube","niño","zorro"] rend niño, nube, zorro, ñu. ["ação","acordo","água","avô"] rend acordo, avô, ação, água. Quatre langues, quatre réponses fausses, une ligne de code.

L'ordre des unités de code n'est pas inutile. Il est total, transparent, rapide — 20 000 mots triés en 6 ms dans le banc d'essai ci-dessous — et identique dans tous les moteurs et toutes les locales, ce qui en fait le bon choix pour tout ce que lit une machine : clés d'index, seaux de déduplication, identifiants de cache, sérialisations canoniques. Il n'est faux que lorsque la sortie s'adresse à une personne.

L'ordre naturel : lire les chiffres comme des nombres

L'ordre naturel — celui d'un gestionnaire de fichiers — traite une suite de chiffres à l'intérieur d'une chaîne comme un seul nombre plutôt que comme une suite de caractères. En JavaScript, c'est une option : new Intl.Collator("fr", { numeric: true }). Sur ["chapitre10","chapitre9","chapitre2"], elle rend chapitre2, chapitre9, chapitre10, et sur une liste plus longue ["item2","item9","item10","item100","item20"] elle rend item2, item9, item10, item20, item100, là où le .sort() par défaut rend item10, item100, item2, item20, item9.

Deux limites méritent d'être connues avant de l'activer partout. La collation numérique est un confort d'affichage, pas de l'arithmétique : elle compare des suites de chiffres, elle a donc un avis sur « v1.10 » face à « v1.9 » qu'un analyseur de versions sémantiques ne partagerait pas, et elle ne dit rien d'utile sur les signes, les séparateurs décimaux ou les séparateurs de milliers. Et elle change la réponse pour des clés qui contiennent des chiffres par hasard, comme des codes produits où 0090 et 90 sont deux articles distincts. Active-la pour les listes qu'une personne parcourt, laisse-la éteinte pour les identifiants.

La collation par locale : l'allemand contre le suédois

La collation par locale est le cas classique, et l'allemand contre le suédois en est la paire classique. Prends ["Öl","Ohr","Zebra","Ähre"]. Sous new Intl.Collator("de"), le tri donne Ähre, Ohr, Öl, Zebra : ä est une variante de a, ö une variante de o, et le signe diacritique ne départage qu'en cas d'égalité. Sous new Intl.Collator("sv"), les mêmes quatre chaînes donnent Ohr, Zebra, Ähre, Öl : en suédois, å, ä et ö sont les trois dernières lettres de l'alphabet, après le z. Aucun des deux n'est un bug. Ce sont deux langues avec deux alphabets, et la liste doit en choisir un.

Vient ensuite la partie gênante : sur cette liste, le .sort() par défaut rend Ohr, Zebra, Ähre, Öl — caractère pour caractère la réponse suédoise. Un programme qui a sauté la locale n'a pas produit « aucun ordre en particulier ». Il a produit un ordre étranger précis, en silence, et il continuera à le produire pour chaque liste allemande, espagnole, portugaise ou française qu'il touchera.

Les autres locales de cet article se comportent de la même façon. L'espagnol fait de ñ une lettre à part entière après n : ["ñu","nube","niño","zorro"] donne niño, nube, ñu, zorro sous es, alors que l'ordre des unités de code exile ñu derrière zorro. Le portugais traite les accents comme des départages : ["ação","acordo","água","avô"] ressort dans l'ordre du dictionnaire sous pt et en désordre sous .sort(). L'italien donne ancora, Àncora, elite, zucchero sous it, où l'accent est une différence secondaire et la majuscule une différence tertiaire. Et le français possède un ordre réellement régional : sur ["cote","coté","côte","côté"], fr rend cote, coté, côte, côté, tandis que fr-CA rend cote, côte, coté, côté, parce que le français canadien compare les accents depuis la fin du mot.

Une langue, plusieurs ordres : les variantes de collation

Même à l'intérieur d'une langue il y a plus d'une réponse correcte, et le CLDR d'Unicode les livre comme variantes nommées, choisies via la chaîne de locale. L'allemand en a deux d'usage courant. La collation de dictionnaire, de, trie ["Göbel","Goethe","Godel","Gözde","Gott"] en Göbel, Godel, Goethe, Gott, Gözde : ö est une variante de o. La collation d'annuaire, de-u-co-phonebk, trie les mêmes cinq en Godel, Göbel, Goethe, Gözde, Gott, parce que ö est développé en oe — ce qui place Göbel entre Godel et Goethe, exactement là où quelqu'un qui cherche « Goebel » regarderait.

Deux réglages accompagnent la variante et changent la réponse autant qu'elle. sensitivity décide quelles différences comptent : sur « cote » face à « côte » et « cote » face à « Cote », la sensibilité « base » déclare les deux paires égales, « accent » sépare l'accent mais pas la casse, « case » sépare la casse mais pas l'accent, et « variant » — la valeur par défaut — sépare les deux. caseFirst décide qui gagne en cas d'égalité : sur ["apple","Apple","APPLE"], le défaut rend apple, Apple, APPLE, et caseFirst: "upper" rend APPLE, Apple, apple. Aucun des deux réglages n'est cosmétique. sensitivity est aussi ce qui fait d'un collateur un outil de recherche : avec « base », compare rend 0 pour des chaînes qu'un lecteur appellerait le même mot.

La stabilité : ce qu'il advient des ex aequo

Un tri est stable quand les éléments jugés égaux conservent l'ordre relatif qu'ils avaient en entrée. Cela compte dès que l'on trie sur une clé partielle — une initiale, une catégorie, une date sans heure — car les ex aequo ne sont pas de rares cas limites : ils sont la majeure partie de la liste. En triant dix prénoms sur leur seule initiale, les éléments d'initiale a sont ressortis dans les positions d'entrée 1, 2, 4, 6, 8 et ceux d'initiale b dans les positions 0, 3, 5, 7, 9 : chaque groupe conservé, dans l'ordre.

Array.prototype.sort est tenu par la spécification d'être stable depuis ES2019. Auparavant, les moteurs pouvaient employer un algorithme instable au-delà d'une certaine taille de tableau, et plusieurs le faisaient : c'est pourquoi les vieux conseils recommandent un comparateur composite ou de transporter l'index. L'exigence vaut quelle que soit la taille : un tableau de mille éléments trié sur une clé à trois valeurs distinctes est revenu avec chaque groupe dans l'ordre d'entrée. Tu peux donc construire un tri multi-clés en triant plusieurs fois, de la clé la moins significative à la plus significative — d'abord le prénom, puis le nom — et compter sur la survie des passes précédentes.

Ce que cela coûte, et la règle qui en découle

Le tri sensible à la locale coûte plus cher que le tri par unités de code, mais pas autant qu'on le craint, et l'erreur coûteuse est ailleurs. Tri de 20 000 mots dans Node 26.3 : le .sort() par défaut a pris 6 ms, a.localeCompare(b, "de") 12 ms, un collateur construit une fois et réutilisé 28 ms — et construire un new Intl.Collator à l'intérieur du comparateur a pris 1 771 ms, soixante fois plus lent que la réutilisation. Le coût n'est pas la collation. Le coût, c'est de construire le collateur des centaines de milliers de fois.

Il reste une règle assez courte pour être appliquée. Si une machine lit la sortie, trie par unité de code et écris-le noir sur blanc. Si une personne la lit, nomme une locale — la langue dans laquelle le document est écrit, pas celle du navigateur qui l'affiche — construis un seul Intl.Collator, décide sciemment de numeric et de sensitivity, et réutilise-le. La seule chose jamais défendable est d'appeler .sort() sur du texte destiné à des lecteurs et de qualifier le résultat d'alphabétique.

Questions fréquentes

Pourquoi « Zebra » se trie-t-il avant « apple » ?

Parce que .sort() sans comparateur compare des unités de code UTF-16, et que toute majuscule ASCII (0x41–0x5A) a une valeur plus petite que toute minuscule ASCII (0x61–0x7A). Il ne trie pas des lettres, il trie des nombres qui représentent des lettres. N'importe quel collateur de locale corrige cela : new Intl.Collator("en").compare rend apple, Banana, zebra, Zebra dans cet ordre, la casse servant de dernier départage et non de premier critère.

Le tri de JavaScript est-il stable ?

Oui, et c'est une obligation. ES2019 a fait de la stabilité une exigence de la spécification pour Array.prototype.sort, et Array.prototype.toSorted suit la même règle. Vérifié ici sur un tableau de mille éléments trié par une clé à trois valeurs distinctes : chaque groupe est revenu dans l'ordre d'entrée. C'est cette garantie qui permet d'implémenter un tri multi-colonnes comme une suite de tris mono-colonne, en commençant par la colonne la moins significative.

Quelle locale utiliser si j'ignore celle du lecteur ?

Utilise la langue du contenu, pas celle de l'appareil du lecteur. Une liste de noms de produits allemands relève de la collation allemande quel que soit celui qui la regarde, exactement comme un catalogue allemand imprimé. Se rabattre sur le défaut du moteur est la pire option, parce qu'il est invisible : new Intl.Collator() sans argument s'est résolu en en-US sur la machine où cet article a été écrit, et se résoudrait autrement sur la suivante, si bien que la même liste s'ordonnerait différemment sur deux serveurs sans changer une ligne de code.

Pourquoi mon gestionnaire de fichiers classe-t-il item2 avant item10 alors que mon code non ?

Le gestionnaire de fichiers utilise l'ordre naturel : il reconnaît la suite de chiffres comme un nombre. Ton code compare des caractères, s'arrête donc sur « 1 » face à « 9 » et ne lit jamais la suite. Ajoute { numeric: true } à un Intl.Collator, ou passe la même option à localeCompare, et les deux s'accordent. N'essaie pas d'imiter cela en complétant les chaînes affichées par des zéros : cela répare le tri et casse les libellés.

localeCompare est-il trop lent pour une longue liste ?

Pas en soi. Sur 20 000 mots dans Node 26.3, a.localeCompare(b, "de") a pris 12 ms et un Intl.Collator réutilisé 28 ms, contre 6 ms pour le .sort() par défaut — un écart que personne ne remarquera. Ce qui est réellement lent, c'est de construire un collateur à l'intérieur du comparateur : le même tri a alors pris 1 771 ms, parce qu'un collateur neuf est fabriqué pour chacune des centaines de milliers de comparaisons. Construis-le une fois, hors du tri, et passe son .compare.

Comment trier des noms allemands comme le fait un annuaire ?

Demande la variante de collation par son nom : new Intl.Collator("de-u-co-phonebk"). La partie -u-co- d'un identifiant de locale sélectionne une collation, et phonebk est l'adaptation « annuaire allemand », dans laquelle ö se comporte comme oe, ä comme ae et ü comme ue. Sur ["Göbel","Goethe","Godel","Gözde","Gott"], de simple donne Göbel, Godel, Goethe, Gott, Gözde et de-u-co-phonebk donne Godel, Göbel, Goethe, Gözde, Gott. D'autres langues ont leurs variantes : une liste chinoise peut être ordonnée par pinyin ou par nombre de traits de la même manière.