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
 local:   i , j , n, v sont des  Entiers naturels
 Entrée : Tab est  Tableau d'Entiers naturels de 0 à n éléments
 Sortie : Tab est Tableau d'Entiers naturels de 0 à n éléments
dans la cellule de rang 0 se trouve une sentinelle chargée d'éviter de tester dans la boucle tantque .. faire si l'indice j n'est pas inférieur à 1, elle aura une valeur inférieure à toute valeur possible de la liste
}
début
pour i de jusqu’à faire// la partie non encore triée (ai, ai+1, ... , an)
     v <- Tab[ i ] ;  // l'élément frontière : ai
     j <- i ;        // le rang de l'élément frontière
      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 
      FinTant ;
      Tab[ j ]  <- v //on recopie ai dans la place libérée
  fpour
Fin 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 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 jusqu’à 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²).

آخر تعديل: Sunday, 7 February 2021, 11:24 AM