Cette page suit toujours le même plan : le principe en une phrase, les étapes dans l'ordre exact, une démonstration interactive, le code Python, puis le nombre de comparaisons et la complexité.
Utilisation de la démonstration
La démonstration avance uniquement quand vous cliquez sur « Suivant » ou « Précédent » : rien ne bouge tout seul. Un bouton « Lecture automatique » est disponible si vous préférez laisser les étapes défiler seules, à une vitesse que vous choisissez.
1. Vocabulaire à connaître avant de commencer
Chaque mot ci-dessous est utilisé exactement dans ce sens dans toute la page.
Mot
Définition précise
Tableau
Une liste de valeurs numérotées à partir de l'indice 0.
Indice
Le numéro qui repère une case du tableau. Le premier indice est 0, pas 1.
Comparer deux valeurs
Regarder laquelle des deux est la plus petite (pour un tri croissant).
Décaler une valeur
Une valeur se déplace d'une case vers la droite, sans échange : l'ancienne valeur de cette case est recopiée plus loin.
Sous-tableau trié
La partie du tableau, à gauche, qui est déjà dans le bon ordre à cette étape.
Itération
Un passage dans la boucle principale. On note i le numéro de l'itération.
Complexité
Une estimation du nombre d'opérations faites par l'algorithme, en fonction du nombre n de valeurs du tableau.
2. Le tableau d'exemple utilisé dans cette page
On utilise le tableau T, de 6 valeurs, pour la démonstration du tri par insertion :
Indice
0
1
2
3
4
5
Valeur T[i]
5
3
8
1
9
2
But de l'algorithme : transformer ce tableau, sur place, pour obtenir T = [1, 2, 3, 5, 8, 9], trié par ordre croissant.
3. Tri par insertion
3.1 — Principe, en une phrase
Principe
À chaque étape i, on prend la valeur à l'indice i et on la décale vers la gauche, case par case, jusqu'à ce qu'elle arrive à sa bonne place dans la partie déjà triée.
3.2 — Les étapes, dans l'ordre exact
On part de l'indice i = 1 (la case d'indice 0, seule, est toujours considérée comme triée).
On garde en mémoire la valeur à insérer : valeur = T[i].
On compare valeur avec la case juste à sa gauche (indice j = i - 1). Si cette case contient une valeur plus grande que valeur, on la décale d'une case vers la droite.
On continue à comparer et décaler vers la gauche, tant qu'il reste une case à gauche (j >= 0) et que la valeur de cette case est plus grande que valeur.
Dès qu'on trouve une case dont la valeur est plus petite ou égale à valeur, ou qu'on arrive au début du tableau, on y place valeur.
On passe à l'indice suivant : i = i + 1, et on répète les étapes 2 à 5 tant que i est inférieur à n.
3.3 — Démonstration interactive
partie déjà triéeindice j en cours de comparaisonemplacement actuel de « valeur »
Étape 1 / 1
La ligne de code correspondant à l'étape en cours est surlignée ci-dessous.
3.4 — Code Python
def tri_insertion(T): """Trie le tableau T par ordre croissant (tri par insertion).""" n = len(T) for i in range(1, n): valeur = T[i] j = i - 1 while j >= 0 and T[j] > valeur: T[j + 1] = T[j] j = j - 1 T[j + 1] = valeur return T# Jeu de données : le même exemple que la démonstration ci-dessusT = [5, 3, 8, 1, 9, 2]print(tri_insertion(T))# Résultat affiché : [1, 2, 3, 5, 8, 9]
3.5 — Nombre de comparaisons et complexité
Le nombre de comparaisons dépend de l'ordre initial des valeurs, contrairement au tri par sélection.
Meilleur cas : le tableau est déjà trié. Chaque valeur est comparée une seule fois avec sa voisine de gauche : n - 1 comparaisons. Complexité en O(n).
Pire cas : le tableau est trié dans l'ordre décroissant. Chaque valeur doit être décalée jusqu'au début : n(n-1)/2 comparaisons. Complexité en O(n²).
Pour notre exemple, le nombre de comparaisons est de 11 (vous pouvez les compter vous-même dans la démonstration ci-dessus, à chaque fois que le message indique « on compare »).