Tri par insertion⚓︎
Au programme de NSI
Le tri par insertion fait partie du programme de NSI.
Dans ce cadre il est important de le comprendre et de pouvoir le rédiger.
Le tri par insertion en bref
On suppose qu'on a déjà trié les éléments à gauche d'une certaine valeur.
Pour la trier, on va la placer correctement :
- si c'est la première valeur, il n'y a rien à faire,
- sinon, on l'échange avec une valeur à gauche jusqu'à qu'elle soit bien placée.
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.
Il est important de s'attarder sur deux points :
- à quels éléments est-il indispensable d'appliquer l'algorithme ?
- sous quelle condition peut-on décaler des éléments ?
À 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 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 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.
Coût de l'algorithme⚓︎
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 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
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 :
- 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.
Dans le meilleur des cas ?
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.
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.
La fonction tri_insertion
Compléter la fonction tri_insertion prenant en argument un tableau et le triant en place à l'aide du tri par insertion.
Solution
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