Tri par insertion

Le tri par insertion est un algorithme de tri classique dont le principe est très simple. C'est le tri que la plupart des personnes utilisent naturellement pour trier des cartes : prendre les cartes mélangées une à une sur la table, et former une main en insérant chaque carte à sa place.

En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme le tri rapide et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique.

Le tri par insertion est cependant considéré comme le tri le plus efficace sur des entrées de petite taille. Il est aussi très rapide lorsque les données sont déjà presque triées. Pour ces raisons, il est utilisé en pratique en combinaison avec d'autres méthodes comme le tri rapide (ou quicksort).

En programmation informatique, on applique le plus souvent ce tri à des tableaux. La description et l'étude de l'algorithme qui suivent se restreignent à cette version, tandis que l'adaptation à des listes est considérée plus loin.

Description de l'algorithme

Dans l'algorithme, on parcourt le tableau à trier du début à la fin. Au moment où on considère le i-ème élément, les éléments qui le précèdent sont déjà triés. Pour faire l'analogie avec l'exemple du jeu de cartes, lorsqu'on est à la i-ème étape du parcours, le i-ème élément est la carte saisie, les éléments précédents sont la main triée et les éléments suivants correspondent aux cartes encore mélangées sur la table.

L'objectif d'une étape est d'insérer le i-ème élément à sa place parmi ceux qui précèdent. Il faut pour cela trouver où l'élément doit être inséré en le comparant aux autres, puis décaler les éléments afin de pouvoir effectuer l'insertion. En pratique, ces deux actions sont fréquemment effectuées en une passe, qui consiste à faire « remonter » l'élément au fur et à mesure jusqu'à rencontrer à un élément plus petit.

Voici une description en pseudo-code de l'algorithme présenté. Les éléments du tableau T sont numérotés de 0 à n-1.

  procédure tri_insertion(tableau T, entier n)
      pour i de 1 à n - 1
          x := T[i]
          j = i
          tant que j > 0 et T[j - 1] > x
              T[j] = T[j - 1]
              j = j - 1;
          T[j] = x

Le tri par insertion est un tri stable (conservant l'ordre d'apparition des éléments égaux) et un tri en place (il n'utilise pas de tableau auxiliaire).

Exemple

Voici les étapes de l'exécution du tri par insertion sur le tableau $T=[9,6,1,4,8]$ . Le tableau est représenté au début et à la fin de chaque itération.

i=1

9	6	1	4	8

\rightarrow

6	9	1	4	8

i=2

6	9	1	4	8

\rightarrow

1	6	9	4	8

i=3

1	6	9	4	8

\rightarrow

1	4	6	9	8

i=4

1	4	6	9	8

\rightarrow

1	4	6	8	9

Complexité

La complexité du tri par insertion est Θ(n²) dans le pire cas et en moyenne, et linéaire dans le meilleur cas. Plus précisément :

Dans le pire cas, atteint lorsque le tableau est trié à l'envers, l'algorithme effectue de l'ordre de n²/2 affectations et comparaisons^[1].
Si les éléments sont distincts et que toutes leurs permutations sont équiprobables, alors en moyenne, l'algorithme effectue de l'ordre de n²/4 affectations et comparaisons^[1].
Si le tableau est déjà trié, il y a n-1 comparaisons et O(n) affectations.

La complexité du tri par insertion reste linéaire si le tableau est presque trié (par exemple, chaque élément est à une distance bornée de la position où il devrait être, ou bien tous les éléments sauf un nombre borné sont à leur place). Dans cette situation particulière, le tri par insertion surpasse d'autres méthodes de tri : par exemple, le tri fusion et le tri rapide (avec choix aléatoire du pivot) sont tous les deux en $\Theta (n\,\log n)$ même sur une liste triée.

Variantes et optimisations

Optimisations pour les tableaux

Plusieurs modifications de l'algorithme permettent de diminuer le temps d'exécution, bien que la complexité reste quadratique.

On peut optimiser ce tri en commençant par un élément au milieu de la liste puis en triant alternativement les éléments après et avant. On peut alors insérer le nouvel élément soit à la fin, soit au début des éléments triés, ce qui divise par deux le nombre moyen d'éléments décalés. Il est possible d'implémenter cette variante de sorte que le tri soit encore stable.
En utilisant une recherche par dichotomie pour trouver l'emplacement où insérer l'élément, on peut ne faire que $O(n\,\log n)$ comparaisons. Le nombre d'affectations reste en O(n²).
L'insertion d'un élément peut être effectuée par une série d'échanges plutôt que d'affectations. En pratique, cette variante peut être utile dans certains langages de programmation (par exemple C++), où l'échange de structures de données complexes est optimisé, alors que l'affectation provoque l'appel d'un constructeur de copie (en).

Le tri de Shell est une variante du tri par insertion qui améliore sa complexité asymptotique, mais n'est pas stable.

Tri par insertion sur des listes

Le principe du tri par insertion peut être adapté à des listes chaînées (une implémentation en Caml est décrite dans la section Implémentations). Dans ce cas, le déplacement de chaque élément peut se faire en temps constant (une suppression et un ajout dans la liste). Par contre, le nombre de comparaisons nécessaires pour trouver l'emplacement où insérer reste de l'ordre de n²/4, la méthode de recherche par dichotomie ne pouvant pas être appliquée à des listes.

Combinaison avec d'autres tris

En pratique, les algorithmes de tri en $O(n\,\log n)$ basés sur la méthode « diviser pour régner » (tri fusion, tri rapide) sont moins efficaces que le tri par insertion sur les petites entrées, en dessous d'une taille critique K (qui dépend de l'implémentation et de la machine utilisée). Dans ce type d'algorithmes, plutôt que de diviser récursivement l'entrée jusqu'à avoir des sous-problèmes élémentaires de taille 1 ou 2, on peut s'arrêter dès que les sous-problèmes ont une taille inférieure à K et les traiter avec le tri par insertion.

Pour le cas particulier du tri rapide, une variante plus efficace existe^[2] :

exécuter d'abord le tri rapide en ignorant simplement les sous-problèmes de taille inférieure à K ;
faire un tri par insertion sur le tableau complet à la fin, ce qui est rapide car la liste est déjà presque triée.

Implémentations

Une mise en œuvre simple du tri par insertion sur un tableau de nombres entiers en C :

#define MAX 100

void insertion(int t[MAX]) 
{
    /* Tri du tableau t par insertion séquentielle */
    int i,p,j;
    int x;
 
    for (i = 1; i < MAX; i++) 
    {
        /* Stockage de la valeur en i */
        x = t[i]; 
        
        /* Recherche du plus grand indice p inférieur à i tel que t[p] <= t[i] */
        p = i-1;
        while (t[p] > x && p-- > 0) {}

        /* Il faut insérer t[i] juste après cette case */
        p++;
 
        /* Décalage avant des valeurs de t entre p et i */         
        for (j = i-1; j >= p; j--) {
            t[j+1] = t[j]; 
        }   
        
        t[p] = x; /* Insertion de la valeur stockée à la place vacante */
    }
}

Tri par insertion en Pascal en ordre croissant.

function position (t:tab ; i : integer ): integer ; 
var 
   j : integer ; 
Begin 
 j:=0 ; 
  repeat 
   j:=j+1 ; 
  until t[j] >= t[i] ; 
 position:=j ; 
End; 
 
procedure tri(var t : tab ; n:integer ); 
var 
int,i,j,p : integer ; 
Begin 
 for i:=2 to n do 
  begin 
   p:=position(t,i); 
    if p <> i then 
     begin 
      int:=t[i] ; 
       for j :=i-1 downto p do 
        begin 
         t[j+1]:=t[j] ; 
        end; 
      t[p]:=int ; 
     end; 
  end;  
End;

Tri par insertion en utilisant des vecteurs en OCaml (en ordre décroissant).

let tri_ins t =
  let n = vect_length t and s=t  in
    for k = 1 to (n - 1) do
      let  x = t.(k) and j = ref( k - 1) in
        while ( !j >= 0 ) & ( x > s.(!j) ) do 
                           s.(!j + 1) <- t.(!j);
                           j:= !j - 1;
        done;                   
        s.( !j + 1 ) <- x;
    done;
  s;;

Tri par insertion récursif en utilisant des listes en OCaml.

 let rec insere elem = function
     [] -> [elem]
   | tete::queue ->
       if elem <= tete
       then elem::tete::queue            (* on a trouvé la place de l'élément *)
       else tete :: (insere elem queue)  (* on continue à chercher dans la queue de la liste *)
 
 let rec tri_insertion = function
     [] -> []
   | tete::queue -> insere tete (tri_insertion queue)

On remarque que les listes sont des structures de données plus simples à trier par insertion que les tableaux, parce qu'il n'y a pas besoin de "décaler les éléments".

Tri par insertion en ordre croissant en utilisant le langage Java (JDK avant la version 5.0)

public static void triParInsertion(int [] tab, int tailleLogique){
    int cpt;
    int element;
 
    for(int i = 1; i < tailleLogique ; i++)
    {    
        element = tab[i];
        cpt = i-1;
        while(cpt>=0 && tab[cpt]>element){
           tab[cpt+1] = tab[cpt];
           cpt--;
        }
        tab[cpt+1] = element;
    }
}

Tri par insertion avec le langage PHP.

function Tri_insrt($liste, $taille )
{
    for($i = 0; $i < $taille; $i++)
    {
        $element_a_inserer = $liste[$i];
        for($j = 0; $j < $i; $j++)
        {
            $element_courant = $liste[$j];
            if ($element_a_inserer < $element_courant)
            {
                $liste[$j] = $element_a_inserer;
                $element_a_inserer = $element_courant;
            }  
        }
        $liste[$i] = $element_a_inserer;
    }
}

Tri par insertion avec le langage Python.

def insertionSort(array):
    for j in range(1, len(array)):
        i = j - 1
        tmp = array[j]
        while i > -1 and array[i] > tmp:
            array[i+1] = array[i]
            i -= 1
        array[i+1] = tmp

Notes et références

↑ ^{a et b} (en) Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley 1973 (ISBN 0-201-03803-X). (section 5.2.1, p. 83)
↑ (fr) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique (2^e édition), Dunod 2004. (ISBN 2-10-003922-9). (ex. 7.4.5, p. 153)

Modèle:Algorithme de tri

[complexite-1] {a et b} (en) Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley 1973 (ISBN 0-201-03803-X). (section 5.2.1, p. 83)

[2] (fr) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique (2^e édition), Dunod 2004. (ISBN 2-10-003922-9). (ex. 7.4.5, p. 153)

[1]

[2]