Diviser pour régner : Tri Fusion

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é

En une seule image

\

Ci-dessous un deuxième exemple

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

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] et i = i + 1
      Sinon
          tableau[k] = droite[j] et j = j + 1
      k = k + 1

  Pour les éléments restant, les ajouter à fin de tableau

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 3 → 1 est le plus petit.

  t=[1]

• Comparer 2 et 3 → 2 est le plus petit.

  t=[1, 2]

• Comparer 5 et 3 → 3 est le plus petit.

  t=[1, 2, 3]

• Comparer 5 et 4 → 4 est le plus petit.

  t=[1, 2, 3, 4]

• Compléter 5 → t=[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.

4 - Implémentation en Python

⇩ ⇧ ⤊

Implémentez en Python l'algorithme de tri-fusion vu ci-dessus.
Vous testerez votre programme à l'aide du tableau suivant A = [23, 12, 4, 56, 35, 32, 42, 57, 3]