Tri par insertion

Le tri par insertion, comme le tri par sélection, consiste à découper la liste en deux parties :

• Une partie triée située en début de liste (en noir sur le schéma ci-dessous)
• Une partie non triée située en fin de liste (en blanc sur le schéma ci-dessous)

Le changement majeur est qu'au lieu de chercher la valeur minimale dans la partie non triée, on va récupérer la première valeur qu'on va insérer dans la première partie (en respectant l'ordre du tri).

Une animation en ligne permet également de visualiser l'algorithme. Bien sélectionner INS en haut.

Programmation en Python

Pour réaliser le tri par sélection en Python, il est plus pratique de séparer les étapes en fonctions pour simplifier le programme final :

• Une première fonction deplacer(l, dest, source) permet d'insérer dans la liste l à la position dest la valeur d'indice source tout en supprimant l'ancienne valeur.
  • Exemple : Si l = [1, 1, 4, 5, 3, 2, 8], alors deplacer(l, 2, 4) modifie l, et si on print(l) on a comme affichage [1, 1, 3, 4, 5, 2, 8]. En effet, la valeur d'indice 4 (dont la valeur est 3) a été déplacé à la position 2. Les valeurs sur la droite ont été décalées.
• Une deuxième fonction position_tri(l, fin, valeur) renvoie l'indice où la valeur valeur doit être insérée dans la liste l de telle sorte que la sous-liste de l'indice 0 à l'indice fin exclu soit toujours* triée après insertion de la valeur.
  • Exemple : Si l = [1, 5, 6, 8, 3, 2], alors position_tri(l, 4, 3) regarde où placer la valeur 3 dans la sous-liste [1, 5, 6, 8]. On peut insérer 3 à l'indice 1 ce qui donnerait [1, 3, 5, 6, 8] qui est toujours triée. La fonction renvoie donc 1 sans modifier la liste.
• La fonction principale tri_insertion(l) qui trie la liste l.