Table des matières
Tri par insertion
Version avec deux tableaux
Tout le long de l'algorithme, on considère deux zones du tableau. L'une à gauche – sur fond orange dans l'exemple – et l'autre à droite – sur fond jaune dans l'exemple.
L'algorithme est constitué principalement d'une boucle répétitive. À chaque exécution de cette boucle, on considère le premier item de la zone jaune.
On cherche, en partant de l'item sélectionné et en remontant vers sa gauche, la position où il faudrait l'insérer de façon à maintenir la zone orange dans l'ordre croissant. C'est à dire que partant de l'item sélectionné on remonte vers la gauche à la recherche d'un item inférieur ou égal. En même temps on décale les éléments d'une case vers la droite pour faire une place.
On décale les items de la zone orange de façon à laisser un trou où insérer l'item sélectionné.
La boucle s'arrête quand on a traité le dernier item du tableau.
Le tableau contient 8 items. Combien de processus d'insertion doit on effectuer ? Et si le tableau contenait n items ?
L'insertion est plus ou moins coûteuse : Quand on doit insérer un item tout à gauche – comme le 13 dans l'exemple – on doit décaler d'une case à droite tous les items de la zone orange, soit 5 items. Au contraire dans certains cas, on n'a rien à faire – exemple du 86.
Si on se place dans le pire des cas, le nombre de décalage à faire, qui est une bonne estimation du coût total de l'algorithme, sera de : $$1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36$$
Ce cas se produit si le tableau initial est trié en ordre inverse.
Preuve de correction
On profite de notre travail sur les algorithmes de tri pour réfléchir aux problèmes de correction.
Un algorithme est correct si pour toutes les entrées permises :
il termine en un temps fini, il donne la réponse attendue
Terminaison
La boucle principale s'exécute pour chaque item du tableau pris dans son ordre d'apparition dans le tableau d'origine. Il est donc évident que cette boucle se termine puisque le nombre d'items dans le tableau est fini.
Validité de la réponse
On veut prouver qu'à la fin de l'algorithme, les items du tableau sont bien dans l'ordre croissant.
À vous : justifiez que :
- les items de la zones orange sont toujours dans l'ordre croissant
- le tableau est dans l'ordre à la fin de l'exécution
L'algorithme
Variante à améliorer
FONCTION tri_par_insertion
ENTRÉE: tableau, le tableau à trier
La fonction ne renvoie rien, le tableau est trié en place
DÉBUT
soit n la longueur de tableau
POUR i allant de 1 à n - 1 FAIRE
soit item l'élément de rang i dans tableau
soit j = i
TANT QUE j > 0 et tab[j-1] > item FAIRE
tab[j] = tab[j-1]
j = j - 1
tab[j] = item
FIN
FIN
- Implémentez cet algorithme en Python.
- En fonction de
n, et en considérant que chaque ligne de votre programme s'exécute en un temps T, quelle sera la durée totale de ce tri ?