tri-insertion.py

from random import seed, randint

        
def tri_insertion_iter(T) :
    def inserer_a_sa_place_iter(ind) : # insere le Ieme dans T[0:i]
        save = T[ind]
        i=ind
        while (i>0 and T[i-1] > save) : 
            T[i]=T[i-1]
            i -= 1
        T[i]=save
        
    if len(T) < 2 : return
    for i in range(1,len(T)) :
        inserer_a_sa_place_iter(i)  # insere le Ieme dans T[0:i]
        
# ------- Prog Princ
seed()                                      # initialise le generateur de nombres aleatoires
N=10
T = [randint(2, 3*N) for i in range(N)]     # construction de la liste
print("Avant le tri, liste = {}".format(T))
TT=[]                                       # Avant d'utiliser TT, il faut la faire exister !
TT[:]=T[:]
tri_insertion_iter(T)
TT.sort()
if (T == TT) :
    print("Après le tri, liste = {}".format(T))
else :
    print("ERREUR !!, T={}, TT={}".format(T,TT)) 

""" TRACE :
Avant le tri, liste = [14, 11, 24, 24, 27, 14, 30, 22, 22, 17]
Après le tri, liste = [11, 14, 14, 17, 22, 22, 24, 24, 27, 30]
"""