Livre_silo 30 août 2013 16:32 Page 316
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
316
Informatique pour tous
Dans tout ce chapitre, on suppose que les éléments à trier sont des entiers, mais les algorithmes présentés sont valables pour n’importe quel type d’éléments, pourvu qu’il soit
muni d’un ordre total. On suppose qu’on trie des tableaux, dans l’ordre croissant. On note
N le nombre d’éléments à trier.
Pour chaque tri présenté, on indique sa complexité en nombre de comparaisons et d’affectations effectuées, dans le meilleur et dans le pire des cas. La complexité en moyenne est
également donnée, à titre de comparaison, mais son calcul n’est pas détaillé (la complexité
en moyenne n’ est pas au programme). Il est bon de savoir que la complexité optimale d’un
tri effectuant uniquement des comparaisons d’éléments est en O(N log N ). On en trouvera une démonstration à la fin du chapitre.
13.1 Tri par insertion
Le tri par insertion est sans doute le plus naturel. Il consiste à insérer successivement
chaque élément dans l’ensemble des éléments déjà triés. C’est souvent ce que l’on fait quand
on trie un jeu de cartes ou un paquet de copies.
Le tri par insertion d’un tableau a s’effectue en place, c’est-à-dire qu’il ne demande pas
d’autre tableau que celui que l’on trie. Son coût en mémoire est donc constant si on ne
compte pas la place occupée par les données. Il consiste à insérer successivement chaque
élément a[i] dans la portion du tableau a[0:i] déjà triée. Illustrons cette idée sur un tableau
de cinq entiers contenant initialement [5,2,3,1,4]. Au départ, a[0:1] = 5 est déjà trié.
On insère 2 dans a[0:1].
5 2 3 1 4
On insère 3 dans a[0:2].
2 5 3 1 4
On insère 1 dans a[0:3].
2 3 5 1 4
On insère 4 dans a[0:4].
1 2 3 5 4
1 2 3 4 5
13.1.1 Réalisation
De manière générale, chaque étape du tri par insertion correspond à la situation suivante :
0
i-1
. . . déjà trié . . . a[i] . . . à trier . . .
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
316
Informatique pour tous
Dans tout ce chapitre, on suppose que les éléments à trier sont des entiers, mais les algorithmes présentés sont valables pour n’importe quel type d’éléments, pourvu qu’il soit
muni d’un ordre total. On suppose qu’on trie des tableaux, dans l’ordre croissant. On note
N le nombre d’éléments à trier.
Pour chaque tri présenté, on indique sa complexité en nombre de comparaisons et d’affectations effectuées, dans le meilleur et dans le pire des cas. La complexité en moyenne est
également donnée, à titre de comparaison, mais son calcul n’est pas détaillé (la complexité
en moyenne n’ est pas au programme). Il est bon de savoir que la complexité optimale d’un
tri effectuant uniquement des comparaisons d’éléments est en O(N log N ). On en trouvera une démonstration à la fin du chapitre.
13.1 Tri par insertion
Le tri par insertion est sans doute le plus naturel. Il consiste à insérer successivement
chaque élément dans l’ensemble des éléments déjà triés. C’est souvent ce que l’on fait quand
on trie un jeu de cartes ou un paquet de copies.
Le tri par insertion d’un tableau a s’effectue en place, c’est-à-dire qu’il ne demande pas
d’autre tableau que celui que l’on trie. Son coût en mémoire est donc constant si on ne
compte pas la place occupée par les données. Il consiste à insérer successivement chaque
élément a[i] dans la portion du tableau a[0:i] déjà triée. Illustrons cette idée sur un tableau
de cinq entiers contenant initialement [5,2,3,1,4]. Au départ, a[0:1] = 5 est déjà trié.
On insère 2 dans a[0:1].
5 2 3 1 4
On insère 3 dans a[0:2].
2 5 3 1 4
On insère 1 dans a[0:3].
2 3 5 1 4
On insère 4 dans a[0:4].
1 2 3 5 4
1 2 3 4 5
13.1.1 Réalisation
De manière générale, chaque étape du tri par insertion correspond à la situation suivante :
0
i-1
. . . déjà trié . . . a[i] . . . à trier . . .