Je vois parfois des trucs un peu bizarre pour faire des tris de liste, en particulier en JavaScript / TypeScript. En particulier quand il s'agit de trier sur plusieurs critères... C'est assez dommage vu qu'au final ce n'est vraiment pas compliqué...

Note : pour faire mes tests, je vais utiliser le REPL de Deno pour cet article. Pourquoi ? C'est simple : je peux faire du TypeScript en first-class citizen, sans compilation, au besoin et je préfère ce moteur JavaScript ! À priori ça ne changera rien pour vous, mais je vous encourage à tester !

Le basic .sort()

Je pense que tout le monde a déjà fait ça :

const list = ['a', 'c', 'b'];
list.sort();
// list = ['a', 'b', 'c']

C'est simple, ça fonctionne mais il se passe déjà plein de choses ! Déjà .sort() a muté notre liste, et ce n'est pas forcément toujours souhaitable (j'y reviendrais plus tard) ! Ensuite alors qu'on ne lui a pas dit dans quel ordre on voulait trier, il nous a trié la liste par ordre alphabétique... ou presque. En fait si on suit la spécification, le tri a été fait par "la valeur du point de code Unicode de chaque caractère d'après la conversion en chaîne de caractère".

Donc en gros : chaque élément qui n'est pas une chaîne de caractère est converti en chaîne de caractère avant d'être comparé : ici c'est pas grave, on a déjà des chaîne de caractère mais ça peut devenir une opération lourde et hasardeuse !

const list = ['a', 'c', 'A', '2', { 'b': 1 }, { 'a': 2 },',','Z', 1, 'b'];
list.sort();
// list = [ ",", 1, "2", "A", "Z", { b: 1 }, { a: 2 }, "a", "b", "c" ]

Est-ce que c'est ce à quoi vous attendiez ? Pas sûr. En tout cas moi pas pour certains éléments... Et surtout rarement l'ordre que je veux !

En résumé : .sort() sans argument c'est pas ouf...

Un jeu de données

Avant d'aller plus loin et pour limiter les répétions, posons directement un jeu de donnée et son format. Donc je vais partir sur une collection de livre, certains faisant partie d'une série, d'autres non.

type Book = {
    id: string;
    title: string;
    editor: string;
    author: string;    
} & ({} | { series: string; volume: number; });

const books: Book[] = [
    {
        "id": "f47ac10b-58cc-4372-a567-0e02b2c3d479",
        "title": "Jeux de vilains",
        "series": "Kid Paddle",
        "editor": "Dupuis",
        "volume": 1,
        "author": "Midam"
    },
    {
        "id": "f47ac10b-58cc-4372-a567-0e02b2c3d480",
        "title": "Carnage total",
        "series": "Kid Paddle",
        "editor": "Dupuis",
        "volume": 2,
        "author": "Midam"
    },
    {
        "id": "f47ac10b-58cc-4372-a567-0e02b2c3d481",
        "title": "Blork Raider",
        "series": "Game Over",
        "editor": "Dupuis",
        "volume": 1,
        "author": "Midam"
    },
    {
        "id": "f47ac10b-58cc-4372-a567-0e02b2c3d482",
        "title": "No problemo",
        "series": "Game Over",
        "editor": "Dupuis",
        "volume": 2,
        "author": "Midam"
    },
    {
        "id": "f47ac10b-58cc-4372-a567-0e02b2c3d483",
        "title": "La Quête d'Ewilan",
        "series": "La Quête d'Ewilan",
        "editor": "Rageot",
        "volume": 1,
        "author": "Bottero, Pierre"
    },
    {
        "id": "f47ac10b-58cc-4372-a567-0e02b2c3d484",
        "title": "Les Frontières de glace",
        "series": "La Quête d'Ewilan",
        "editor": "Rageot",
        "volume": 2,
        "author": "Bottero, Pierre"
    },
    {
        "id": "f47ac10b-58cc-4372-a567-0e02b2c3d485",
        "title": "L'Appel de Cthulhu",
        "editor": "Folio",
        "author": "Lovecraft, Howard Phillips"
    },
    {
        "id": "f47ac10b-58cc-4372-a567-0e02b2c3d486",
        "title": "Dans l'abîme du temps",
        "editor": "Folio",
        "author": "Lovecraft, Howard Phillips"
    }
];

Maintenant qu'on sait ce qu'on va manipuler comme données, passons aux choses sérieuses !

Avec un comparateur !

Comme je disais un peu plus tôt, utiliser .sort() sans paramètre c'est pas terrible, ça donne rarement ce qu'on veut donc autant lui passer des paramètres ! Cette fonction prend un seul et unique paramètre : un comparateur.

Mais c'est quoi un comparateur ?

C'es tout simple : c'est une fonction qui sert à comparer ! Ba dum tss 🧌

Bon sérieusement, c'est une fonction qui permet de dire si un élément a est à placer avant ou après un élément b.

Imaginons un comparateur très simple qui trie par numéro de volume (en prenant en compte que certains n'en n'ont pas) :

function sortByVolume() {
    return (a: Book, b: Book) => {
        const aVolume = a.volume ?? -1;
        const bVolume = b.volume ?? -1;
        return aVolume - bVolume;
    }
}

books.sort(sortByVolume());

Note : je préfère avoir un comparateur que je pose à part et nomme explicitement (car c'est je pense plus clair pour tout le monde), et je préfère l'écrire sous la forme d'une fonction qui renvoie une fonction de comparaison qu'une fonction qui prend directement les éléments de comparaison par habitude d'avoir besoin de passer des paramètres de temps en temps.

Donc ici on trie par ordre croissant de volume tous les livres en comparant la valeur de volume. Comment le moteur JavaScript sait quoi faire ensuite ? Il va comparer par paire les éléments : si le résultat est négatif, a est avant b ; si le résultat est 0, ils sont équivalent donc pas d'ordre particulier ; si le résultat est positif, a est après b.

Si vous voulez les trier par ordre décroissant, il suffit d'inverser la soustraction de a.volume et b.volume :

function sortByVolumeDesc() {
    return (a: Book, b: Book) => {
        const aVolume = a.volume ?? -1;
        const bVolume = b.volume ?? -1;
        return bVolume - aVolume;
    }
}

books.sort(sortByVolumeDesc());

Simple ? Sauf que si on a besoin de beaucoup de comparateurs, et de trier parfois par ordre croissant, parfois décroissant (au hasard : un tableau de donnée avec des titres de colonne qui permettent un tris croissant/décroissant au clic), c'est un peu embêtant de devoir créer tous les comparateurs en double. Donc je vous propose une fonction utilitaire desc (comme on ferait un ORDER BY ? DESC en SQL) :

function desc<T>(comparator: (a: T, b: T) => number) {
    return (a: T, b: T) => {
        return -comparator(a, b);
    }
}

books.sort(desc(sortByVolume()));

Comme ça vous n'êtes pas obligé de créer tout en double !

Là je vous ai montré pour des nombres, c'est plutôt facile. Pour des chaînes de caractères (par exemple le titre) on fait quoi ?

function sortByTitle() {
    return (a: Book, b: Book) => {
        return a.title.localeCompare(b.title);
    }
}

books.sort(sortByTitle());

La fonction .localeCompare() va faire la comparaison caractère à caractère pour renvoyer un nombre indiquant quelle est la chaîne qui est la première dans l'ordre comme pour des nombres.

Je ne vais pas vous montrer des centaines d'exemples, mais on peut toujours ramener une comparaison qui renvoie un nombre.

Au passage, on peut faire des comparateurs un peu plus sympa :

function sortByString<T>(project: (x: T) => string) {
    return () => (a: T, b: T) => {
        return project(a).localeCompare(project(b));
    }
}
function sortByNumber<T>(project: (x: T) => number) {
    return () => (a: T, b: T) => {
        return project(a) - project(b);
    }
}

const sortByTitle = sortByString((book: Book) => book.title);
const sortByEditor = sortByString((book: Book) => book.editor);
const sortByAuthor = sortByString((book: Book) => book.author);
const sortBySeries = sortByString((book: Book) => "series" in book ? book.series : "");
const sortByVolume = sortByNumber((book: Book) => "volume" in book ? book.volume : -1);

books.sort(sortByTitle());
books.sort(sortByEditor());
books.sort(sortByAuthor());
books.sort(sortBySeries());
books.sort(sortByVolume());

Simple non ?

Plusieurs critères ?

Là c'était encore facile et courant comme truc, mais comment on fait pour trier sur plusieurs critères ?

Imaginons que je veuille trier d'abord par éditeur, puis par auteur, puis par série, puis par numéro de volume puis par titre (en sautant la case série/volume si pas présent) ? Beaucoup plus simple que ce qu'on pourrait penser :

function sortByStrictClassification() {
  return (a: Book, b: Book) => {
    if (a.editor !== b.editor) {
      return sortByEditor()(a, b);
    }
    if (a.author !== b.author) {
      return sortByAuthor()(a, b);
    }
    if ("series" in a && "series" in b && a.series !== b.series) {
      return sortBySeries()(a, b);
    }
    if ("volume" in a && "volume" in b && a.volume !== b.volume) {
      return sortByVolume()(a, b);
    }
    return sortByTitle()(a, b);
  };
}

books.sort(sortByStrictClassification());

Je ne trouve pas l'écriture très élégante (beaucoup de if, des vérifications en double au niveau des champs optionnels, etc.) mais c'est simple à écrire.

Plusieurs critères avec un snippet !

Vous vous en doutez sans doute, j'ai des idées pour améliorer l'écriture du comparateur multi-critère. Je vous propose d'écrire un petit utilitaire pour rendre le truc plus littéral !

Déjà je vous montre ce que j'ai envie d'écrire :

function sortByStrictClassification() {
  return multiSortWith(sortByEditor())
    .then(sortByAuthor())
    .then(sortBySeries())
    .then(sortByVolume())
    .end(sortByTitle());
}

books.sort(sortByStrictClassification());

Beaucoup plus simple à lire non ?

Et comment ça fonctionne sous le capot :


type Comparator<T> = (a: T, b: T) => number;

function multiSortWith<T>(comparator: Comparator<T>) {
  const comparators = [comparator];
  const self = {
    then(thenComparator: Comparator<T>) {
      comparators.push(thenComparator);
      return self;
    },
    end(endComparator: Comparator<T>) {
      self.then(endComparator);
      return (a: T, b: T) => {
        for (const comp of comparators) {
          const diff = comp(a, b);
          if (diff !== 0) {
            return diff;
          }
        }
        return 0;
      };
    },
  } as const;
  return self;
}

L'idée est simple : on construit une liste de comparateur, au fil de l'eau, et quand on passe par end() on renvoie un comparateur qui va tester les comparateurs un par un jusqu'à trouver une différence. Pas si compliqué à construire, plus facile de lire le comparateur multi-critère !

La même chose en immutable !

Si vous vous rappelez le début de l'article, j'évoquais le côté mutable de de la fonction .sort(). En effet, quand on fait books.sort(sortByTitle()) on va modifier books ce qui peut être embêtant dans certains cas (concurrence, trie temporaire pour un traitement particulier, etc.).

La solution la plus basique à ce problème est de dupliquer le tableau avant de trier :

const booksSortedByTitle = [...books].sort(sortByTitle());

Mais c'est coûteux de dupliquer un tableau comme ça (en tout cas, si le tableau est gros), on y pense pas forcément, et ce n'est pas toujours très lisible en fonction du traitement qu'on souhaite faire, par exemple si on veut filtrer / modifier les données dans un enchaînement de map/filter/reduce avec un tri au milieu. Et quand bien même ça fonctionne : on a pas envie de muter un tableau comme ça la plupart du temps !

Heureusement, depuis Baseline 2023 (soit tous les navigateurs depuis Juillet 2023), on peut utiliser .toSorted() à la place de .sort(). Cette fonction prend le même paramètre que .sort(), renvoie aussi le tableau trié, mais ne modifie plus la liste d'origine !

Donc on peut écrire sans souci :

const booksSortedByTitle = books.toSorted(sortByTitle());

Note : en lisant bien la documentation des 2 fonctions, on observe une petite différence dans un cas précis : les sparse array (ou tableau avec des cases vide). En effet .sort() va conserver les éléments manquant à la fin après les éléments undefined, là où .toSorted() va les traiter comme des éléments undefined.

Concrètement, on pourra observer :

let sparse = ['z']
sparse[4] = 'a';
sparse[6] = undefined;

console.log(sparse); // [ "z", <3 empty items>, "a", <1 empty item>, undefined ]
console.log(sparse.toSorted()); // [ "a", "z", undefined, undefined, undefined, undefined, undefined ]
sparse.sort();
console.log(sparse); // [ "a", "z", undefined, <4 empty items> ]

Dans l'absolue, je pense que c'est un cas très à la marge, mais c'est à connaître car ça peut créer des effets de bords dans certains cas particuliers.

Bonus : mélanger = trier par ordre aléatoire ?

Avant de finir cet article, je voulais ajouter un point sur un cas particulier, le cas où on veut mélanger une liste. Ça arrive peu avec les applications de gestions soyons honnêtes (imaginez 2 secondes si votre application de bancaire affichait dans un ordre aléatoire les transactions 🙈), mais pour faire des applications plus grand public de jeux, de recommandation (prendre un article de blog au hasard en plus de ceux qui sont similaires par exemple), choisir au hasard dans sa collection de livres / jeux, etc. Globalement on peut en avoir besoin !

Mais comment on fait ce tri "au hasard", alors que .sort() et .toSorted() même par défaut ont une règle ?

On peut passer par un comparateur qui renvoie un nombre au hasard positif ou négatif sans s'occuper des éléments qu'on lui passe.

function randomlySort() {
    return () => {
        return Math.random() - 0.5;
    }
}

books.sort(randomlySort());

Ici la liste sera triée dans un ordre au hasard comme Math.random() va nous donner un nombre à virgule au hasard compris entre 0 et 1, et donc avec notre - 0.5, on obtient un nombre au hasard entre -0.5 et 0.5. Facile non ?

Conclusion

Les tris n'ont plus de secret pour vous ! Vous êtes maintenant un roi ou une reine du tri des tableaux et plus rien ne pourra vous résister ! 🤓

Plus sérieusement, le tri de tableau c'est quelque chose qu'on fait quasiment tous les jours et pourtant je vois souvent des gens qui ne maîtrise pas entièrement ce fonctionnement. Ce n'est pas forcément toujours une évidence, mais je me dis qu'avoir une article à partager en mode "cheat sheet" au besoin sous la main sera toujours une bonne chose !

Au passage, là j'ai montré comment ça fonctionne en JavaScript/TypeScript, mais on retrouve à peu près la même chose dans d'autres langages, avec des petites nuances sur le côté mutable/immutable et sur le côté sparse array mais c'est de l'ordre du détail, ce qui compte c'est le pattern général qu'on peut appliquer un peu partout !

Sources:

Crédit photo : Générée via Mistral AI avec le prompt suivant

Crée une illustration d'un bibliothécaire concentré, triant soigneusement des livres dans une immense bibliothèque aux étagères remplies de volumes anciens et modernes. La scène doit capturer l'atmosphère paisible et studieuse de la bibliothèque, avec des détails comme des échelles en bois, des lampes de lecture douces, et des fenêtres laissant entrer une lumière naturelle diffuse.