Lycée > Premiere > NSI > Trier par insertion

Trier par insertion

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

Écrire un algorithme de tri par insertion d’un tableau de nombres.
Prouver la terminaison et la correction du tri par insertion.
Montrer que le cout du tri par insertion est quadratique.
Coder en Python l’algorithme de tri par insertion d’un tableau de nombres.

Points clés

Le tri par insertion d’un tableau consiste, au fur et à mesure du parcours de ce tableau, à insérer à sa place chaque élément dans le début déjà trié.
Le cout d’un tri par insertion est dans le pire des cas quadratique.

Pour bien comprendre

Utiliser des boucles (for et while).
Algorithmes de recherche : rechercher un extremum (terminaison, correction et cout).

1. L’algorithme de tri par insertion

a. Principe

Le tri par insertion d’un tableau de nombres de taille n consiste à le parcourir et à le trier au fur et à mesure pour que les éléments soient dans l’ordre croissant. Le tri par insertion se fait sur place. Ainsi, à l’étape k, les k–1 premiers éléments du tableau sont triés et on insère le k-ième élément à sa place parmi les k premiers éléments.

Exemple
Voici les étapes du tri par insertion de Tab=[2, 3, 1, 6, 4, 5].

Étape	Tab	Commentaire
0	[2, 3, 1, 6, 4, 5]	Le début [2] est déjà trié. Rien ne change.
1	[2, 3, 1, 6, 4, 5]	3 est déjà à sa place. Rien ne change.
2	[1, 2, 3, 6, 4, 5]	On insère 1 à sa place dans le début [2, 3].
3	[1, 2, 3, 6, 4, 5]	6 est déjà à sa place. Rien ne change.
4	[1, 2, 3, 4, 6, 5]	On insère 4 à sa place dans le début [1, 2, 3, 6].
5	[1, 2, 3, 4, 5, 6]	On insère 5 à sa place dans le début [1, 2, 3, 4, 6].

b. Algorithme et exemple

Voici ci-dessous un algorithme de tri par insertion d’un tableau de nombres Tab de taille n.

Pour i allant de 1 à n−1	i = 1, puis i = 2, puis… i = n−1
cle ← Tab[i]	On affecte à la variable cle la valeur Tab[i]. C’est elle que l’on va insérer.
j ← i−1	On affecte à j la valeur de i−1 pour commencer le parcours des éléments précédents.
Tant que j>=0 et que Tab[j]>cle	Tant que j est positif et que Tab[j] est strictement supérieur à cle (= Tab[i]),
Tab[j+1] ← Tab[j]	on décale Tab[j] au rang j+1.
j ← j−1	On décale j au rang j−1 pour s’intéresser à l’élément précédent.
Fin Tant que	Fin de la boucle « Tant que ». On a décalé tous les éléments du tableau pour insérer cle = Tab[i].
Tab[j+1] ← cle	On insère cle = Tab[i] à sa place (en sortie de boucle, sa place est j+1).
FinPour	Fin de la boucle « Pour ».

Exemple – Tri par insertion de Tab=[2, 3, 1, 6, 4, 5]

Au début, on a Tab=[2, 3, 1, 6, 4, 5]
i = 1
cle = 3
j = i − 1 = 1 − 1 = 0
cle est déjà à sa place car (Tab[j] > cle) est faux.
Tab=[2, 3, 1, 6, 4, 5]
i = 2
cle = 1
j = i − 1 = 2 − 1 = 1
Tab=[2, 3, 3, 6, 4, 5]
j = i − 1 = 1 − 1 = 0
Tab=[2, 2, 3, 6, 4, 5]
j = i − 1 = 0 − 1 = −1
On place cle à sa place car (j ≥ 0) est faux.
Tab=[1, 2, 3, 6, 4, 5]
i = 3
cle = 6
j = i − 1 = 3 − 1 = 2
On place cle à sa place car (Tab[j] > cle) est faux.
Tab=[1, 2, 3, 6, 4, 5]
i = 4
cle = 4
j = i − 1 = 4 − 1 = 3
Tab=[1, 2, 3, 6, 6, 5]
On place cle à sa place car (Tab[j] > cle) est faux.
Tab=[1, 2, 3, 4, 6, 5]
i = 5
cle = 5
j = i − 1 = 5 − 1 = 4
Tab=[1, 2, 3, 4, 6, 6]
On place cle à sa place car (Tab[j] > cle) est faux.
Tab=[1, 2, 3, 4, 5, 6]

c. Programmation en Python 3

En Python, la fonction tri_insertion(Tab) implémente le tri par insertion de Tab.

def tri_insertion(Tab):	On définit la fonction tri_insertion.
n = len(Tab)	La longueur de la table len(Tab) est affectée à la variable n.
for i in range(1, n):	Pour i allant de 1 à n−1,
cle = Tab[i]	Tab[i] est affecté à la variable cle,
j = i−1	et i−1 est affecté à la variable j.
while j >= 0 and Tab[j] > cle:	Tant que j est positif ou nul et que Tab[j] est supérieur à cle,
Tab[j+1] = Tab[j]	Tab[j] est affecté à Tab[j+1],
j = j−1	et j−1 est affecté à la variable j
Tab[j+1] = cle	cle est affecté à Tab[j+1].

2. Terminaison, correction et cout du tri par insertion

a. Terminaison

L’algorithme de la partie précédente contient deux boucles imbriquées : une boucle externe Pour et une boucle interne Tant que.

La boucle externe Pour se termine comme toutes les boucles Pour.
La boucle interne Tant que se termine car l’une de ses conditions d’exécution est j >= 0.
Or l’affectation j ← j−1 indique que j décroit strictement.
Comme j est un entier positif, j >= 0 est donc faux au bout d’un nombre fini d’itérations.

L’algorithme de tri par insertion se termine donc car les deux boucles se terminent toujours.

b. Correction

Pour l’algorithme de tri par insertion de la partie précédente, un invariant de boucle (proposition qui doit être vraie à chaque itération de l’algorithme) peut être :
P(i) : « Après la i-ème itération de la boucle Pour, dans le tableau Tab, les éléments Tab[0], Tab[1], …, Tab[i] sont triés. »

Démonstration de la correction

Initialisation : P(0) est vraie car Tab[0] est trié puisqu’il est seul.
Hypothèse : Supposons P(i) vraie (pour 0 < i < n−1).
Montrons que P(i+1) est vraie.
Si P(i) est vraie, alors les éléments Tab[0], Tab[1], …, Tab[i] sont triés dans le tableau Tab.
À la (i+1)-ième itération, on mémorise Tab[i+1] dans la variable cle, et j vaut i.
- Si Tab[j] est plus petit que cle (Tab[i], donc Tab[j+1]), cela signifie que Tab[i] n’est pas à sa place (la boucle doit continuer tant que la condition Tab[j] > cle est respectée). Donc on déplace Tab[j] à la place suivante avec l’affectation Tab[j+1] = Tab[j].
- Ensuite, on diminue j de 1 avec j = j−1.
- On compare ensuite de nouveau Tab[j] et cle.
- Ainsi, tant que cle n’est pas à sa place (la condition Tab[j] > cle est respectée), et tant que l’on n’est pas au premier élément du tableau (la condition j >= 0 est respectée), on décale les éléments vers la droite.
- En sortie de la boucle while, soit on a trouvé la place de cle et on le place avec l’affectation Tab[j+1] = cle, soit j = −1 et on place cle au début du tableau avec l’affectation Tab[j+1] = cle puisque j+1 vaut 0.
Finalement, P(i) est vraie pour i entre 0 et n−1. Comme P(n−1) est vraie, alors Tab[0], Tab[1], …, Tab[n−1] sont triés. C’est pourquoi Tab est trié.
L’algorithme fait bien ce que l’on veut.

c. Cout

Le cout d’un algorithme de tri par insertion dépend de la taille n du tableau et de sa nature : si le tableau est déjà trié (ou partiellement trié), le cout est en effet beaucoup moins important que si le tableau est trié dans l’ordre décroissant.

On s’intéresse ici au pire des cas, où le tri du tableau n’a pas encore débuté.

L’algorithme de tri par insertion contient deux boucles imbriquées. Ainsi, pour un tableau de taille n,

la boucle externe Pour exécute n−1 instructions car for i in range(1, n) correspond à n−1 itérations ;
pour chaque valeur de i de la boucle externe, le nombre d’instructions exécutées par la boucle Tant que dépend du tableau utilisé. Toutefois, dans le pire des cas, si l’affectation j = j−1 est réalisée jusqu’à ce que le booléen j >= 0 soit faux, il y aura i instructions (j prenant les valeurs de i−1 à −1).