58
**2.2 Complexité du tri par fusion
Considérons 2 tableaux T1 et T 2 comportant n 1 et n 2 éléments, respectivement. Les
éléments des deux tableaux sont déjà triés, suivant un ordre croissant par exemple.
L’objectif est de fusionner ces deux tableaux en un tableau T unique contenant les
n 5 n 1 1 n 2 éléments de T1 et T 2, T devant être lui aussi trié suivant le même ordre
croissant.
Considérons l’algorithme suivant effectuant la fusion de T1 et T 2 (par la suite,
nous noterons T 5 T1 { T 2 le résultat de cette opération) :
1. i 1 d 1 ; i 2 d 1 ; i d 1 ;
2. Tant que i 1 < n 1 et i 2 < n 2
3. si T11 i 1 2 < T 21 i 2 2 alors : T(i) d T1(i 1 ) ; i 1 d i 1 1 1
4. sinon : T(i) d T 2(i 2 ) ; i 2 d i 2 1 1
5. i d i 1 1
6. si i 1 < n 1 alors tant que i 1 < n 1 : T(i) d T1(i 1 ) ; i 1 d i 1 1 1 ; i d i 1 1
7. sinon tant que i 2 < n 2 : T(i) d T 2(i 2 ) ; i 2 d i 2 1 1 ; i d i 1 1
1) Appliquer cet algorithme aux tableaux suivants :
T 1
T 2
4
1
3
9
6
7
5
2
8
2) Après avoir montré que l’algorithme effectue correctement la fusion de deux
tableaux triés en un seul, montrer que la complexité dans le pire des cas de cet algorithme est O(n). Quelles sont les complexités dans le meilleur des cas et dans le cas
moyen ?
Considérons maintenant un tableau T contenant n éléments. L’objectif est de trier
les éléments de T suivant un ordre croissant par exemple.
Si n > 2, nous notons m 5 j
n
2
k (l’arrondi par défaut de
n
2
).
Nous désignons par T gauche la première moitié de T (c’est-à-dire le tableau constitué des éléments T 1 12 , c , T 1 m 2 2 , et par T droite la seconde moitié de T (le tableau
constitué des éléments T 1 m 1 12 , c , T 1 n 2 ).
Considérons l’algorithme Tri(T) suivant :
1. Tri(T)
2. si n > 2 alors T d Tri 1 T gauche 2 { Tri 1 T droite 2
3. sinon Tri 1 T 2 d T
3) Montrer que la complexité de l’algorithme est O1 n log n2 .
Chapitre 2 • Notions de complexité