2BCPST1 Algorithmes de tri : Tri par insertion Informatique - Lycée Thiers

Après le tri à bulle étudions un autre algorithme de tri : le tri par insertion. 3 2 1 5 6 4 Tableau à trier
C’est celui qu’on utilise habituellement pour trier un paquet de carte. On démontre 3 2 1 5 6 4 Premier élément
que c’est le plus raide pour trier une faible nombre de données. 3 2 1 5 6 4 Deuxième élément
2 3 1 5 6 4 Inséré dans le tableau trié
2 3 1 5 6 4 Troisième élément
2 1 3 5 6 4 Inséré dans le tableau trié
1 2 3 5 6 4 ⋮
2 Tri par insertion 1 2 3 5 6 4 Quatrième élément
1 2 3 5 6 4 Inséré dans le tableau trié
2.1 Principe 1 2 3 5 6 4 Cinquième élément
1 2 3 5 6 4 Inséré dans le tableau trié
Etudions un autre algorithme de tri : le Tri par insertion. C’est celui que l’on 1 2 3 5 6 4 Dernier élément
utilise habituellement dans la vie courante, par exemple, pour trier un paquet de 1 2 3 5 4 6 Inséré dans le tableau trié
carte : 1 2 3 4 5 6 ⋮
1 2 3 4 5 6 Tableau trié.
On constitue (imaginairement) 2 tas :

– l’un dans la main droite, contenant toutes les cartes avant tri,

– l’autre dans la main gauche, contenant les cartes déjà triées,

2.3 Tri par insertion - Algorithme

Initialement la main gauche est vide. Le tri peut s’opérer directement sur le tableau passé en paramètre : on parle de
Tri en place.
Chaque étape consiste à :
En pseudo-code, l’algorithme de Tri par insertion s’écrit :
– prendre la première carte du tas non trié (on prend pour convention que les éléments du tableau sont indicés à partir de 0,
et donc jusqu’à longueur(tableau) - 1.)
– L’insérer progressivement à sa bonne place dans le tas trié, en la faisant des-
cendre d’une position tant que sa valeur reste inférieure à celle de la carte Tri Par insertion(T) # T est le tableau à trier
située en dessous-d’elle. N = longueur(T) # N = longueur du tableau
# Balayage du tableau du 2ème jusqu’au dernier élément :
Pour i variant de 1 à N-1:
Après chaque étape le tas non trié contient une carte de moins, le tas trié une carte
x = T[i] # C’est l’élément à insérer
de plus.
k = i # k est son indice
A la fin du tri la main droite est vide. La main gauche contient toutes les cartes, # Insertion dans la partie triée :
triées. Tant que k > 0 et T[k-1] > x:
# Décalage d’un cran sur la gauche :
T[k] = T[k-1]
k = k-1
2.2 Tri par insertion - exemple T[k] = x

● Code de couleurs :

– En noir : Partie du tableau, non triée,

2.4 Tri par insertion - Code
– En bleu : Partie du tableau triée,

– En rouge : Elément à insérer dans la partie triée. En python :

page 1
2BCPST1 Algorithmes de tri : Tri par insertion Informatique - Lycée Thiers

def tri insertion(T): # T est le tableau à trier – Dans le pire des cas : le cas d’un tableau ordonné dans le sens décroissant :
N = len(T) # N = longueur du tableau
Par exemple : N (N − 1) ⋯ 2 1
# Balayage du tableau du 2eme jusqu’au dernier élément:
for i in range(1,N): Lors de la i-ème insertion l’élément doit être inséré en tout début de tableau :
x = T[i] # C’est l’élément à insérer la boucle while s’exécute i − 1 fois ; de l’ordre exactement de i opérations
k = i # k est son indice pour l’insertion du i-ème élément. La complexité est exactement d’ordre :
# Insertion dans la partie triée :
while k > 0 and T[k-1] > x:
N −1
# Décalage d’un cran sur la gauche : ∑ i = Θ(N )
2
(quadratique)
T[k] = T[k-1] i=1
k = k-1
T[k] = x
return T # Si l’on souhaite retourner le résultat – Dans le meilleur des cas : le cas d’un tableau ordonné dans le sens croissant :
Correction de l’algorithme. Considérer comme invariant de boucle : Par exemple : 1 2 ⋯ (N − 1) N
”Après le k-ième balayage les k premiers éléments du tableau sont ordonnés dans
Lors de la i-ème insertion l’élément est déjà à la bonne place : la boucle
le sens croissant. ”
while ne s’exécute pas ; de l’ordre d’1 opérations pour chaque insertion. La
(par récurrence sur k). complexité est exactement d’ordre :

2.5 Tri par insertion : complexité (N − 1) × 1 = Θ(N ) (linéaire)

● Déterminons le nombre d’opérations élémentaires dans le pire et le meilleur
des cas en fonction de la taille N du tableau à trier.
– 1 opération élémentaire pour retourner N = len(T) Ainsi :

– puis on répète N-1 fois ce qui est dans la boucle for : 1. Le tri par insertion est un tri en place : sa complexité en espace mémoire est
– 1 opération pour x = T[i] (lecture dans un tableau et affectation) en O(1).
– 1 opération pour l’affectation k = i 2. Le tri par insertion a une complexité (temporellle) :
– 1 à 2 opérations pour tester la condition du while
(a) linéaire dans le meilleur des cas (i.e. le cas d’un tableau déjà trié).
– au plus N-1 décalages dans la boucle while :
– 3 opérations (accès en lecture/écriture et décrémentation). (b) quadratique dans le pires des cas (ce n’est pas un très bon algorithme de
tri pour un grand nombre de données).
● La complexité de l’algorithme est donc :
– Dans le pire des cas majorée par l’ordre de : 3. Cependant on démontre que dans le cas d’un petit nombre d’éléments à trier
(inférieur à ...) c’est le plus rapide en moyenne.
(N − 1) × (N − 1) = Θ(N 2 ) (quadratique)
´¹¹ ¹ ¹ ¹ ¹ ¸¹¹ ¹ ¹ ¹ ¹ ¶ ´¹¹ ¹ ¹ ¹ ¹ ¸¹¹ ¹ ¹ ¹ ¹ ¶ 4. Il est également très efficace lorsque le tableau est déjà presque trié. Par
for while
exemple la complexité est linéaire si de plus tous les éléments sont à une
– Dans le meilleur des cas minorée par l’ordre de : distance uniformément bornée (ne dépendant pas de N ) de leur position
finale. Ou lorsque le nombre d’éléments qui ne sont à la bonne place est
(N − 1) × 1 = Θ(N ) (linéaire) uniformément borné.
®
´¹¹ ¹ ¹ ¹ ¹ ¸¹¹ ¹ ¹ ¹ ¹ ¶ while
for
Conclusion : continuons à l’utiliser pour trier un paquet de carte (c’est le meilleur
● Montrons que ces bornes sont atteintes : possible), mais nous allons voir que lorsque le nombre d’éléments à trier devient
grand, ce n’est plus celui à utiliser sur de grands tableaux très ”désordonnés”.

page 2
2BCPST1 Algorithmes de tri : Tri par insertion Informatique - Lycée Thiers

2.6 Tri par insertion - Exemples Cas d’une liste ordonnée dans le sens décroissant :
In [2]: tri insertion([6,5,4,3,2,1])
Modifions le code pour afficher les états intermédiaires et les insertions : [6, 5, 4, 3, 2, 1]
def tri insertion(T): # T est le tableau à trier Insertion de 5 d’indice 1
[5, 6, 4, 3, 2, 1]
N = len(T) # N = longueur du tableau Insertion de 4 d’indice 2
print(T) # Affichage initial [5, 4, 6, 3, 2, 1]
[4, 5, 6, 3, 2, 1]
# Balayage du tableau du 2eme jusqu’au dernier élément: Insertion de 3 d’indice 3
for i in range(1,N): [4, 5, 3, 6, 2, 1]
x = T[i] # C’est l’élément à insérer [4, 3, 5, 6, 2, 1]
[3, 4, 5, 6, 2, 1]
k = i # k est son indice Insertion de 2 d’indice 4
print(”Insertion de”, T[i], ”d’indice”, i) # Annonce d’insertion [3, 4, 5, 2, 6, 1]
# Insertion dans la partie triée : [3, 4, 2, 5, 6, 1]
[3, 2, 4, 5, 6, 1]
while k > 0 and T[k-1] > x: [2, 3, 4, 5, 6, 1]
# Décalage d’un cran sur la gauche : Insertion de 1 d’indice 5
[2, 3, 4, 5, 1, 6]
T[k] = T[k-1] [2, 3, 4, 1, 5, 6]
T[k-1] = x [2, 3, 1, 4, 5, 6]
k = k-1 [2, 1, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
print(T) # Affichage insertion Out[2]: [1, 2, 3, 4, 5, 6]
return T # Si l’on souhaite retourner le résultat
● Sur une liste déjà triée :
In [1]: tri insertion([3,2,5,1,6,4])
[3, 2, 5, 1, 6, 4] In[3]: tri insertion([1,2,3,4,5,6])
Insertion de 2 d’indice 1 [1, 2, 3, 4, 5, 6]
[2, 3, 5, 1, 6, 4] Insertion de 2 d’indice 1
Insertion de 5 d’indice 2 Insertion de 3 d’indice 2
Insertion de 1 d’indice 3 Insertion de 4 d’indice 3
[2, 3, 1, 5, 6, 4] Insertion de 5 d’indice 4
[2, 1, 3, 5, 6, 4] Insertion de 6 d’indice 5
[1, 2, 3, 5, 6, 4] Out[3]: [1, 2, 3, 4, 5, 6]
Insertion de 6 d’indice 4
Insertion de 4 d’indice 5
[1, 2, 3, 5, 4, 6]
[1, 2, 3, 4, 5, 6]
Out[1]: [1, 2, 3, 4, 5, 6]

page 3