Livre_silo 30 août 2013 16:32 Page 325
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
325
13 – Algorithmes de tri
def tri_fusion(a):
tmp = a[:]
def tri_fusion_rec(g, d):
if g >= d-1: return
m = (g+d)//2
tri_fusion_rec(g, m)
tri_fusion_rec(m, d)
tmp[g:d] = a[g:d]
fusion(tmp, a, g, m, d)
tri_fusion_rec(0, len(a))
13.3.2 Complexité
Si on note C(N ) (resp. f (N )) le nombre total de comparaisons effectuées par tri_fusion
(resp. fusion) pour trier un tableau de longueur N , on a l’équation de récurrence suivante :
C(N ) = 2C(N/2) + f (N )
En effet, les deux appels récursifs se font sur deux segments de même longueur N/2. Dans
le meilleur des cas, la fonction fusion n’ examine que les éléments de l’un des deux segments
car ils sont tous plus petits que ceux de l’autre segment. Dans ce cas, f (N ) = N/2 et donc
C(N ) ∼
1
2 N log N . Dans le pire des cas, tous les éléments sont examinés par fusion et
donc f (N ) = N − 1, d’où C(N ) ∼ N log N .
Le nombre d’affectations est le même dans tous les cas : N affectations dans la fonction
fusion (chaque élément est copié de a1 vers a2) et N affectations effectuées par la copie
de a vers tmp. Si on note A(N ) le nombre total d’affectations pour trier un tableau de
longueur N , on a donc :
A(N ) = 2A(N/2) + 2N,
d’où un total de 2N log N affectations.
meilleur cas
moyenne
pire cas
comparaisons
1
2
N log N
N log N
N log N
affectations
2N log N
2N log N
2N log N
On note que, dans tous les cas, la complexité du tri fusion est la même. Cette complexité
est optimale.