Chapitre 10 : Tri par insertion.
Introduction :
Vous connaissez déjà une façon de trier une liste. Mais est-ce la seule ? Et si une autre stratégie s'avérait plus efficace dans certaines situations ?
1. Tri par insertion.
Le tri par insertion est un algorithme de tri simple qui construit une liste triée un élément à la fois en insérant chaque élément à sa place appropriée dans la partie triée de la liste.
L'algorithme de tri par insertion fonctionne comme suit :
- Commencer avec le deuxième élément (l'élément à l'index 1) et le comparer avec le premier élément. Si le deuxième élément est plus petit, les échanger.
- Continuer à déplacer l'élément comparé vers la gauche jusqu'à ce qu'il atteigne sa position appropriée parmi les éléments triés précédents.
- Répéter les étapes 1 et 2 pour tous les éléments suivants dans la liste non triée.
Observe l'animation ci-dessous pour voir l'algorithme à l'œuvre :
Clique sur « Démarrer / Redémarrer » pour lancer l'animation.
2. Exercice : tri par insertion à la main.
À faire dans le cahier.
À la main :
Trier la liste [42, 17, 9, 87, 23, 56, 34, 71, 5, 91] en mettant une ligne par étape avec un algorithme de tri par insertion.
3. Pseudo-code du tri par insertion
Pseudo-code
Algorithme TRI_INSERTION(tab)
n ← longueur(tab)
Pour i allant de 1 à n-1 faire
clé ← tab[i]
j ← i - 1
Tant que j ≥ 0 et tab[j] > clé faire
tab[j+1] ← tab[j]
j ← j - 1
tab[j+1] ← clé
Renvoyer tab4. Exercice : implémentation du tri par insertion.
Compléter la fonction tri_insertion ci-dessous pour trier une liste en utilisant l’algorithme du tri par insertion. La fonction modifie la liste sur place.
5. Exercice : invariant de boucle du tri par insertion.
À faire dans le cahier.
On veut prouver la correction de l’algorithme de tri par insertion à l’aide d’un invariant de boucle.
Rappel du pseudo-code :
Algorithme TRI_INSERTION(tab)
n ← longueur(tab)
Pour i allant de 1 à n-1 faire
clé ← tab[i]
j ← i - 1
Tant que j ≥ 0 et tab[j] > clé faire
tab[j+1] ← tab[j]
j ← j - 1
tab[j+1] ← clé
Renvoyer tab-
Propose un invariant de boucle pour la boucle externe (celle sur
i). -
Montre que l’invariant est vrai au début (initialisation).
-
Montre que l’invariant est conservé après une itération (conservation).
-
Explique pourquoi, à la fin de la boucle, l’invariant permet de conclure que le tableau est trié.
6. Complexité du tri par insertion
Principe du tri par insertion
Le tri par insertion consiste à construire progressivement une partie triée du tableau, en insérant chaque nouvel élément à la bonne place.
Nombre de comparaisons
Soit un tableau de taille \( n \).
Dans le pire des cas (lorsque le tableau est trié dans l’ordre décroissant), chaque nouvel élément doit être comparé à tous ceux qui le précèdent pour être inséré à la bonne place.
Plus précisément :
- le deuxième élément est comparé avec le premier : 1 comparaison ;
- le troisième élément est comparé avec les deux premiers : 2 comparaisons ;
- le quatrième élément est comparé avec les trois premiers : 3 comparaisons ;
- et ainsi de suite jusqu’au dernier élément, comparé \( n - 1 \) fois.
Le nombre total de comparaisons est donc :
\( 1 + 2 + \dots + (n - 1) \)
Calcul de la somme
Cette somme vaut :
\( 1 + 2 + \dots + (n - 1) = \frac{n(n - 1)}{2} \)
Complexité temporelle
Le terme dominant de \( \frac{n(n - 1)}{2} \) est \( n^2 \).
La complexité du tri par insertion dans le pire des cas est donc : \( \mathcal{O}(n^2) \).
Cas particulier favorable
Si le tableau est déjà presque trié, le nombre de comparaisons est faible.
Dans le meilleur des cas (tableau déjà trié), la complexité est \( \mathcal{O}(n) \).
Le tri par insertion est donc plus efficace que le tri par sélection sur des tableaux presque triés.