CPGE OUJDA SPE
TRI FUSION
Le tri fusion est un algorithme de tri basé sur la technique algorithmique diviser pour régner. L'opération principale de l'algorithme est la fusion, qui consiste à réunir deux listes triées en une seule.
Principe :
Le principe de cet algorithme tend à adopter une formulation récursive :
ü On découpe les données à trier en deux parties plus ou moins égales
ü On trie les 2 sous-parties ainsi déterminées
ü On fusionne les deux sous-parties pour retrouver les données de départ
ü Exemple
L'implémentation de cet algorithme repose essentiellement en 2 fonctions :
Ø Fusion :Permet de fusionner deux listes triées de telle sorte que la liste résultante la soit aussi.
Ø triFusion : Une fonction récursive qui assure le découpage de la liste et l'appel de la fonction de fusion.
Ø
Ø
Ø def fusion(L1, L2):
Ø res = []
Ø ind1, ind2 = 0, 0
Ø
while
ind1 < len(L1) and ind2 < len(L2):
Ø
if
L1[ind1] <= L2[ind2]:
Ø res.append(L1[ind1])
Ø ind1 += 1
Ø else:
Ø res.append(L2[ind2])
Ø ind2 += 1
Ø if ind1!=len(L1):
Ø res+=L1[ind1:]
Ø if ind2!=len(L2):
Ø res+=L2[ind2:]
Ø return res
Ø def triFusion(ls):
Ø if len(ls) <= 1:
Ø return ls
Ø moitie = len(ls) // 2
Ø return fusion( triFusion(ls[:moitie]), triFusion(ls[moitie:]))
Autre
méthode
Fusion de deux listes – Programme
Python
Python
def fusion(T1,T2) :
if T1==[] :return T2 if T2==[] :return T1
if T1[0]<T2[0] :
return [T1[0]]+fusion(T1[1 :],T2)
else :
return [T2[0]]+fusion(T1,T2[1 :])
Tri fusion d’une liste – Programme
Python
Python
def trifusion(T) :
if len(T)<=1 : return T
T1=[T[x] for x in range(len(T)//2)] T2=[T[x] for x in range(len(T)//2,len(T))] return fusion(trifusion(T1),trifusion(T2))
Complexit´e du tri par fusion
Complexit´e temporelle Pour d´eterminer la formule de r´ecurrence qui nous donnera
la complexit´e de l’algorithme trFusion,
´etudions les trois phases de cet algorithme « di-
viser pour r´egner » :
1. Diviser : cette ´etape se r´eduit au calcul du milieu de l’intervalle [g..h]
2. R´egner : l’algorithme r´esout r´ecursivement deux sous-probl`emes de tailles respec- tives n/2.
3. Combiner : la complexit´e de cette
´etape est celle de l’algorithme de fusion qui est
de
Θ(n) pour la construction d’un tableau solution
de taille n.
Par cons´equent, la complexit´e du tri par fusion est donn´ee par la r´ecurrence :
Θ(1) si n = 1