Tri par insertion

Plus précisément, dans l’algorithme de tri par insertion, on commence par l’élément le plus à gauche et on avance pas à pas vers la droite. Dès qu’on trouve un élément plus petit que ceux placés à sa gauche, on décale un à un tous les éléments pour libérer un emplacement pour la valeur en cours et on la place à sa position correcte. Ainsi, si l’on dispose d’un tableau [0, 2, 4, 1, 10, 8] et que l’on s’intéresse à la valeur 1, on décalera d’abord 4, puis 2 vers la droite, avant de placer 1 entre 0 et 2. On obtient alors [0, 1, 2, 4, 10, 8]. On passe ensuite à l’élément 10. On ne fait rien puisqu’il est plus grand que tous les éléments de gauche. Puis, on prend 8 et on décale 10 vers la droite pour placer 8 entre 4 et 10.

a = [...]
for i in range(1, len(a)):              # on commence à partir du deuxième élément
    while i > 0 and a[i] < a[i - 1]:    # tant que l'élément courant est plus petit
        a[i - 1], a[i] = a[i], a[i - 1] # on décale l'élément courant avec son prédécesseur
        i -= 1                          # on met à jour l'indice de l'élément courant
print(a)