Tri par insertion
Principe du tri par insertion
Principe du tri par insertion
En résumé :
L'opération, pour chaque position i, consiste à prendre l'éléments d'indice i (la clef) et à l'insérer à la bonne place dans le tableau des éléments d'indices 0 ài - 1. Ce processus assure que les i premiers éléments seront triés.
On pourra donc recommencer avec l'élément suivant (la clef suivante à l'indice i + 1).
Algorithme :
Pour un tableau tab de taille n
pour i allant de 1 à n-1
clef ← tab[i]
insérer la clef au bon endroit dans tab
Activité 1 - Déroulé « à la main »
Considérons la situation suivante (utiliser les onglets afin de passer d'une étape à la suivante)
On débute dans la situation où les premières cartes ont déjà été triées.
Il faut désormais placer le \(2\) convenablement.
La première étape est de mettre cette carte de côté.
On la sort du jeu.
Cette étape réalisée, on va comparer sa valeur à la carte précédente. Ici le \(8\) est strictement supérieur au \(2\).
On décale le \(8\) vers la droite :
On peut ensuite comparer le \(2\) et le \(3\).
Là encore, le \(3\) est strictement supérieur au \(2\) : on le décale vers la droite.
Le \(2\) est remonté au début du tableau, le comparer à la carte précédente n'a pas de sens.
On peut insérer le \(2\) à cette position.
À quels éléments est-il indispensable d'appliquer l'algorithme ?
- À tous les éléments
- À tous les éléments sauf le premier
- À tous les éléments sauf le dernier
- À un élément sur deux en partant du deuxième
À tous les éléments
À tous les éléments sauf le premier- À tous les éléments sauf le dernier
- À un élément sur deux en partant du deuxième
En effet, le premier élément ne peut pas être décalé car au début du tableau. Il faut par contre aborder tous les autres éléments.
Sous quelle condition peut-on décaler des éléments ?
- On décale un élément lorsque le précédent est strictement inférieur au suivant
- On décale un élément lorsque le précédent est strictement supérieur au suivant
- On ne peut pas décaler l'élément s'il est en deuxième position
- On ne peut pas décaler l'élément s'il est en première position (à gauche du tableau)
- On décale deux éléments lorsque le précédent est strictement inférieur au suivant
- On décale deux éléments lorsque le précédent est strictement supérieur au suivant
- On ne peut pas décaler l'élément si l'on est en deuxième position
- On ne peut pas décaler l'élément si l'on est en première position
La condition de décalage est double. Il faut ainsi que :
- l'élément étudié ne soit pas au début du tableau,
- l'élément précédent lui soit strictement supérieur.
Activité 2 - Algorithme du tri par insertion en Python
Avant d'écrire l'ensemble du tri, attardons nous sur les décalages de valeurs.
Contrairement à l'exemple du tri de cartes, il est impossible de « sortir un élément » du tableau. Il est néanmoins possible de stocker sa valeur dans une variable temporaire.
Les décalages vers la droite vont, quant à eux, alors dupliquer des valeurs ! Toutefois, chaque valeur dupliquée sera « écrasée » de proche en proche lors des décalages. En dernier lieu, la valeur à insérer viendra « écraser » la dernière valeur dupliquée.
L'illustration ci-dessous présente ce fonctionnement dans le cadre d'un tableau. La valeur à insérer est stockée sur la gauche.
Trier votre tableau
Avant de transcrire en Python l'algorithme, gardons à l'esprit que :
- il n'est pas indispensable d'aborder tous les éléments du tableau,
- l'élément abordé dans une itération doit être stocké dans une variable temporaire,
- la condition pour savoir s'il est possible de décaler des éléments est double,
- lors de chaque décalage, on duplique un élément.
Compléter la fonction tri_insertion prenant en argument un tableau et le triant en place à l'aide du tri par insertion.
tester le tri par insertion
Tester ci-dessous. Que s'est-il passé ?
# Tests (insensible à la casse)(Ctrl+I)
Solution
La fonction n'a pas de return, c'est une procédure. Elle renvoie donc None
Que fait la fonction de tri par insertion ?
Tester ci-dessous. Que s'est-il passé ?
# Tests (insensible à la casse)(Ctrl+I)
Solution
La liste de départ a été modifiée ...
C'est ce qu'on appelle un effet de bord. La fonction a modifié "en place" la liste.
Activité 3 - Complexité du tri par insertion
Déterminons le coût de cet algorithme.
Tri par insertion « à la main »
On considère le tableau \([6,\,1,\,4,\,5,\,2,\,3]\).
- Lors de la première itération, le \(6\) reste à sa place
- Après deux itérations, le tableau est \([1,\,4,\,6,\,5,\,2,\,3]\)
- Après trois itérations, le tableau est \([1,\,2,\,4,\,6,\,5,\,3]\)
- Au total, la valeur \(6\) sera déplacée 5 fois
- La première itération étudie la deuxième valeur, le \(1\). Le \(6\) sera donc décalé
- Oui car on a traité les valeurs \(1\) et \(4\)
- La troisième itération décale le \(5\). On obtient donc \([1,\,4,\,5,\,6,\,2,\,3]\)
- Oui car cette valeur doit être décalée à la fin du tableau
La performance du tri par insertion peut s'évaluer en nombre d'itérations élémentaires. Comme dans le cas du tri par sélection, il y a deux boucles imbriquées :
- la boucle principale est une boucle « Pour ». Elle parcourt les valeurs de la deuxième à la dernière afin de les insérer à la bonne position à leur gauche,
- chaque insertion est menée dans une seconde boucle « Tant que » qui décale la valeur vers la gauche.
À l'issue de chaque tour de la boucle principale, on a inséré un élément sur la gauche et on est certain que tous les éléments du début du tableau jusqu'à celui-ci inclus sont triés dans l'ordre croissant.
On présente ci-dessous les différentes étapes du tri. Chaque onglet correspond à une itération de la boucle principale.
Dans un tableau de \(5\) valeurs, on effectue donc \(4\) itérations de la boucle principale.
Les différentes étapes de la boucle secondaire correspondent aux illustrations présentées en haut de la page.
Combien d'itérations ? de lectures ?
On considère un tableau de \(20\) valeurs initialement trié dans l'ordre décroissant.
- La boucle principale va s'exécuter \(19\) fois
- Lors de la première itération de la boucle principale on doit lire \(1\) valeur
- La troisième itération de la boucle principale va effectuer \(3\) décalages de valeurs
- Lors de la dernière itération de la boucle principale on doit effectuer \(1\) seul décalage
- Oui car la première valeur n'est pas traitée par cette boucle
- On étudie la deuxième valeur et on la compare à la première. Il faut lire \(2\) valeurs
- On place correctement la quatrième valeur : elle remonte de trois positions. On effectue donc \(3\) décalages
- Lors de la dernière itération, la dernière valeur remonte en première position. Il faut effectuer \(19\) décalages
Complexité dans le "pire des cas?"
Solution
Le pire des cas est atteint lorsque le tableau est trié dans l'ordre décroissant. Dans ce cas, pour un tableau de \(N\) valeurs :
Dans le pire des cas :
- la boucle principale effectue \(N-1\) itérations,
- la première boucle secondaire effectue \(1\) décalage,
- la deuxième effectue \(2\) décalages,
- la troisième \(3\) décalages,
- ...
- la dernière boucle \(N - 1\) décalages.
On effectue donc au total \(1 + 2 + 3 + \dots+(N-1)\) décalages. On retrouve la somme étudiée dans cette page. Le coût de cet algorithme est donc quadratique.
Complexité dans le "meilleur des cas?"
Solution
Dans le cas où le tableau est initialement trié dans l'ordre croissant, l'algorithme n'effectuera qu'une seule comparaison et aucun échange à chaque itération de la boucle principale.
Le coût sera alors linéaire.
Activité 4 - Mesures du temps de calcul
On se place dans le pire des cas
Le pire des cas est celui où la liste est triée par ordre décroissant.
Vérifions sur une liste de taille 100000 ...
Recopier le script ci-dessous dans votre éditeur Python (pas en ligne)
Il faut attendre un peu, on trie une "grosse" liste ...
from timeit import timeit
def tri_insertion(tableau):
for i in range(1, len(tableau)):
valeur_a_inserer = tableau[i]
j = i
while j > 0 and tableau[j - 1] > valeur_a_inserer:
tableau[j] = tableau[j - 1]
j = j - 1
tableau[j] = valeur_a_inserer
liste_croiss = [i for i in range(10000)]
liste_decroiss = [i for i in range(10000,0,-1)]
t_croiss = timeit("tri_insertion(liste_croiss)", number = 1, globals = globals())
t_decroi = timeit("tri_insertion(liste_decroiss)", number = 1, globals = globals())
print("t_croiss = ",t_croiss)
print("t_decroi = ",t_decroi)
Remarque
En nous inspirant de ce qui a été fait sur les tri par sélection, nous allons comparer le temps de tri pour différentes tailles de listes
💣 Attention, il y a une difficulté supplémentaire. Le tri par insertion est beaucoup plus lent si la liste n'est pas triée.
Nous avons vu que nous mesurons le pire des cas. Or le tri par insertion est à effet de bord. Donc n'oubliez pas que si vous avez chronométré le tri d'une liste une première fois , et que vous voulez recommencer une deuxième fois, il faut le faire sur la liste originale (indication : ou une copie de celle-ci...)
regardons plus précisément
Recopier le script ci-dessous dans votre éditeur Python (pas en ligne). Que se passe-t-il ?
from timeit import timeit
def tri_insertion(tableau):
for i in range(1, len(tableau)):
valeur_a_inserer = tableau[i]
j = i
while j > 0 and tableau[j - 1] > valeur_a_inserer:
tableau[j] = tableau[j - 1]
j = j - 1
tableau[j] = valeur_a_inserer
liste_tailles = [300, 900, 2700]
liste_ref = [i for i in range(100,0,-1)] # liste [100, 99, 98, ..., 1]
# pour chronométrer les 20 fois, on reprend à chaque fois une copie de la liste de départ list(liste_ref)
tref = timeit("tri_insertion(list(liste_ref))", number = 20, globals = globals())
print("n = 100 : tref = ",tref)
for n in liste_tailles :
print("n =", n, end = '')
# Création de la liste triée par ordre décroissant de taille n : [n, n-1, ..., 1]
liste_decr = [i for i in range(n, 0, -1)]
# Temps d'éxécution du tri : il faut trier list(liste_decr) pour ne pas trier la liste déjà triée !
temps = timeit("tri_insertion(list(liste_decr))", number = 20, globals = globals())
# Affichage
print('\t-> temps = ', round(temps, 2), '\t x', round(temps/tref, 2) )
# Nouveau temps de référence avant le tour de boucle suivant
tref = temps
Solution
Lorsque la taille de la liste et multipliée par 3, la temps est multiplié par 9. Or \(3^2 = 9\)
Cela correspond bien à une complexité quadratique
Visulalisation du temps de calcul
Activité 5 - Correction de l'algorithme de tri par insertion
Prouver la correction de l'algorithme à l'aide d'un invariant de boucle.
Réponse
Après la ième itération de la boucle for (boucle en i de l’algorithme fourni) les i premiers éléments sont triés.
Cette propriété est un invariant de boucle pour le tri par insertion.
Cela se comprend aisément car dans chaque tour de boucle nous avions utilisé la fonction insere dont le rôle est de ranger les i premiers éléments de la liste par ordre croissant.
Cet invariant de boucle prouve la correction du tri par insertion.
Activité 6 - Terminaison de l'algorithme de tri par insertion
Justifier la terminaison à l'aide d'un variant de boucle.
Réponse
La procédure de tri par insertion contient une boucle while 
: est-on sûr que cette boucle va se terminer ?
Cette boucle s'arrête quand l'une des 2 conditions est fausse, donc quand :
j <= 0- ou
tableau[j - 1] <= valeur_a_inserer
Avant la boucle, j vaut i et 0 <= i <n.
Notons que si i = 0 on n'entre pas dans la boucle, elle se termine d'emblée sans commencer. La terminaison est alors évidente.
Sinon, on démarre avec j > 0, on entre donc dans la boucle.
Dans le corps de la boucle, j est décrémenté de 1.
On a donc un entier positif qui décroît strictement à chaque itération.
Donc j finira par devenir négatif si on n'a pas été stoppé avant par l'autre condition.
Ceci prouve que la boucle se termine.
j est un variant de boucle qui nous a permis de démontrer la terminaison de l'algorithme.
Ici, ce variant de boucle est une quantité qui décroît strictement et finit donc inévitablement par atteindre une valeur "plancher" qui assure la terminaison.
À retenir
- Le tri par insertion a une complexité quadratique, c'est à dire de l'ordre du carré de la taille de la liste à trier \(N^2\) : \(O(n^2)\)
def tri_insertion(tableau):
for i in range(1, len(tableau)):
valeur_a_inserer = tableau[i]
j = i
while j > 0 and tableau[j - 1] > valeur_a_inserer:
tableau[j] = tableau[j - 1]
j = j - 1
tableau[j] = valeur_a_inserer
# Tests(insensible à la casse)(Ctrl+I)