Implémentation récursive du Tri Fusion

Bonjour !

Dans la leçon précédente, nous avons exploré la stratégie "Diviser pour Régner", une méthode de conception puissante qui décompose un problème complexe en parties plus simples. Nous avons vu l'idée générale avec la recherche dichotomique et nous avons eu un aperçu du tri fusion.

Aujourd'hui, nous allons mettre cette stratégie en pratique. L'objectif est d'implémenter en pseudo-code l'un des algorithmes de tri les plus importants : le tri fusion (Merge Sort). Vous allez voir concrètement comment la récursivité, que nous avons introduite avec "Diviser pour Régner", nous permet de construire une solution élégante et efficace pour trier un tableau. C'est une étape clé pour comprendre comment concevoir des algorithmes qui mènent à du "code clean" et performant.

1. La pierre angulaire du Tri Fusion : l'étape "Combiner"

Rappelez-vous les trois étapes de "Diviser pour Régner" : Diviser, Régner, Combiner. Pour le tri fusion, la magie opère principalement dans l'étape "Combiner". C'est là que le tri s'effectue réellement.

L'idée est la suivante : si nous avons deux tableaux qui sont déjà triés, comment pouvons-nous les fusionner pour obtenir un seul grand tableau trié ?

Imaginez que vous avez deux paquets de cartes, chaque paquet étant déjà trié par ordre croissant. Pour les fusionner en un seul paquet trié, vous regarderiez la première carte de chaque paquet, prendriez la plus petite des deux, et la placeriez dans un nouveau paquet. Vous répéteriez ce processus jusqu'à ce que l'un des paquets de départ soit vide. Il ne vous resterait plus qu'à ajouter les cartes restantes de l'autre paquet à la fin du nouveau.

C'est exactement ce que fait l'algorithme de fusion. Pour bien comprendre ce mécanisme, je vous invite à lire la section "Le fusionnement" du document suivant.

Algorithmique IV - Le tri fusion

Ce texte, de J.P. Zanotti, explique en détail et avec une excellente analogie l'algorithme de fusion, qui est le cœur du tri fusion. Il fournit également le pseudo-code de la fonction.

Lisez attentivement la section intitulée "Le fusionnement". Concentrez-vous sur l'analogie des paquets de cartes et essayez de suivre la logique du pseudo-code de l'algorithme Fusionner.

Analyse de l'algorithme `Fusionner`

L'algorithme Fusionner prend en entrée un tableau L et trois indices p, q, r qui délimitent deux sous-tableaux adjacents et déjà triés : L[p..q] (la partie gauche) et L[q+1..r] (la partie droite).

Le processus, comme vous l'avez lu, se déroule ainsi :

Copie : On copie les deux sous-tableaux dans des tableaux auxiliaires, G (gauche) et D (droite). Cela est nécessaire pour ne pas écraser les valeurs dans L pendant qu'on les lit.
Comparaison et Fusion : On utilise trois pointeurs (indices) : i pour G, j pour D, et k pour L (à partir de p). On compare G[i] et D[j]. On place le plus petit des deux dans L[k] et on avance le pointeur correspondant (i ou j) ainsi que le pointeur k.
Copie du reste : On répète l'étape 2 jusqu'à ce que l'un des tableaux auxiliaires (G ou D) soit entièrement parcouru. Ensuite, on copie simplement les éléments restants de l'autre tableau à la fin de L.

L'image suivante illustre ce mécanisme de comparaison avec les pointeurs i, j et k.

Illustration du processus de fusion dans le Tri Fusion (Merge Sort) — Cette image montre comment deux tableaux triés, T1 et T2, sont fusionnés. Les pointeurs i et j parcourent T1 et T2, tandis que le pointeur k construit le tableau final en sélectionnant à chaque étape le plus petit élément entre T1[i] et T2[j].

2. L'assemblage récursif : l'algorithme `Tri-Fusion`

Maintenant que nous maîtrisons la fusion, la structure globale de Tri-Fusion devient très simple à comprendre. C'est une application directe de "Diviser pour Régner" :

Diviser : On divise le tableau L[p..r] en deux moitiés en calculant l'indice du milieu q.
Régner : On appelle récursivement Tri-Fusion sur la moitié gauche (L, p, q) et sur la moitié droite (L, q+1, r).
Combiner : On appelle Fusionner(L, p, q, r) pour fusionner les deux moitiés, qui sont maintenant triées grâce aux appels récursifs.

La récursivité s'arrête lorsque le sous-tableau à trier ne contient qu'un seul élément (ou aucun). C'est notre cas de base. Un tableau d'un seul élément est, par définition, déjà trié. C'est pourquoi l'algorithme n'agit que SI (p < r).

Voici le pseudo-code correspondant, tiré du même document.

ALGORITHME Tri-Fusion(@L, p, r)
DONNEES
  L: tableau de valeurs
  p, r: entiers
VARIABLES
  q: entier
DEBUT
  SI (p < r) ALORS
    q ← (p + r) / 2  // Diviser
    Tri-Fusion(L, p, q)      // Régner (partie gauche)
    Tri-Fusion(L, q + 1, r)  // Régner (partie droite)
    Fusionner(L, p, q, r)    // Combiner
  FSI
FIN

Le schéma ci-dessous montre la séquence complète des appels récursifs (division) et des fusions pour un tableau d'exemple.

Visual Representation of Merge Sort Algorithm — Cet organigramme visuel décompose le tri fusion. En descendant, le tableau est divisé récursivement jusqu'à obtenir des tableaux d'un seul élément. En remontant, les sous-tableaux sont fusionnés deux par deux pour finalement obtenir le tableau entièrement trié.

3. Traçage manuel d'un exemple

Pour bien ancrer votre compréhension, traçons ensemble l'algorithme sur un petit tableau : T = [6, 5, 3, 1]. L'appel initial est Tri-Fusion(T, 0, 3).

Tri-Fusion(T, 0, 3): p=0, r=3. p < r est vrai.
- q = (0+3)/2 = 1.
- Appel Tri-Fusion(T, 0, 1).
  1. Tri-Fusion(T, 0, 1): p=0, r=1. p < r est vrai.
    - q = (0+1)/2 = 0.
    - Appel Tri-Fusion(T, 0, 0).
      - p=0, r=0. p < r est faux. L'appel se termine. Le sous-tableau [6] est trié.
    - Appel Tri-Fusion(T, 1, 1).
      - p=1, r=1. p < r est faux. L'appel se termine. Le sous-tableau [5] est trié.
    - Appel Fusionner(T, 0, 0, 1). On fusionne [6] et [5]. Le sous-tableau T[0..1] devient [5, 6].
- Appel Tri-Fusion(T, 2, 3).
  1. Tri-Fusion(T, 2, 3): p=2, r=3. p < r est vrai.
    - q = (2+3)/2 = 2.
    - Appel Tri-Fusion(T, 2, 2).
      - p=2, r=2. p < r est faux. [3] est trié.
    - Appel Tri-Fusion(T, 3, 3).
      - p=3, r=3. p < r est faux. [1] est trié.
    - Appel Fusionner(T, 2, 2, 3). On fusionne [3] et [1]. Le sous-tableau T[2..3] devient [1, 3].
- Appel Fusionner(T, 0, 1, 3). On fusionne [5, 6] et [1, 3]. Le tableau T final devient [1, 3, 5, 6].

Le tableau est maintenant trié !

4. Exercice pratique

Votre objectif est de maîtriser l'algorithme par la pratique. Prenez une feuille de papier et un crayon.

Problème : Appliquez l'algorithme Tri-Fusion pour trier le tableau suivant : [38, 27, 43, 3, 9, 82, 10].

Pour ce faire :

Écrivez l'arbre des appels récursifs, comme dans l'exemple ci-dessus.
Pour chaque appel à Fusionner, montrez l'état des deux sous-tableaux en entrée et le résultat de leur fusion.
Indiquez l'état final du tableau.

Cet exercice est fondamental. Il vous force à simuler le comportement de la machine, ce qui est la meilleure façon de s'approprier la logique récursive et le mécanisme de fusion.

Cliquez ici pour voir les étapes principales de la solution

L'arbre des appels va diviser le tableau jusqu'à obtenir des éléments uniques. Les fusions se feront dans l'ordre suivant :

Fusionner([38], [27]) -> [27, 38]
Fusionner([43], [3]) -> [3, 43]
Fusionner([27, 38], [3, 43]) -> [3, 27, 38, 43]
Fusionner([9], [82]) -> [9, 82]
Fusionner([9, 82], [10]) -> [9, 10, 82]
Fusionner([3, 27, 38, 43], [9, 10, 82]) -> [3, 9, 10, 27, 38, 43, 82]

Le tableau final trié est : [3, 9, 10, 27, 38, 43, 82]. Essayez de bien retrouver toutes les étapes de division qui mènent à ces fusions.

Conclusion

Félicitations ! Vous venez d'implémenter et de tracer l'un des algorithmes de tri les plus fondamentaux et efficaces. C'est un grand pas dans votre parcours.

Points clés à retenir :

Le tri fusion implémente parfaitement la stratégie "Diviser pour Régner".
Le "vrai" travail de tri se fait dans la fonction Fusionner, qui combine deux sous-tableaux déjà triés de manière efficace.
La fonction principale Tri-Fusion est récursive. Son rôle est de diviser le problème jusqu'au cas de base (un tableau d'un seul élément) et d'orchestrer les appels à Fusionner.
Le traçage manuel est une compétence essentielle pour comprendre et déboguer les algorithmes récursifs.

Et après ?

Nous avons implémenté le tri fusion, mais pourquoi est-il considéré comme si efficace ? Il est temps de répondre à cette question. Dans la prochaine leçon, nous analyserons la complexité du tri fusion. Nous allons démontrer mathématiquement pourquoi sa complexité en $O (n lo g n)$ le rend bien supérieur aux tris simples en $O (n^{2})$ que nous avons étudiés, surtout lorsque la taille des données augmente. Cela vous donnera une appréciation encore plus profonde de la puissance de la stratégie "Diviser pour Régner".

Recommended resources