Fiche de cours

Trier par insertion

Lycée > Premiere > NSI > Trier par insertion

Fiche de cours
Quiz et exercices
Vidéos et podcasts

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).

Finalement, dans le pire des cas, il y aura 1 + 2 + 3 + 4 + … + n−1 instructions.

On admet la relation suivante :
.

Comme le terme dominant du cout est n², on dit que le cout est quadratique.

À retenir
Le cout du tri par insertion est dans le pire des cas quadratique.

Évalue ce cours !

Note 4.5 / 5. Nombre de vote(s) : 18

Des quiz et exercices pour mieux assimiler sa leçon

La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.

S’abonner

Des exercices variés pour ne pas s’ennuyer

Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !

Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.

S’abonner

Des quiz pour une évaluation en direct

Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.

myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.

S’abonner

Des vidéos et des podcasts pour apprendre différemment

Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.

Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !

S’abonner

Des podcasts pour les révisions

La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.

Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.

S’abonner

Des vidéos de cours pour comprendre en image

Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !

S’abonner

Profs en ligne

Découvrez le soutien scolaire en ligne avec myMaxicours

Plongez dans l'univers de myMaxicours et découvrez une approche innovante du soutien scolaire en ligne, conçue pour captiver et éduquer les élèves de CP à la terminale. Notre plateforme se distingue par une riche sélection de contenus interactifs et ludiques, élaborés pour stimuler la concentration et la motivation à travers des parcours d'apprentissage adaptés à chaque tranche d'âge. Chez myMaxicours, nous croyons en une éducation où chaque élève trouve sa place, progresse à son rythme et développe sa confiance en soi dans un environnement bienveillant.

Profitez d'un accès direct à nos Profs en ligne pour une assistance personnalisée, ou explorez nos exercices et corrigés pour renforcer vos connaissances. Notre assistance scolaire en ligne est conçue pour vous accompagner à chaque étape de votre parcours éducatif, tandis que nos vidéos et fiches de cours offrent des explications claires et concises sur une multitude de sujets. Avec myMaxicours, avancez sereinement sur le chemin de la réussite scolaire, armé des meilleurs outils et du soutien de professionnels dédiés à votre épanouissement académique.

EXERCE-TOI EN T'ABONNANT