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

  • Une partie non triée située en fin de liste

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 croissant).

Animation représentant le tri par insertionInformations[1]

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

MéthodeProgrammation en Python

Pour réaliser le tri par insertion en Python, il faut 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 source la valeur d'indice dest tout en supprimant l'ancienne valeur.

    • Exemple : Si l = [8, 3, 9, 5, 2], alors deplacer(l, 1, 3) modifie l, et si on print(l) on a comme affichage [8, 5, 3, 9, 2].

1
def deplacer(l, dest, source):
2
    valeur = l[source]
3
    l.pop(source)
4
    l.insert(dest, valeur)

  • 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ù palcer 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.

1
def position_tri(l, fin, valeur):
2
    for i in range(fin):
3
        if valeur < l[i]:
4
            return i
5
    return fin

  • La fonction principale tri_insertion(l) qui trie la liste l.

1
def tri_insertion(l):
2
    for i in range(len(l)):
3
        print(l)
4
        indice = position_tri(l, i, l[i])
5
        deplacer(l, indice, i)