Exercice Algorithme : Le Tri Fusion

Travail à Faire:

Réaliser le Tri Fusion

Principe

Le principe de cet algorithme est de diviser le tableau en sous tableaux de les traiter et ensuite de les fusionner. Cet algorithme est récursif. On divise le tableau en deux sous tableaux qui sont eux mêmes sont divisés en deux sous tableaux, etc.. La condition d'arrêt est lorsque le tableau ne comporte plus qu'un seul élément.
L'algorithme contient plusieurs parties : la division du tableau en deux, le tri des deux tableaux et la fusion des deux tableaux.

Exemple:

Algorithme fusion (T , deb, fin) mid = (deb + fin)/2 ; i = 0 ; i1 = deb ; i2 = mid + 1 ; Tant que (i1 ) Faire Si (T [i1] [i2]) temp[i] = T [i1] ; i1 = i1 + 1 ; Sinon temp[i] = T [i2] ; i2 = i2 + 1 ; Fin Si i = i + 1 ; Fin Tant que Si (i1 ) Pour (j = i1 a mid) Faire temp[i] = T [j] ; i = i + 1 ; Fin Pour Sinon Si (i2 ) Pour (j = i2 a fin) Faire temp[i] = T [j] ; i = i + 1 ; Fin Pour Fin Si Pour (i = deb a fin) Faire T [i] = temp[i] ;Fin Pour