57
© Dunod – Toute reproduction non autorisée est un délit.
Exercices
EXERCICES
*2.1 Le tri par transpositions et sa complexité
On veut trier, par ordre croissant, n nombres rangés dans un tableau (à une seule
ligne, ou « vecteur »), par transpositions successives. Par exemple pour trier :
5
1
2
3
4
4
9
1 , on opère comme suit :
5
4
9
1
4
5
9
1
5 . 4 : on les transpose
5 , 9 : on ne les transpose pas
4
5
9
1
4
5
1
9
9 . 1 : on les transpose
fin de la 1
ère
phase
En fin de la 1
ère
phase, le nombre le plus grand (ici 9) est à sa place définitive : la
case n. Puis on entreprend une seconde phase avec les n 2 1 nombres des cases 1 à
n 2 1 (ici n 2 1 5 3) :
4
5
1
4
5
1
4
1
5
4 , 5 : on ne transpose pas
5 . 1 : on les transpose
En fin de seconde phase, le second plus grand nombre est à sa place. Ici, il n’y a
que 3 phases (n 2 1 5 3)
4
1
1
4
4 . 1 : on transpose
FIN.
Ce tableau trié par ordre croissant est donc :
1
4
5
9
1) Évaluer le nombre de comparaisons entre deux nombres effectuées dans
l’exemple. Puis donner la complexité de ce tri, avec n nombres.
2) Écrire une procédure générale pour le tri par transpositions de n nombres.