from random import *

# Tri par insertion

def TriInsertion(liste):
    """
    TriInsertion(list liste) -> None
    Trie la liste de nombres de manière croissante
    """

    for i in range(1, len(liste)):
        
        elt = liste[i]              # prochain élément à trier
        position = i

        # décalage des éléments déjà triés:
        while position > 0 and liste[position-1] > elt:
            liste[position] = liste[position-1]
            position = position - 1

        # insertion de l'élément à trier:
        if position != i:
            liste[position] = elt
        
        

### Programme test ###

borne = 100000
n = int(input("Nombre d'éléments à trier: "))
liste = []
for i in range(n):
    liste.append(randint(0, borne))

print("La liste non triée est: ", liste, "\n")
TriInsertion(liste)
print("La liste triée est: ", liste)