Tri par insertion

Principe

  1. Démarrer à partir de la deuxième case (case n° 2)
  2. Si son contenu est plus petit que celui de la case précédente :
    • Rechercher parmi les cases précédentes la plus petite valeur supérieure
    • Insérer la nouvelle valeur juste avant, et décaler vers le haut (ou la droite) toutes les cases jusqu'à la case « vidée ».
  3. Passer à la case suivante
Ainsi de suite, jusqu'à ne plus avoir de cases à explorer

Comme dans la méthode précédente, on constitue petit à petit une partie « basse » triée, mais au lieu de chercher la valeur qui vient « en bout » de cette partie, on insère la valeur trouvée là où il faut et on décale les cases suivantes.

Algorithme

Pour I variant de (IMin + 1) à IMax

Exemple

Tableau à trier : [7,5,1,9,2]

L'évolution du tableau est figurée ci-dessous.
La case colorée contient la valeur qu'on cherche à classer (et qui est mémorisée dans la colonne Valeur).
La valeur en gras est celle à laquelle est comparée la valeur à classer : si la précédente case contient une valeur plus faible, il faut comparer au contenu de toutes les cases précédentes.

1 2 3 4 5 Valeur 1 2 3 4 5 Valeur
Test 2ème case Test 4ème case
7 5 1 9 2 5 1 5 7 9 2 1
7 5 1 9 2 5 Test 5ème case
5 7 1 9 2 5 1 5 7 9 2   2
Test 3ème case 1 5 7 9 2 2
5 7 1 9 2   1 1 5 7 9 2 2
5 7 1 9 2   1 1 5 7 9 2 2
5 5 7 9 2   1 1 5 5 7 9 2
1 5 7 9 2   1 1 2 5 7 9 2

Exemple de programme en Visual Basic

Amélioration possible

La recherche de l'endroit où insérer une valeur se fait dans la partie basse du tableau, donc triée. Cette recherche est améliorée si elle est dichotomique.

Utilisation

Cette méthode donne des résultats peu performants ; elle est donc plutôt adaptée à des tableaux de faible taille, ou de taille moyenne (avec une recherche dichotomique).

Cette méthode est toutefois plus performante que d'autres pour des tableaux déjà presque triés.

Retour à la table des matières des tri

Dernière mise à jour de cette page : 12/8/2007