Tri par insertion

Attention ! cette page va être migrée vers https://lwh-21.github.io/Algos/

Le tri par insertion

C'est le tri du joueur de cartes. On fait comme si les éléments à trier étaient donnés un par un, le premier élément constituant, à lui tout seul, une liste triée de longueur 1. On range ensuite le second élément pour constituer une liste triée de longueur 2, puis on range le troisième élément pour avoir une liste triée de longueur 3 et ainsi de suite...

Le principe du tri par insertion est donc d'insérer à la nième itération le nième élément à la bonne place.

L'animation ci-après illustre le fonctionnement de ce tri :

Démonstration du tri par insertion

  1. PROCEDURE tri_Insertion ( Tableau a[1:n])
  2.     POUR i VARIANT DE 2 A n FAIRE
  3.         INSERER a[i] à sa place dans a[1:i-1];
  4. FIN PROCEDURE;
  1. let tri_insertion tableau =
  2.     for i = 1 to 19 do     
  3.         let en_cours = tableau.(i) and j = ref (i - 1) in
  4.             (* Décalage des éléments du tableau *)
  5.             while (!j>=0) && (tableau.(!j)>en_cours) do            
  6.                 tableau.(!j + 1) <-  tableau.(!j);    
  7.                 j := !j - 1;
  8.             done;
  9.             (* on insère l'élément à sa place *)
  10.             tableau.(!j + 1) <- en_cours;
  11.     done;
  12. tableau;;
  1. type tab = array[1..20] of integer;
  2. procedure tri_insertion(var tableau : tab);
  3. var i, j, en_cours : integer;
  4. begin
  5.     for i:=2 to 20 do
  6.     begin
  7.         en_cours := tableau[i]; j := i - 1;  
  8.         {décalage des éléments du tableau }
  9.         while (j > 0) and (tableau[j] > en_cours) do
  10.         begin
  11.             tableau[j + 1] :=  tableau[j];              
  12.             j := j - 1;
  13.         end;
  14.         {on insère l'élément à sa place }
  15.         tableau[j + 1] := en_cours;
  16.     end;
  17. end
  1. def tri_insertion(tableau):
  2.     for i in range(1,len(tableau)):
  3.         en_cours = tableau[i]
  4.         j = i
  5.         #décalage des éléments du tableau }
  6.         while j>0 and tableau[j-1]>en_cours:
  7.             tableau[j]=tableau[j-1]
  8.             j = j-1
  9.         #on insère l'élément à sa place
  10.         tableau[j]=en_cours
  1. void tri_insertion(int* t)
  2. {
  3.     int i, j;
  4.     int en_cours;
  5.  
  6.     for (i = 1; i < 20; i++) {
  7.         en_cours = t[i];
  8.         for (j = i; j > 0 && t[j - 1] > en_cours; j--) {
  9.             t[j] = t[j - 1];
  10.         }
  11.         t[j] = en_cours;
  12.     }
  13. }

Si on utilise le tri par insertion pour résoudre le petit jeu de la page précédente, on a :



 


Les graphiques ci-dessous montrent la progression du nombre d'opérations en fonction du nombre d'éléments à trier.

Complexité du tri par insertion

Dans le meilleur des cas, avec des données déjà triées, l'algorithme effectura seulement n comparaisons. Sa complexité dans le meilleur des cas est donc en Θ(n).

Complexite du tri par insertion dans le meilleur des cas Nombre d'opérations Nombre d'elements à trier Θ(n)

Dans le pire des cas, avec des données triées à l'envers, les parcours successifs du tableau imposent d'effectuer (n-1)+(n-2)+(n-3)..+1 comparaisons et échanges, soit (n2-n)/2. On a donc une complexité dans le pire des cas du tri par insertion en Θ(n2).

Complexite du tri par insertion dans le pire des cas Nombre d'opérations Nombre d'elements à trier Θ(n2)

Si tous les éléments de la série à trier sont distincts et que toutes leurs permutations sont équiprobables, la complexité en moyenne de l'algorithme est de l'ordre de (n2-n)/4 comparaisons et échanges. La complexité en moyenne du tri par insertion est donc également en Θ(n2)

Complexite du tri par insertion en moyenne Nombre d'opérations Nombre d'elements à trier Θ(n2)

On notera également une propriété importante du tri par insertion : contrairement à celle d'autres méthodes, son efficacité est meilleure si le tableau initial possède un certain ordre. L'algorithme tirera en effet parti de tout ordre partiel présent dans le tableau. Jointe à la simplicité de l'algorithme, cette propriété le désigne tout naturellement pour "finir le travail" de méthodes plus ambitieuses comme le tri rapide

Suivant : algorithme du tri par sélection