NSI Terminale

Diviser pour régner : Tri Fusion


Diviser pour régner

Le diviser pour régner est une méthode algorithmique basée sur le principe suivant :

On prend un problème (généralement complexe à résoudre), on divise ce problème en une multitude de petits problèmes.
L'idée étant que les "petits problèmes" seront plus simples à résoudre que le problème original. Une fois les petits problèmes résolus, on recombine les "petits problèmes résolus" afin d'obtenir la solution du problème de départ.

Le paradigme "diviser pour régner" repose donc sur 3 étapes :

  • DIVISER : le problème d'origine est divisé en un certain nombre de sous-problèmes
  • RÉGNER : on résout les sous-problèmes (les sous-problèmes sont plus faciles à résoudre que le problème d'origine)
  • COMBINER : les solutions des sous-problèmes sont combinées afin d'obtenir la solution du problème d'origine.

Les algorithmes basés sur le paradigme "diviser pour régner" sont très souvent des algorithmes récursifs.

1 - Principe du Tri Fusion

Nous avons déjà étudié des algorithmes de tri : le tri par insertion et le tri par sélection, en classe de première.
Nous allons maintenant étudier une nouvelle méthode de tri, le tri-fusion.
Comme pour les algorithmes déjà étudiés, cet algorithme de tri fusion prend en entrée un tableau non trié et donne en sortie, le même tableau, mais trié.

Pour commencer une petite video :

Ci-dessous un premier exemple détaillé

Etape 0
Etape 1
Etape 2
Etape 3
Etape 4
Etape 5
Etape 6
En une seule image
exemple\

Ci-dessous un deuxième exemple

Application de cet algorithme sur le tableau A = [23, 12, 4, 56, 35, 32, 42, 57, 3] :


01° Reprenez tout le raisonnement qui vient d'être fait sur le tableau T = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Vous n'hésiterez pas à faire un schéma.

2 - Algorithme

Tri Fusion

tri_fusion (tableau) :
    Si la longueur est > 1:
      # séparer
      milieu = longueur // 2
      gauche = tableau [0 ... milieu - 1]
      droite = tableau [milieu ... fin]

      # diviser
      tri_fusion(gauche)
      tri_fusion(droite)

      # combiner
      fusion(tableau, gauche, droite)
	  	  

Algorithme Fusion

fusion (tableau, gauche, droite)
	i, j, k = 0
	tant que i < longueur de gauche et j < longueur de droite
		Si gauche[i] < droite[j] alors
			tableau[k] = gauche[i]
			i = i + 1
		Sinon
			tableau[k] = droite[j]
			j = j + 1
		k = k + 1
		
	# Pour les éléments restant, les ajouter à fin de tableau
	tant que i < longueur de gauche
        tableau[k] = gauche[i]
		i = i + 1
		k = k + 1
    tant que j < longueur de droite
        tableau[k] = droite[j]
		j = j + 1
        k = k + 1	

Exemple détaillé pour la fusion

Fusionner g = [1, 2, 5] et d = [3, 4] : le premier élément du tableau fusionné sera le premier élément d’une des deux tableaux d’entrée (soit 1, soit 3) car ce sont des listes triées.


g = [1, 2, 5] et d = [3, 4]

  • Comparer 1 et 31 est le plus petit.

    t=[1]

  • Comparer 2 et 32 est le plus petit.

    t=[1, 2]

  • Comparer 5 et 33 est le plus petit.

    t=[1, 2, 3]

  • Comparer 5 et 44 est le plus petit.

    t=[1, 2, 3, 4]

  • Compléter 5t=[1, 2, 3, 4, 5]

Récursion

Il faut bien comprendre l’ordre dans lequel sont effectués les appels récursifs

tri_fusion s’appelle elle même AVANT d’appeler fusion

Donc :

D’abord on découpe le tableau, sa première moitié, son premier quart etc. jusqu’à avoir un élément (le premier).

Ensuite on fait fusion sur lui (il ne change pas) Ensuite on arrive à la fusion des deux premiers,

Pour avancer il faut avoir découpé (3 et 4) jusqu’à avoir une taille 1, Ensuite on les fusionne.

Et on fusionne les éléments 0, 1, avec 2, 3.

etc.

L’algorithme ne progresse pas “par étage” comme la présentation le laisse croire.

3 - Complexité

Nous avons vu que le tri par insertion et tri par sélection ont tous les deux une complexité $O(n^2)$.
Qu'en est-il pour le tri-fusion ?

Le calcul rigoureux de la complexité de cet algorithme sort du cadre de ce cours.
Mais, en remarquant que la première phase (DIVISER) consiste à "couper" les tableaux en deux plusieurs fois de suite, intuitivement, on peut dire qu'un logarithme base 2 doit intervenir. La deuxième phase consiste à faire des comparaisons entre les premiers éléments de chaque tableau à fusionner, on peut donc supposer que pour un tableau de n éléments, on aura n comparaisons.
En combinant ces 2 constations on peut donc dire que la complexité du tri-fusion est en $O(n.log(n))$
(encore une fois la "démonstration" proposée ici n'a rien de rigoureux).

La comparaison des courbes de la fonction $n^2$ (en rouge) et $n.log(n)$ (en bleu) :

nous montre que l'algorithme de tri-fusion est plus "efficace" que l'algorithme de tri par insertion ou que l'algorithme de tri par sélection.

Activité publiée le 25 03 2021
Auteur : Andjekel
Sources : pixees et NSI4NOOBS