Livre_silo 30 août 2013 16:32 Page 324
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
324
Informatique pour tous
Dans les deux cas, on copie l’élément dans a2[k] et on incrémente l’indice correspondant.
a2[k] = a1[i]
i = i+1
else:
a2[k] = a1[j]
j = j+1
On écrit ensuite la fonction tri_fusion. On commence par allouer un tableau temporaire
tmp en faisant une copie du tableau à trier :
def tri_fusion(a):
tmp = a[:]
La partie récursive du tri fusion est matérialisée par une fonction récursive locale
tri_fusion_rec qui prend en arguments les indices g et d délimitant la portion à trier :
def tri_fusion_rec(g, d):
Si le segment contient au plus un élément, c’est-à-dire si g ⩾ d − 1, il n’y a rien à faire :
if g >= d-1: return
Sinon, on partage l’intervalle en deux moitiés égales : on calcule l’élément médian m, puis
on trie récursivement a[g..m[ et a[m..d[ :
m = (g+d)//2
tri_fusion_rec(g, m)
tri_fusion_rec(m, d)
Il reste à effectuer la fusion. Pour cela, on copie toute la portion a[g..d[ dans le tableau tmp,
puis on appelle la fonction fusion, qui fusionne le tout dans a :
tmp[g:d] = a[g:d]
fusion(tmp, a, g, m, d)
Enfin, on trie le tableau a tout entier en appelant tri_fusion_rec sur la totalité de ses éléments :
tri_fusion_rec(0, len(a))
Le code complet est donné ci-après.
PROGRAMME 18 Tri fusion
def fusion(a1, a2, g, m, d):
i, j = g, m
for k in range(g, d):
if i < m and (j == d or a1[i] <= a1[j]):
a2[k] = a1[i]
i = i+1
else:
a2[k] = a1[j]
j = j+1
¯