Livre_silo 30 août 2013 16:32 Page 323
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
323
13 – Algorithmes de tri
• Pour trier a[4:6], on trie a[4:5] et a[5:6].
4 2
• On fusionne a[4:5] et a[5:6].
2 4
• Pour trier a[6:8], on trie a[6:7] et a[7:8].
1 8
• On fusionne a[6:7] et a[7:8].
1 8
• On fusionne a[4:6] et a[6:8].
1 2 4 8
• On fusionne a[0:4] et a[4:8].
1 2 3 4 5 6 7 8
13.3.1 Réalisation
On va chercher à réaliser le tri fusion d’un tableau en place, en délimitant la portion à
trier par deux indices g (inclus) et d (exclu). Pour le partage, il suffit de calculer l’indice
médian m =
g+d
2 . On trie alors récursivement les deux parties délimitées par g et m d’une
part, m et d d’autre part. Il reste à effectuer la fusion. Il s’avère extrêmement difficile de la
réaliser en place. Le plus simple est d’utiliser un second tableau, alloué une et une seule
fois au début du tri.
On commence par écrire la fonction fusion. Elle prend en arguments deux tableaux, a1
et a2, et les trois indices g, m et d. Les portions a1[g..m[ et a1[m..d[ sont supposées triées.
L’ objectif est de les fusionner dans a2[g..d[. Pour cela, on va parcourir les deux portions
de a1 avec deux variables i et j et la portion de a2 à remplir avec une boucle for :
def fusion(a1, a2, g, m, d):
i, j = g, m
for k in range(g, d):
À chaque itération, la situation est donc la suivante :
g
m
d
a1
trié
trié
↑ i
↑ j
a2
trié
↑ k
Il faut alors déterminer la prochaine valeur à placer en a2[k]. Il s’agit de la plus petite des
deux valeurs a1[i] et a1[j]. Il convient cependant de traiter correctement le cas où il n’y a
plus d’élément dans l’une des deux moitiés. On détermine si l’élément doit être pris dans
la moitié gauche avec le test suivant :
if i < m and (j == d or a1[i] <= a1[j]):
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
323
13 – Algorithmes de tri
• Pour trier a[4:6], on trie a[4:5] et a[5:6].
4 2
• On fusionne a[4:5] et a[5:6].
2 4
• Pour trier a[6:8], on trie a[6:7] et a[7:8].
1 8
• On fusionne a[6:7] et a[7:8].
1 8
• On fusionne a[4:6] et a[6:8].
1 2 4 8
• On fusionne a[0:4] et a[4:8].
1 2 3 4 5 6 7 8
13.3.1 Réalisation
On va chercher à réaliser le tri fusion d’un tableau en place, en délimitant la portion à
trier par deux indices g (inclus) et d (exclu). Pour le partage, il suffit de calculer l’indice
médian m =
g+d
2 . On trie alors récursivement les deux parties délimitées par g et m d’une
part, m et d d’autre part. Il reste à effectuer la fusion. Il s’avère extrêmement difficile de la
réaliser en place. Le plus simple est d’utiliser un second tableau, alloué une et une seule
fois au début du tri.
On commence par écrire la fonction fusion. Elle prend en arguments deux tableaux, a1
et a2, et les trois indices g, m et d. Les portions a1[g..m[ et a1[m..d[ sont supposées triées.
L’ objectif est de les fusionner dans a2[g..d[. Pour cela, on va parcourir les deux portions
de a1 avec deux variables i et j et la portion de a2 à remplir avec une boucle for :
def fusion(a1, a2, g, m, d):
i, j = g, m
for k in range(g, d):
À chaque itération, la situation est donc la suivante :
g
m
d
a1
trié
trié
↑ i
↑ j
a2
trié
↑ k
Il faut alors déterminer la prochaine valeur à placer en a2[k]. Il s’agit de la plus petite des
deux valeurs a1[i] et a1[j]. Il convient cependant de traiter correctement le cas où il n’y a
plus d’élément dans l’une des deux moitiés. On détermine si l’élément doit être pris dans
la moitié gauche avec le test suivant :
if i < m and (j == d or a1[i] <= a1[j]):