Python, l'algorithme d'insertion.

Dans cet article, nous allons détailler le fonctionnement de l’algorithme de tri par insertion au travers d’un exemple complet en Python. Chaque étape du processus est commentée et illustrée pour vous permettre de comprendre le déplacement et l’insertion des éléments dans la liste.

liste1 = [20, 5, 28, 9, 32, 7, 11]

def trier_liste_par_insertion(liste):
    n = len(liste)
    for i in range(1, n):
        print(f"Étape {i}")
        x = liste[i]
        print(f"{x=}")
        j = i
        print(f"{j=}")
        while j > 0 and liste[j - 1] > x:
            print(f"boucle while {j=}")
            liste[j] = liste[j - 1]
            j -= 1
            print(f"prochaine itération {j=}")
        liste[j] = x
        print(
            f"Étape {i} terminée, {liste[j]=} \n{liste}"
        )
    return liste

trier_liste_par_insertion(liste1)

Nous définissons une liste d’entiers non triés que nous allons passer à notre fonction de tri :

liste1 = [20, 5, 28, 9, 32, 7, 11]

Nous déclarons une fonction nommée trier_liste_par_insertion qui prendra une liste en argument et appliquera l’algorithme de tri par insertion :

def trier_liste_par_insertion(liste):

Nous mesurons la longueur de la liste et stockons ce nombre dans n afin de connaître le nombre total d’éléments à parcourir :

n = len(liste)

Nous parcourons les indices de 1 jusqu’à n - 1, car l’élément d’indice 0 est considéré comme déjà trié au départ :

for i in range(1, n):
    print(f"Étape {i}")

Nous copions la valeur à insérer (liste[i]) dans la variable x, afin de la comparer ensuite avec les éléments qui la précèdent :

x = liste[i]
print(f"{x=}")

Nous initialisons j avec l’indice courant ; j va se déplacer vers la gauche pour chercher la bonne position de x :

j = i
print(f"{j=}")

Nous entrons dans une boucle tant que nous ne sommes pas revenus au début de la liste (j > 0) et que l’élément situé juste avant (liste[j - 1]) est plus grand que x :

while j > 0 and liste[j - 1] > x:
    print(f"boucle while {j=}")
    liste[j] = liste[j - 1]
    j -= 1
    print(f"prochaine itération {j=}")

Quand la bonne position est trouvée, nous plaçons x à l’indice j pour maintenir l’ordre trié de la sous-liste de gauche :

liste[j] = x
print(
    f"Étape {i} terminée, {liste[j]=} \n{liste}"
)

Une fois la boucle terminée, nous renvoyons la liste triée :

return liste

Nous appelons la fonction en lui passant liste1, ce qui lance l’algorithme et affiche toutes les étapes détaillées :

trier_liste_par_insertion(liste1)