Le tri par insertion est comparable au tri par sélection vu dans le TP2

On considère une tableau L d'éléments comparables que l'on trie selon le protocole suivant.

• On classe au fur et à mesure de l'avancée dans le tableau :
  • si le tableau n’a qu’un seul élément il est déjà trié,
  • sinon on prend le deuxième et on le compare au premier pour les mettre dans le bon ordre.
• Si on suppose les i premiers éléments déjà classés on prend le (i + 1)-ème que l’on compare, par exemple en descendant à partir de la position i, jusqu’à trouver, ou pas, un plus petit que lui et l'insérer alors à la bonne place.

FONCTION tri_par_insertion
ENTRÉE: tableau_a_trier, le tableau à trier
La fonction ne renvoie rien, le tableau est trié en place
DÉBUT
  soit n la longueur de tableau_a_trier
  POUR i allant de 1 à n - 1 FAIRE
    soit item l'élément de rang i dans tableau_a_trier
    soit j = i
    TANT QUE j > 0 et l'élément de rang j-1 supérieur à item FAIRE
      copier l'item de rang j-1 au rang j
      j passe à j-1
    FIN
    copier item au rang j
  FIN
FIN

Ici, le tri se fait en place, ce qui est une bonne chose du point de vue de l'utilisation de la mémoire. On peut apporter des améliorations pour limiter le nombre de comparaisons ou d'échanges, mais cela ne change pas le principe d’insertion : il y a deux boucles imbriquées, ici une boucle globale en for et à l'intérieur une boucle en while.

1. Traduisez cet algorithme en Python et testez.
2. Écrivez une fonction liste_aleatoire(N:int, n:int) créant une liste aléatoire de n entiers i tels que 0 ⇐ i < N.
3. À l’aide de la fonction time du module time, donner la durée d’exécution de la fonction tri_insertion pour quelques listes aléatoires de grande taille.
   On pourra commencer par

$N = 10^7$ et $n$ dans $\left\lbrace 100, 1000, 10 000\right\rbrace$.

On prouvera plus tard la correction du programme et on étudiera sa complexité.

En profitant du fait qu'au moment de chaque insertion, le début de liste est déjà trié, on peut procéder à une insertion dichotomique selon le principe qui suit :

• On suppose que l'on dispose d’une liste L de longueur n triée dans l’ordre croissant et d'un élément a comparable que l’on veut ajouter à la liste en l'insérant de manière telle qu'en sortie la nouvelle liste soit encore triée dans l'ordre croissant.
• On considère l'élément m du milieu de la liste – il faudra choisir lequel on prend lorsque n

est pair

• Si a == m alors on peut insérer a à gauche ou à droite de m (il faudra choisir),
• si a < m alors on peut recommencer en insérant a dans la sous-liste extraite de L en prenant les premiers éléments de L jusqu'à m
• si a > m, alors on insère a dans la sous-liste de L extraite à droite de m.

On montre que la complexité dans le pire des cas du tri avec insertion dichotomique est en $n\,\ln(n)$.