II) Tri par insertion

1) Algorithme du tri par insertion

---

Pour commencer, voici une vidéo qui explique le principe du tri par insertion :

https://www.youtube.com/watch?v=bRPHvWgc6YM

On peut résumer le principe de fonctionnement de l'algorithme de tri par insertion avec le schéma suivant :

Voici l'algorithme du tri par insertion :

VARIABLE
t : tableau d'entiers
i : nombre entier
j : nombre entier
k : nombre entier
DEBUT
i←2
tant que i<=longueur(t):  
  j←i-1
  k←t[i]
  tant que j>0 et que t[j]>k: 
    t[j+1]←t[j]
    j←j-1
  fin tant que
  t[j+1]←k
  i←i+1
fin tant que
FIN

2) Complexité du tri par insertion

---

Essayons maintenant de déterminer la complexité de l'algorithme de tri par insertion :

Comme précédemment nous nous intéresserons à la complexité en temps dans le pire des cas. À quoi correspond le pire des cas pour un algorithme de tri ? Tout simplement quand le tableau initial est "trié à l'envers" (les entiers sont classés du plus grand au plus petit), comme dans cet exemple : t = [5, 4, 3, 2, 1].

Pour déterminer la complexité de l'algorithme de tri par insertion nous n'allons pas rechercher le nombre d'opérations élémentaires, mais, pour souci de simplicité, directement nous intéresser au "nombre de décalages effectués" pour trier entièrement un tableau. J'appelle "décalage" ce qui est symbolisé par une flèche noire sur le schéma ci-dessous :

Pour l'étape ci-dessus nous avons 3 décalages (décalages du 10, du 12 et du 27). Nous ne tiendrons pas compte du "placement" du nombre en cours de traitement (8 dans notre exemple) symbolisé par la flèche en pointillé.

Évaluons le nombre de décalages nécessaires pour trier le tableau t = [5, 4, 3, 2, 1]

Il est, je l'espère, évident pour vous que nous avons : $1 + 2 + 3 + 4 = 10$ décalages.

Dans le cas où nous avons un tableau à trier qui contient n éléments, nous aurons : $1 + 2 + 3 +....+ (n-3) + (n-2) + (n-1)$ décalages (puisque pour 5 éléments nous avons $1 + 2 + 3 + 4$ ). Si vous n'êtes pas convaincu, faites le test avec un tableau de 6 éléments, vous devriez trouver $1 + 2 + 3 + 4 + 5 = 15$ décalages.

Que vaut cette somme $S = 1 + 2 + 3 + .... + (n-3) + (n-2) + (n-1)$ ?

Écrivons cette somme un peu différemment : $S = (n-1) + (n-2) + (n-3) + .... + 3 + 2 + 1$.

En associant les termes de cette somme un par un nous obtenons : $S + S = n + n + n + .... + n + n + n$.

En effet :

• $1+(n-1)=n$
• $2+(n-2)=n$
• $3+(n-3)=n$
• ....
• $(n-3)+3=n$
• $(n-2)+2=n$
• $(n-1)+1=n$.

Soit $2S = n + n + n + .... + n + n + n$

Si vous comptez bien nous avons $n-1$ fois $n$, ce que l'on peut écrire : $2S = n(n−1)$.

Soit $S = \dfrac{n(n-1)}{2}$, soit $S = \dfrac{n^2-n}{2}$, soit encore $S = \dfrac{1}{2}n^2 - \dfrac{1}{2}n$.

Comme nous l'avons vu précédemment $\dfrac{1}{2}n^2 - \dfrac{1}{2}n = O(n^2)$.

L'algorithme de tri par insertion a donc une complexité en $O(n^2)$. On parle aussi de complexité quadratique.

Ce calcul est un peu complexe à comprendre, rassurez-vous, vous ne serez jamais interrogé sur cette démonstration. Vous devez juste retenir que nous avons une boucle imbriquée dans une autre boucle et que donc la complexité de l'algorithme du tri par insertion est $O(n^2)$.