4. Tri par insertion
C'est un tri en général un peu plus coûteux en particulier en nombre de transfert à effectuer qu'un tri par sélection cf. complexité.
4.1. Spécification abstraite
Son principe est de parcourir la liste non triée (a1, a2, ... , an) en la décomposant en deux parties une partie t déjà triée et une partie non triée. La méthode est identique à celle que l'on utilise pour ranger des cartes que l'on tient dans sa main : on insère dans le paquet de cartes déjà rangées une nouvelle carte au bon endroit. L'opération de base consiste à prendre l'élément frontière dans la partie non triée, puis à l'insérer à sa place dans la partie triée (place que l'on recherchera séquentiellement), puis à déplacer la frontière d'une position vers la droite. Ces insertions s'effectuent tant qu'il reste un élément à ranger dans la partie non triée.. L'insertion de l'élément frontière est effectuée par décalages successifs d'une cellule.
La liste (a1, a2, ... , an) est décomposée en deux parties : une partie triée (a1, a2, ... , ak) et une partie non-triée (ak+1, ak+2, ... , an); l'élément ak+1 est appelé élément frontière (c'est le premier élément non trié).
4.2. Spécification concrète itérative
La suite (a1, a2, ... , an) est rangée dans un tableau T[...] en mémoire centrale. Le tableau contient une partie triée ((a1, a2, ... , ak) en violet à gauche) et une partie non triée ((ak+1, ak+2, ... , an) en blanc à droite).
En faisant varier j de k jusqu'à 2 , afin de balayer toute la partie (a1, a2, ... , ak) déjà rangée, on décale d'une place les éléments plus grands que l'élément frontière :
tantque aj-1 > ak+1 faire
décaler aj-1 en aj ;
passer au j précédent
ftant
La boucle s'arrête lorsque aj-1 < ak+1, ce qui veut dire que l'on vient de trouver au rang j-1 un élément aj-1 plus petit que l'élément frontière ak+1, donc ak+1 doit être placé au rang j.
4.3. Algorithme
|
Algorithme Tri_Insertion |
Sans la sentinelle en T[0] nous aurions une comparaison sur j à l'intérieur de la boucle :
Tantque Tab[ j-1 ] > v faire//on travaille sur la partie déjà triée (a1, a2, ... , ai)
Tab[ j ] <- Tab[ j-1 ]; // on décale l'élément
j <- j-1; // on passe au rang précédent
si j = 0 alors Sortir de la boucle fsi
FinTant ;
4.4. Complexité
Choisissons comme opération élémentaire la comparaison de deux cellules du tableau. |
Dans le pire des cas le nombre de comparaisons "Tantque Tab[ j-1 ] > v faire" est une valeur qui ne dépend que de la longueur i de la partie (a1, a2, ... , ai) déjà rangée. Il y a donc au pire i comparaisons pour chaque i variant de 2 à n :
La complexité au pire en nombre de comparaison est donc égale à la somme des n termes suivants (i = 2, i = 3,.... i = n)
C = 2 + 3 + 4 +...+ n = n(n+1)/2 -1 comparaisons au maximum. (c'est la somme des n premiers entiers moins 1).
La complexité au pire en nombre de comparaison est de de l'ordre de n², que l'on écrit O(n²).
Choisissons maintenant comme opération élémentaire le transfert d'une cellule du tableau. |
Calculons par dénombrement du nombre de transferts dans le pire des cas. Il y a autant de transferts dans la boucle "Tantque Tab[ j-1 ] > v faire" qu'il y a de comparaisons il faut ajouter 2 transferts par boucle "pour i de 2 jusqu’à n faire", soit au total dans le pire des cas :
C = n(n+1)/2 + 2(n-1) = (n² + 5n - 4)/2
La complexité au pire en nombre de transferts est de l'ordre de n², que l'on écrit O(n²).