Tri par insertion

Tri par insertion

Tri par insertion

Il existe plusieurs tris différents : le tri par insertion en est un exemple. 
On dispose de $n$ données à trier. Le principe de l’algorithme de tri est qu’à chaque étape, on suppose que les $k$ premières données sont triées et on place la $(k + 1)$-ième à sa juste place parmi les $k$ premières valeurs. On itère ensuite ce processus à l’ensemble de la liste.

On doit trier une liste de $n$ éléments. On donne l’algorithme ci dessous. 

for $i$ from $0$ to $n-2$
  $k  leftarrow i + 1$
  $new leftarrow L[k]$
  while $new < L[k-1]$ and $k > 0$
    $L[k] leftarrow L[k-1]$
    $k leftarrow k-1$
  $L[k] leftarrow new$

$new$ correspond à l’élément que l’on souhaite place lors de la $i$ème itération. On appelle aussi cet élément la clé. 
La condition $k > 0$ permet d’éviter de sortir de la liste à gauche. 

Afin d’améliorer la compréhension de l’algorithme, on propose une version littérale de l’algorithme. 
Pour chaque valeur de $i$ variant de $0$ à $n-2$, on travaille sur la liste $L[0:i+1]$ pour placer $L[i+1]$ à sa juste place.

Pour ce faire, on compare $new$ aux données précédentes, en commençant par la donnée d’indice $i$. On remonte la liste jusqu’à trouver la bonne place entre deux données successives, l’une plus petite, l’autre plus grande. L’élément à trier peut être placé en début de liste. 

On s’intéresse à présent sur la terminaison de cet algorithme, afin de savoir si il n’existe pas de situation pour laquelle l’algorithme ne se terminerait pas.
On remarque pour cela que l’algorithme est constitué de deux boucles. 
La première est la boucle for dont le nombre de passage est fini et fixé : il y en a $n-1$. 
La deuxième boucle est une boucle interne while. Les valeurs prises par l’indice variant $k$ constituent une suite d’entiers strictement décroissante, incluse dans la suite $i+1, i,…, 2, 1$.

L’algorithme peut sortir de la boucle avant que $k$ n’atteigne la valeur $1$, dans le cas où l’élément n’est pas placé en première position. Il y a donc au plus $i+1$ passages. On vient donc de vérifier la terminaison de cet algorithme. 

Un des autres aspects qu’il faut regarder en écrivant un algorithme est son coût. On distingue ici deux cas.

Le premier cas est celui d’une liste déjà triée dans l’ordre croissant. Dans ce cas, $i$ prend $n-1$ valeurs et il n’y a qu’une seule comparaison dans la boucle while : le coût dans ce cas est donc de $n$. C’est un coût linéaire. 

Le deuxième cas correspond au cas où la liste est triée dans l’ordre décroissant. $i$ prend à nouveau $n-1$ valeurs mais pour chaque valeur de $i$,  il y a $i+1$ comparaison car on place à chaque fois l’élément en première position. Au total, il y a donc $1 + 2 + … + (n-1)$ comparaisons, soit pour de grandes valeurs de $n$ un coût comparable à $n^2$. 

Cet algorithme est donc couteux lorsque la liste est mal triée.

A l’inverse, pour des listes relativement bien triées, cet algorithme est particulièrement efficace.