Le tri par insertion fait partie de la famille des algorithme de tri, on l'utilise intuitivement quand on doit trier une liste de cartes et de billets de banque dans un ordre croissant pour l'exemple. l'algorithme de tri par insertion fait aussi partie de la sous famille des tris stables, c'est à dire qu'il ne change pas l'ordre d'apparition des éléments égaux.

Dans une liste de n éléments nous partirons de l'élément n0 jusqu'à n-1 en comparant n0 à n1, si n1 est plus grand que n0 alors aucun changement ne sera fait. On passe à l'élément suivant, on compare n1 à n2 on se rend compte que n2 est plus petit que n1 alors on sort n2 de la liste on change de place n1, on compare ensuite n0 à n2, n0 est plus petit que n2 donc n0 reste à sa place et on insert n2 à la place d'origine de n1.

Algorithme en python

"""
objectif: L'objectif d'un algorithme de tri par insertion est de ranger une liste dans un ordre croissant.        
entrée: Une liste de nombres réels non ordonnés
sortie: Une liste de nombres réels ordonnés
"""
#initialisation des variables
t=[2,5,4,1,7]
 
def tri_par_insertion(t):
    j=1
    while j<len(t): #boucle 1   
        i=j-1
        k=t[j] #K stocke la valeur de t[j] au cas où si l'on entre dans la boucle 2
        while i>=0 and t[i]>k: #boucle 2
            t[i+1]=t[i] #on place t[i] à la place initiale de k
            i-=1 #la valeur de i déscend chaque fois que k<t[i]
        t[i+1]=k #une fois la boucle 2 terminé on place k dans t[i+1]
        j+=1 #j+1 pour passer à l'élément suivant de la liste à trier
    return t
 
#programme principal
print(tri_par_insertion(t))
 
#sortie
[1, 2, 4, 5, 7]

Algorithme en pseudo-code
Application écrite de l'algorithme

le tri par insertion possède deux types de complexités:

Dans le pire des cas quand on se retrouve avec une liste trié à l'envers[5, 4, 3, 2, 1] la complexité est quadratique noté Θ(n²)