Trier et dédupliquer une liste sans surprises

Trier et dédupliquer ressemblent aux deux opérations les plus simples que l'on puisse appliquer à une liste, et c'est bien pourquoi les résultats sont si souvent discrètement faux. Les deux reposent sur une comparaison, et il n'existe pas de réponse unique à la question de savoir ce qui rend deux lignes égales ou ce qui place une ligne en premier.

L'ordre lexicographique n'est pas l'ordre numérique

La comparaison par défaut pour du texte parcourt deux chaînes caractère par caractère, compare les points de code et s'arrête à la première différence. Rien là-dedans ne sait ce qu'est un nombre.

input:   img1.png, img2.png, img10.png
sorted:  img1.png, img10.png, img2.png

img10.png arrive en deuxième position parce qu'au quatrième caractère, 1 (U+0031) est inférieur à 2 (U+0032), et la comparaison s'arrête là. La même règle place la version 1.10 avant 1.9, et liste un dossier de captures d'écran dans un autre ordre que celui de leur prise.

La comparaison numérique corrige aussi les nombres négatifs : lexicographiquement, -10 tombe entre -1 et -2, parce qu'un signe moins n'est qu'un caractère de plus doté d'un point de code.

Majuscules avant minuscules, et autres surprises de points de code

En ASCII, les capitales occupent les positions 65 à 90 et les minuscules 97 à 122 : chaque capitale se trie donc avant chaque minuscule.

Les chiffres se placent sous toutes les lettres, l'espace (32) sous tout caractère imprimable, et une ligne vide encore en dessous : un tri croissant rassemble donc les lignes vides et celles qui commencent par une espace tout en haut, et un tri décroissant les rassemble tout en bas.

Les blancs en fin de ligne sont la version invisible du même problème : apple et apple se trient l'un à côté de l'autre et ressemblent à un doublon qui refuse d'être supprimé. L'espace insécable (U+00A0) est pire, dessinée exactement comme une espace normale mais triée au-dessus de toutes les lettres, tout comme le retour chariot laissé derrière lui quand un fichier Windows est découpé sur les seuls sauts de ligne. Si deux lignes semblent identiques et refusent encore de fusionner, cherchez des caractères cachés.

La même liste se trie différemment dans deux pays

L'ordre des points de code place aussi tout caractère accentué après tout caractère non accentué. Zürich se trie après Zzz, et Ärger après zebra. Aucune langue n'ordonne son propre alphabet ainsi. La collation adaptée à la locale compare selon les règles d'une langue, et ces règles se contredisent entre elles.

En JavaScript, cela vit dans Intl.Collator :

const words = ["Zebra", "Ärger", "Apfel"];

words.sort(new Intl.Collator("de").compare);
// Apfel, Ärger, Zebra

words.sort(new Intl.Collator("sv").compare);
// Apfel, Zebra, Ärger

Le même objet couvre les problèmes précédents. { numeric: true } compare les suites de chiffres comme des nombres, ce qui donne l'ordre naturel, et sensitivity fixe ce qui compte comme une différence : "base" ignore la casse et les accents, "accent" ignore la casse seule, "case" ignore les accents seuls. Omettre la locale revient à prendre celle de la machine, et c'est ainsi que le même code renvoie deux ordres différents sur deux portables. Nommez la locale quand la sortie doit être identique partout.

Quels doublons comptent comme des doublons

La déduplication n'est bien définie que dans la mesure où le test d'égalité qui la sous-tend l'est. Prenez cinq lignes qui s'affichent toutes comme le mot cafe avec un accent aigu :

Quatre règles raisonnables donnent quatre réponses différentes :

Aucune n'est fausse ; elles répondent à des questions différentes. La normalisation compte davantage qu'il n'y paraît, car un texte issu de noms de fichiers macOS tend à arriver décomposé (NFD) et un texte issu de Windows et de formulaires web composé (NFC), si bien qu'une liste collée depuis deux sources ramasse des jumeaux invisibles. NFKC va plus loin, en rabattant des caractères de compatibilité comme la ligature fi sur leurs équivalents simples.

La première occurrence l'emporte par convention : si la copie mal soignée a été collée en premier, c'est elle qui survit. Et supprimer les doublons est une demande différente de trouver les éléments uniques : Supprimer les lignes en double laisse un exemplaire de chacun, tandis que l'ensemble unique de Fréquence des éléments est le groupe plus restreint de ceux qui n'apparaissent qu'une seule fois.

La stabilité, et le tri sur deux clés

Un tri stable garantit que les entrées jugées égales par le comparateur conservent l'ordre qu'elles avaient en entrée. C'est ce qui fait fonctionner le tri multiclé par passes successives : triez d'abord sur la clé la moins importante, puis sur la plus importante. Trier par nom puis par service donne des services dans l'ordre, avec des noms ordonnés à l'intérieur de chacun. Un tri instable défait la première passe en effectuant la seconde, et le résultat a l'air presque juste, ce qui est pire que d'avoir l'air faux.

L'inversion comporte le même piège, car retourner une liste triée retourne aussi chaque groupe d'ex aequo. Employez Inverser la liste quand c'est bien tout l'ordre que vous voulez retourner, et non comme raccourci vers un tri décroissant.

Les implémentations diffèrent. Le Array.prototype.sort de JavaScript n'est tenu d'être stable que depuis ES2019 ; auparavant, V8 utilisait un tri rapide instable au-delà d'une petite taille de tableau, si bien que le même code se comportait différemment sur dix éléments et sur dix mille. Le sorted de Python est stable, et le sort de GNU ne l'est pas, sauf si on lui donne -s.

Mélanger n'est pas une forme de tri

Le mélange en une ligne, list.sort(() => Math.random() - 0.5), est biaisé. Un tri suppose que son comparateur décrit un ordre cohérent, et il n'interroge que le sous-ensemble de paires dont son algorithme a besoin. Un comparateur qui tire un nouveau nombre à chaque appel brise cette hypothèse : le résultat dépend donc de l'algorithme et de la longueur du tableau, les éléments ont tendance à rester près de leur position de départ, et certaines permutations reviennent bien plus souvent que d'autres.

Un mélange correct emploie Fisher-Yates, en parcourant depuis la fin et en échangeant chaque élément avec un élément choisi uniformément à sa position ou avant :

for (let i = list.length - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));
  [list[i], list[j]] = [list[j], list[i]];
}

La variante cassée la plus répandue utilise Math.random() * list.length à l'intérieur de la boucle, en puisant dans tout le tableau à chaque fois. Cela donne n puissance n suites de tirages également probables, ce qui ne se divise pas de façon égale par les n factorielle ordonnancements : certains ordres reviennent donc plus souvent.

L'aléa et le tri peuvent se combiner correctement en attribuant d'emblée une clé aléatoire à chaque élément et en triant sur cette clé, car le comparateur reste alors cohérent. L'erreur consiste à lancer le dé à l'intérieur de la comparaison.

L'ordre dans lequel enchaîner les étapes

La plupart des problèmes de listes viennent de bonnes opérations effectuées dans le mauvais ordre.

1. Déballez d'abord. Une liste copiée depuis du code arrive sous la forme "apple", ; les guillemets et la virgule font partie de la chaîne, qui ne correspond donc jamais à apple. Déballer les éléments les retire.
2. Rognez et normalisez, pour que l'égalité veuille dire ce que vous croyez qu'elle veut dire.
3. Dédupliquez, avec une règle de correspondance choisie délibérément plutôt que prise par défaut.
4. Triez. Trier les lignes couvre l'ordre textuel, numérique, par longueur et aléatoire ; ajoutez une locale pour des données accentuées.
5. Remodelez en dernier. Grouper les éléments découpe le résultat en lots de taille fixe pour une limite par requête, et Faire tourner la liste décale l'ensemble sans changer l'ordre interne.

Dédupliquer avant de rogner laisse derrière soi des quasi-doublons, et trier avant de dédupliquer ne fait que trier des lignes sur le point d'être jetées.