# ======================================= #
# TRI PAR INSERTION                       #
# Programme de base avec temps de calcul. #
# Version du 21/11/2015                   #
# ======================================= #

# Importations
from random import randint
from time import perf_counter

# La fonction de tri
def tri_insert(L):
    lL = len(L)
    for i in range(1,lL):
        x = L[i]
        k = i
        while k > 0 and x < L[k-1]:
            L[k] = L[k-1]
            k -= 1
        L[k] = x

# Génération d'une liste de nombres entiers aléatoires.
n = int(input('Longueur de la liste à trier ? '))
valmax = int(input('\nValeur maxi des nombres générés ? '))
LNA = [randint(0,valmax) for i in range(n)]
L_init = list(LNA)

# Tri de la liste LNA des nombres aléatoires
t_start = perf_counter()
tri_insert(LNA)
t_end = perf_counter()
t_ellapse = t_end - t_start

# Affichage des listes (initiale et triée) ... si elles ne sont pas trop grandes ! :)
#
if n <= 50:
    print('\nListe initiale :')
    print(L_init)
    print('\nListe triée :')
    print(LNA)

# Affichage de la durée du tri
print('\nDurée du tri : ' + str(t_ellapse))

# ================
# FIN DU PROGRAMME