Algorithmique : les tris

9.1 Introduction et motivation

Les huit premiers chapitres ont couvert le langage OCaml. Mais l'option informatique ne s'arrête pas à la syntaxe : elle demande de concevoir et d'analyser des algorithmes. Ce chapitre ouvre cette seconde moitié en s'attaquant à un problème fondateur, le tri, qui mobilise d'un coup tout ce qu'on a appris — listes et filtrage (chapitre 2), récursion, tableaux (chapitre 5), et le raisonnement de complexité.

Trier, c'est ranger une collection dans l'ordre croissant. Le problème est si central qu'on en connaît des dizaines d'algorithmes ; on en étudie ici trois sur les listes (insertion, fusion, rapide) et deux sur les tableaux (sélection, dénombrement), en comparant leurs coûts. Au-delà du tri lui-même, ces algorithmes illustrent deux grandes idées : « diviser pour régner » (fusion, rapide) et l'art de choisir la bonne structure de données.

9.2 Spécifier le tri

Avant de coder, énonçons le contrat. Une fonction de tri prend une collection et en renvoie une autre qui doit vérifier deux propriétés, indissociables :

La première propriété se teste facilement :

let rec est_trie l =
  match l with
  | [] | [_] -> true
  | x :: (y :: _ as reste) -> x <= y && est_trie reste

Le motif [] | [_] regroupe les listes de zéro ou un élément (toujours triées). Le motif x :: (y :: _ as reste) nomme à la fois les deux premiers éléments x, y et la queue reste (grâce au mot-clé as) : on vérifie x <= y puis on continue.

9.3 Le tri par insertion

Idée : trier « comme on range des cartes en main » — on prend les éléments un à un et on insère chacun à sa place dans la partie déjà triée.