Bilan sur le tri fusion

Tri fusion

• On utilise la méthode « Diviser pour régner »

• On partage le tableau en deux « moitiés » et l'on trie de façon récursive ces moitiés

  • Un tableau de longueur \(0\) ou \(1\) est toujours trié

  • Lors de la fusion de deux tableaux, on choisit toujours le plus petit élément de l'un des sous-tableaux

• Il y a autant d'étapes de partages et de fusion qu'il est possible de couper la taille du tableau en \(2\)

• À chaque étape de fusion on doit traiter les \(N\) valeurs du tableau

• L'algorithme en pseudo-code est :

  📋 Pseudo-code

  Fonction tri_fusion(tableau) :
      Si la taille du tableau est strictement inférieure à 2 :
          Renvoyer tableau
  
      milieu est l'indice du centre du tableau
  
      gauche est le résultat du tri fusion de la première « moitié » de tableau (avant l'indice milieu -exclu-)
      droite est le résultat du tri fusion de la seconde « moitié » de tableau (après l'indice milieu -inclus-)
  
      Renvoyer la fusion de gauche et droite
  

Remarque

Le tri rapide n'étant pas au programme de la spécialité NSI, on ne propose pas de bilan le concernant.