Tri fusion fonctionnel en OCaml

1. La Stratégie "Diviser pour Régner" du Tri Fusion

Le tri fusion (Merge Sort) est un algorithme récursif qui suit une stratégie simple en trois temps :

1. Diviser : Si la liste contient plus d'un élément, on la coupe en deux moitiés (à peu près) égales. Si la liste est vide ou n'a qu'un seul élément, elle est déjà triée par définition. C'est notre cas de base.
2. Régner : On trie récursivement chacune des deux moitiés obtenues.
3. Combiner : On fusionne les deux moitiés, qui sont maintenant triées, pour former une seule liste triée.

L'image suivante illustre ce processus. L'étape de division décompose le problème en sous-problèmes triviaux, puis l'étape de fusion reconstruit la solution pas à pas.

La clé de l'algorithme réside dans l'efficacité de l'étape de fusion. Pour implémenter cet algorithme en OCaml, nous allons donc créer trois fonctions qui correspondent à ces étapes : separer, fusion et la fonction principale tri_fusion.

2. L'Étape de Combinaison : la fonction fusion

Commençons par l'étape la plus intéressante : la fusion. Supposons que nous ayons deux listes, l1 et l2, qui sont déjà triées. Notre objectif est de produire une nouvelle liste triée contenant tous les éléments de l1 et l2.

L'algorithme est le suivant :

• On compare les têtes des deux listes.
• Le plus petit des deux éléments devient la tête de notre nouvelle liste.
• On continue récursivement le processus de fusion avec le reste des listes.
• Si l'une des listes devient vide, il suffit de concaténer l'autre liste (qui est déjà triée) à la fin du résultat.

L'image ci-dessous détaille ce processus de comparaison et de construction itérative.

L'implémentation en OCaml est une traduction directe de cette logique récursive.

Voici le code que vous venez d'analyser :

(* Fusionne l1 et l2 deux listes supposées triées par ordre croissant *)
let rec fusion (l1: 'a list) (l2: 'a list) : 'a list =
  match l1, l2 with
  | [], _ -> l2
  | _, [] -> l1
  | x1::q1, x2::q2 ->
      if x1 < x2 then x1 :: fusion q1 l2
      else x2 :: fusion l1 q2

Notez la clarté de cette fonction :

• Le type est 'a list -> 'a list -> 'a list, indiquant son caractère polymorphe. Elle peut trier des listes de n'importe quel type comparable.
• Le filtrage sur le couple (l1, l2) permet de traiter tous les cas de manière exhaustive.
• L'appel récursif construit la nouvelle liste en utilisant l'opérateur :: sans aucune mutation, respectant ainsi le paradigme fonctionnel.

3. L'Étape de Division : la fonction separer

Maintenant, nous devons implémenter la fonction qui divise une liste en deux. Une stratégie simple consiste à distribuer les éléments de la liste un par un, alternativement dans deux listes distinctes.

Par exemple, pour la liste [1; 2; 3; 4; 5], on mettrait 1 dans la première, 2 dans la seconde, 3 dans la première, 4 dans la seconde, et 5 dans la première, ce qui donnerait [1; 3; 5] et [2; 4].

La fonction separer que vous avez vue est la suivante :

(* renvoie deux listes l1 l2 de même taille à 1 près,
   contenant les éléments de l *)
let rec separer (l: 'a list) : 'a list * 'a list =
  match l with
  | [] -> [], []
  | [x] -> [x], []
  | x::y::q ->
      let l1, l2 = separer q in
      x::l1, y::l2

Cette fonction retourne un couple de listes, ce qui est la manière idiomatique en OCaml de retourner plusieurs valeurs. Une autre implémentation très courante, visible dans la ressource L'approche qualité avec OCaml, consiste à créer une fonction pour les éléments de rang pair et une autre pour ceux de rang impair. L'approche avec une seule fonction retournant un couple est généralement plus efficace car elle ne parcourt la liste qu'une seule fois.

4. Assemblage Final : la fonction tri_fusion

Nous avons maintenant tous les outils pour construire la fonction principale. Elle orchestrera le processus "Diviser pour Régner" :

1. Gérer les cas de base : une liste vide ou à un seul élément est déjà triée.
2. Sinon, appeler separer pour diviser la liste.
3. Appeler tri_fusion récursivement sur les deux moitiés.
4. Appeler fusion pour combiner les deux résultats triés.

Le code final est d'une simplicité remarquable :

let rec tri_fusion (l : 'a list) : 'a list =
  match l with
  | [] | [_] -> l (* Le motif [_] matche toute liste à un élément *)
  | _ ->
      let l1, l2 = separer l in
      fusion (tri_fusion l1) (tri_fusion l2)

5. Exercice et Analyse

Maintenant, à vous de jouer.

1. Implémentation : Dans un fichier tri_fusion.ml, recopiez les trois fonctions (fusion, separer, tri_fusion).
2. Test : Ajoutez quelques tests pour vérifier le bon fonctionnement de votre tri. Par exemple :

   let ma_liste = [5; 2; 8; 1; 9; 4; 7; 3; 6];;
   let liste_triee = tri_fusion ma_liste;;
   (* Affichez liste_triee pour vérifier le résultat. *)
   (* Le résultat attendu est [1; 2; 3; 4; 5; 6; 7; 8; 9] *)
   

   N'hésitez pas à tester avec des listes vides, unitaires, et déjà triées ou triées en ordre inverse.
3. Analyse de Complexité (Réflexion) : La ressource Premiers programmes en OCaml vous guide pour analyser la complexité. La relation de récurrence pour le temps d'exécution $C_n$ sur une liste de taille $n$ est :
   $C_n=2\cdot C_{n/2}+\Theta (n)$
   Le terme $\Theta (n)$ provient des fonctions separer et fusion qui parcourent leurs entrées une fois. Comme vous l'avez vu dans le module sur l'analyse d'algorithmes, cette récurrence se résout en $C_n=\Theta (n\log n)$. Le tri fusion garantit cette complexité dans tous les cas, ce qui est l'un de ses grands atouts.

Conclusion

Aujourd'hui, vous avez implémenté de manière purement fonctionnelle un algorithme de tri classique et efficace. Cette leçon a permis de consolider votre maîtrise de la récursivité, du filtrage par motif sur les listes et de la composition de fonctions.

Points clés à retenir :

• L'approche "Diviser pour Régner" se traduit naturellement par des fonctions récursives en OCaml.
• L'implémentation du tri fusion se décompose logiquement en trois fonctions : separer, fusion et la fonction principale tri_fusion.
• L'immutabilité des listes OCaml nous force à construire de nouvelles listes à chaque étape, garantissant l'absence d'effets de bord, mais cela a un coût en termes d'allocations mémoire.
• Le tri fusion est un algorithme polymorphe et stable avec une complexité temporelle garantie en $\Theta (n\log n)$.

Dans notre prochaine leçon, nous continuerons d'explorer l'implémentation d'algorithmes fondamentaux en OCaml. Nous nous attaquerons aux graphes et implémenterons l'algorithme de parcours en largeur (BFS). Cela posera un nouveau défi intéressant : comment gérer une structure de données comme une file d'attente dans un contexte purement fonctionnel.