Algorithmique : les tris

Cours complet · OCaml (option informatique), chapitre 9 · prépas MPSI et MP, option informatique

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>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 :

Définition 9.1Spécification du tri

Le résultat d'un tri de l doit être :

ordonné : ses éléments sont en ordre croissant ;
une permutation de l : exactement les mêmes éléments, avec les mêmes multiplicités.

La seconde clause est trop souvent oubliée : une fonction qui renvoie [] est « ordonnée » mais ne trie rien.

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.


let rec insere x l =
  match l with
  | [] -> [x]
  | t :: reste -> if x <= t then x :: l else t :: insere x reste

let rec tri_insertion l =
  match l with
  | [] -> []
  | x :: reste -> insere x (tri_insertion reste)

insere place x dans une liste déjà triée, devant le premier élément qui lui est supérieur. tri_insertion trie la queue, puis y insère la tête.

Complexité : Tri par insertion

Insérer dans une liste de longueur $k$ coûte jusqu'à $k$ comparaisons. Trier $n$ éléments en insère $n$ , d'où un coût en $Θ (n^{2})$ dans le pire cas (liste à l'envers). Simple et efficace sur de petites listes ou des listes presque triées, mais à éviter sur de grandes données.

9.4 Le tri fusion

Idée (diviser pour régner) : couper la liste en deux moitiés, trier chacune récursivement, puis fusionner les deux listes triées.


let rec fusion l1 l2 =
  match l1, l2 with
  | [], _ -> l2
  | _, [] -> l1
  | x :: r1, y :: r2 ->
      if x <= y then x :: fusion r1 l2
      else y :: fusion l1 r2

let rec coupe l =
  match l with
  | [] -> ([], [])
  | [x] -> ([x], [])
  | x :: y :: reste ->
      let (a, b) = coupe reste in
      (x :: a, y :: b)

let rec tri_fusion l =
  match l with
  | [] | [_] -> l
  | _ ->
      let (a, b) = coupe l in
      fusion (tri_fusion a) (tri_fusion b)

fusion entrelace deux listes triées en une seule, en comparant les têtes (filtrage sur le couple (l1, l2)). coupe répartit les éléments alternativement en deux listes de tailles presque égales. tri_fusion combine le tout.

Complexité : Tri fusion

La fusion de deux listes de longueur totale $n$ coûte $Θ (n)$ . La récursion divise la taille par deux à chaque niveau, soit $Θ (lo g n)$ niveaux. Coût total : $Θ (n lo g n)$ garanti (dans tous les cas). C'est l'optimal pour un tri par comparaisons.

9.5 Le tri rapide

Idée (diviser pour régner, autrement) : choisir un pivot, répartir les autres éléments en « plus petits » et « plus grands », trier chaque part, et concaténer.


let rec partition pivot l =
  match l with
  | [] -> ([], [])
  | x :: reste ->
      let (inf, sup) = partition pivot reste in
      if x < pivot then (x :: inf, sup) else (inf, x :: sup)

let rec tri_rapide l =
  match l with
  | [] -> []
  | pivot :: reste ->
      let (inf, sup) = partition pivot reste in
      tri_rapide inf @ [pivot] @ tri_rapide sup

On prend la tête comme pivot, on partitionne la queue, puis on trie récursivement chaque part et l'on recolle : triés-plus-petits, pivot, triés-plus-grands.

Complexité : Tri rapide

En moyenne, le pivot coupe la liste en deux parts comparables : coût $Θ (n lo g n)$ . Mais si le pivot est systématiquement le plus petit ou le plus grand (liste déjà triée, ici), les parts sont déséquilibrées et le coût dégénère en $Θ (n^{2})$ . Les @ répétés alourdissent en outre la constante. En pratique, un bon choix de pivot rend ce tri très rapide — d'où son nom.

9.6 Trier un tableau : le tri par sélection

Sur un tableau, on trie volontiers en place (sans créer de nouvelle structure). Le tri par sélection cherche, à chaque étape, le minimum du reste et l'amène à sa place par un échange.


let tri_selection t =
  let n = Array.length t in
  for i = 0 to n - 2 do
    let imin = ref i in
    for j = i + 1 to n - 1 do
      if t.(j) < t.(!imin) then imin := j
    done;
    let tmp = t.(i) in
    t.(i) <- t.(!imin);
    t.(!imin) <- tmp
  done

À l'étape i, la boucle interne trouve l'indice imin du minimum de t.(i..n-1), qu'on échange avec t.(i). Invariant : après l'étape i, les cases 0..i contiennent les i+1 plus petits éléments, triés. Coût $Θ (n^{2})$ , mais aucune allocation : on modifie le tableau sur place.

Complexité : Comparaison des tris

Tri	Pire cas	Remarque
Insertion (liste)	$Θ (n^{2})$	bon sur presque trié
Sélection (tableau)	$Θ (n^{2})$	en place, peu d'écritures
Fusion (liste)	$Θ (n lo g n)$	garanti, optimal par comparaisons
Rapide (liste)	$Θ (n^{2})$	$Θ (n lo g n)$ en moyenne
Dénombrement (tableau)	$Θ (n + k)$	entiers bornés par $k$ (sans comparaison)

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>9.7 Exercices résolus

Niveau $⋆$ (application directe du cours)

Exercice 1 : Vérifier qu'une liste est triée

Écrire est_trie et l'appliquer à [1; 3; 3; 5] et [1; 4; 2].

Démonstration


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

est_trie [1; 3; 3; 5] vaut true (croissante au sens large : <=), est_trie [1; 4; 2] vaut false (car 4 > 2). L'évaluation paresseuse de && arrête au premier défaut.

Exercice 2 : Insertion dans une liste triée

Écrire insere x l (l triée) et dérouler insere 3 [1; 2; 5].

Démonstration


let rec insere x l =
  match l with
  | [] -> [x]
  | t :: reste -> if x <= t then x :: l else t :: insere x reste

Déroulé : insere 3 [1;2;5] : $3 > 1$ donc 1 :: insere 3 [2;5] ; $3 > 2$ donc 1 :: 2 :: insere 3 [5] ; $3 \leq 5$ donc 1 :: 2 :: (3 :: [5]) $=$ [1; 2; 3; 5].

Exercice 3 : Fusionner deux listes triées

Écrire fusion l1 l2 et l'appliquer à fusion [1; 4] [2; 3; 5].

Démonstration


let rec fusion l1 l2 =
  match l1, l2 with
  | [], _ -> l2
  | _, [] -> l1
  | x :: r1, y :: r2 ->
      if x <= y then x :: fusion r1 l2
      else y :: fusion l1 r2

fusion [1;4] [2;3;5] : $1 \leq 2$ → 1 :: fusion [4] [2;3;5] ; $4 > 2$ → 1 :: 2 :: fusion [4] [3;5] ; $4 > 3$ → ... 3 :: fusion [4] [5] ; $4 \leq 5$ → [1; 2; 3; 4; 5].

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Exercice 4 : Tri par insertion complet

Assembler tri_insertion à partir de insere, et expliquer sa terminaison.

Démonstration


let rec tri_insertion l =
  match l with
  | [] -> []
  | x :: reste -> insere x (tri_insertion reste)

On trie la queue (plus courte) puis on y insère la tête : l'appel récursif porte sur reste, strictement plus court, d'où la terminaison. La correction repose sur le fait que insere préserve le caractère trié.

Exercice 5 : Tri fusion

Écrire coupe et tri_fusion, et justifier le coût $Θ (n lo g n)$ .

Démonstration


let rec coupe l =
  match l with
  | [] -> ([], [])
  | [x] -> ([x], [])
  | x :: y :: reste ->
      let (a, b) = coupe reste in
      (x :: a, y :: b)

let rec tri_fusion l =
  match l with
  | [] | [_] -> l
  | _ ->
      let (a, b) = coupe l in
      fusion (tri_fusion a) (tri_fusion b)

À chaque niveau de récursion, le travail total (couper + fusionner) est $Θ (n)$ ; il y a $Θ (lo g n)$ niveaux car la taille est divisée par deux. Le coût est donc $Θ (n lo g n)$ , et ce dans tous les cas (contrairement au tri rapide).

Exercice 6 : Tri rapide

Écrire partition et tri_rapide, et donner un cas où il dégénère en $Θ (n^{2})$ .

Démonstration


let rec partition pivot l =
  match l with
  | [] -> ([], [])
  | x :: reste ->
      let (inf, sup) = partition pivot reste in
      if x < pivot then (x :: inf, sup) else (inf, x :: sup)

let rec tri_rapide l =
  match l with
  | [] -> []
  | pivot :: reste ->
      let (inf, sup) = partition pivot reste in
      tri_rapide inf @ [pivot] @ tri_rapide sup

Sur une liste déjà triée, la tête (pivot) est toujours le plus petit : inf est vide et sup contient tout le reste. La récursion ne réduit la taille que de $1$ par étage, d'où $Θ (n^{2})$ . Choisir un meilleur pivot (médiane, aléatoire) évite ce travers.

Exercice 7 : Tri par sélection en place

Écrire tri_selection sur un tableau, et énoncer son invariant.

Démonstration


let tri_selection t =
  let n = Array.length t in
  for i = 0 to n - 2 do
    let imin = ref i in
    for j = i + 1 to n - 1 do
      if t.(j) < t.(!imin) then imin := j
    done;
    let tmp = t.(i) in
    t.(i) <- t.(!imin);
    t.(!imin) <- tmp
  done

Invariant (boucle externe) : au début de l'étape i, les cases 0..i-1 contiennent, triés, les i plus petits éléments du tableau. À la fin (i = n-1), tout est trié. Le tri est en place : aucune allocation, on échange des cases.

Niveau $⋆ ⋆ ⋆$ (approfondissement)

Exercice 8 : Valider un tri

Écrire est_permutation l1 l2 (mêmes éléments, mêmes multiplicités) en s'appuyant sur un tri, puis verifie tri l qui teste que tri l respecte la spécification complète.

Démonstration


let est_permutation l1 l2 = tri_insertion l1 = tri_insertion l2

let verifie tri l =
  let r = tri l in
  est_trie r && est_permutation r l

Deux listes sont permutations l'une de l'autre si et seulement si elles donnent la même liste une fois triées (on compare alors par égalité structurelle =). verifie vérifie les deux clauses du contrat — ordonné et permutation : c'est un test de propriété, à lancer sur des entrées variées pour gagner confiance dans une fonction de tri.

Exercice 9 : Le tri par dénombrement

Écrire tri_denombrement t k qui trie un tableau d'entiers tous compris entre 0 et k, en $Θ (n + k)$ , sans aucune comparaison.

Démonstration


let tri_denombrement t k =
  let compte = Array.make (k + 1) 0 in
  for i = 0 to Array.length t - 1 do
    compte.(t.(i)) <- compte.(t.(i)) + 1
  done;
  let resultat = Array.make (Array.length t) 0 in
  let pos = ref 0 in
  for v = 0 to k do
    for _j = 1 to compte.(v) do
      resultat.(!pos) <- v;
      pos := !pos + 1
    done
  done;
  resultat

On compte les occurrences de chaque valeur (compte.(v)), puis on réécrit chaque valeur v autant de fois qu'elle apparaît, dans l'ordre croissant. Aucune comparaison : on exploite que les valeurs sont des indices possibles. C'est plus rapide que $Θ (n lo g n)$ , mais au prix d'une hypothèse forte (entiers bornés) et d'un tableau auxiliaire de taille $k + 1$ .

Exercice 10 : Insérer sans `@` — fusion optimisée

Le tri rapide ci-dessus abuse de @. Sans le corriger entièrement, expliquer pourquoi tri_rapide inf @ [pivot] @ tri_rapide sup est coûteux, et proposer la piste d'un accumulateur.

Démonstration

Chaque @ recopie son membre gauche (chapitre 2) : tri_rapide inf @ ... reparcourt tout le préfixe déjà trié à chaque remontée de la récursion, ajoutant un facteur linéaire. La piste classique est de passer un accumulateur — la liste « déjà triée qui suit » — pour préfixer les éléments par :: (temps constant) au lieu de concaténer :


let rec tri_rapide_acc l suite =
  match l with
  | [] -> suite
  | pivot :: reste ->
      let (inf, sup) = partition pivot reste in
      tri_rapide_acc inf (pivot :: tri_rapide_acc sup suite)

let tri_rapide l = tri_rapide_acc l []

On construit le résultat de droite à gauche par ::, sans aucun @ : la même technique d'accumulateur qu'au renverse du chapitre 2.

Synthèse du chapitre (à retenir)

Spécifier un tri : le résultat est ordonné et une permutation de l'entrée — les deux clauses.
Insertion (liste) : insérer chaque élément à sa place dans la partie triée ; $Θ (n^{2})$ , bon sur presque trié.
Fusion (liste, diviser pour régner) : couper, trier les moitiés, fusionner ; $Θ (n lo g n)$ garanti.
Rapide (liste) : pivot + partition ; $Θ (n lo g n)$ en moyenne, $Θ (n^{2})$ au pire (pivot mal choisi) ; éviter les @ via un accumulateur.
Sélection (tableau, en place) : amener le minimum du reste à sa place ; $Θ (n^{2})$ , sans allocation.
Dénombrement (tableau, entiers bornés) : compter puis réécrire ; $Θ (n + k)$ , sans comparaison.
Pour valider un tri : est_trie et est_permutation (deux listes triées égales) sur des entrées variées.

9.8 Exercices d'entraînement

Légende : $⋆$ application directe, $⋆ ⋆$ raisonnement intermédiaire, $⋆ ⋆ ⋆$ approfondissement ; $⧫$ signale un classique incontournable. La numérotation prolonge celle des dix exercices résolus.

Thème A — Autour de l'ordre.

[11.] $⋆$ Écrire est_decroissante l (croissante au sens large à l'envers).
[12.] $⋆ ⋆$ Écrire minimum_liste l : int option (sans trier).
[13.] $⋆ ⋆$ $⧫$ Écrire insere_decroissant et en déduire un tri décroissant par insertion.

Thème B — Tris sur listes.

[14.] $⋆ ⋆$ Modifier fusion pour qu'elle élimine les doublons à la volée (union de deux ensembles triés).
[15.] $⋆ ⋆ ⋆$ Écrire une version de coupe qui renvoie la première et la seconde moitié consécutives (et non en alternance).
[16.] $⋆ ⋆ ⋆$ $⧫$ Compter le nombre de comparaisons effectuées par tri_insertion sur une liste donnée (à l'aide d'une référence).

Thème C — Tris sur tableaux.

[17.] $⋆ ⋆$ Écrire le tri_bulles en place (échanger les voisins mal ordonnés jusqu'à stabilité).
[18.] $⋆ ⋆$ Écrire tri_insertion_tableau (insertion en place sur un tableau).
[19.] $⋆ ⋆ ⋆$ Adapter tri_denombrement pour des entiers dans [a, b] quelconque (pas forcément à partir de $0$ ).

Thème D — Applications.

[20.] $⋆ ⋆$ À l'aide d'un tri, écrire mediane l (élément médian d'une liste d'entiers).
[21.] $⋆ ⋆ ⋆$ Écrire k_plus_petits l k : les k plus petits éléments, triés.
[22.] $⋆ ⋆ ⋆$ $⧫$ Discuter : pour trier $1 0^{6}$ entiers compris entre $0$ et $100$ , quel tri choisir et pourquoi ?

Continuer sur Adloun : animation, QCM, fiches, exercices

Algorithmique : les tris

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>9.1 Introduction et motivation

9.2 Spécifier le tri

9.3 Le tri par insertion

Complexité : Tri par insertion

9.4 Le tri fusion

Complexité : Tri fusion

9.5 Le tri rapide

Complexité : Tri rapide

9.6 Trier un tableau : le tri par sélection

Complexité : Comparaison des tris

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>9.7 Exercices résolus

Niveau ⋆ (application directe du cours)

Niveau ⋆⋆ (raisonnement intermédiaire)

Niveau ⋆⋆⋆ (approfondissement)

9.8 Exercices d'entraînement

Thème A — Autour de l'ordre.

Thème B — Tris sur listes.

Thème C — Tris sur tableaux.

Thème D — Applications.

Niveau $⋆$ (application directe du cours)

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Niveau $⋆ ⋆ ⋆$ (approfondissement)