Tri fusion
Principe
Le principe du tri par fusion est plutot simple. On dit que trier un tableau de taille N, c'est trier deux tableaux de taille N/2; une fois les deux tableaux trié on à plus qu'à les reunir (les fusionner) de sorte à ce que le tableau final soit trié. Ce tri bien sur utilise une notion de recursivite (un tableau etant la somme de deux tableaux)
Algorithme
L'algorithme va se faire en deux partie, la première sera recursive et l'autre consistera à fusionner deux tableaux.
Fonction tri_fusion (T) retourne tableau d'entier Parametre (e)T: tableau d'entier [1...N] Variable: T1, T2 deux tableaux d'entier de taille N/2 (a peu pres) DEBUT si (N=1) renvoie T T1 = tri_fusion (SousTableau (T, 1, N/2)) T2 = tri_fusion (SousTableau (T, N/2, N)) retourne fusion(T1, T2) FIN
Fonction fusion (T1, T2) retourne tableau d'entier Parametre (e)T1[1...N], T2[1...M]: tableau d'entier Variable T: tableau entier [1...M+N] i, j: entier DEBUT i<-1 j<-1 tantque (i+j-1 != N+M) si (i <= N) alors si (j <= M) alors si (T1[i] < T2[j]) alors T[i+j-1]<-T1[i] i<-i+1 sinon T[i+j-1]<-T2[j] j<-j+1 sinon T[i+j-1]<-T1[i] i<-i+1 sinon T[i+j-1]<-T2[j] j<-j+1 retourne T FIN
Pour la fonction de tri en elle meme, il suffit d'ajouter dans un tas vide tout les éléments du tableau un à un, et ensuite de tous les retirer un à un.
Complexite
La compléxité de la fonction fusion est en O(N) car il n'y a qu'un niveau d'imbrication de boucle. Il reste a calculer la complexite de la fonction tri_fusion, la coupe de tableau est en O(N) égalment (d'ailleurs tres facilment optimisable au moment de l'implementation). Pour le calcul de la compléxité, on pose que l'on a un nombre 2puissancek éléments, et l'on fait la somme des compléxités. On trouve que le tri_fusion est de compléxité O(N*log2(N)). Ce tri n'est par contre que peu optimisable quelque soit la tête du tableau (trié ou non), le tri coutera autant.
Ce qui coute cher dans le tri fusion est la création/destruction de nouveau tableau. Selon l'implémentation, on pourra minimiser ce coût.