# insertion_sort.py
'''
Suponha que temos um verto v[0...n-1]
Ideia do algoritmo para ordenar o vetor v crescentemente:
  --- manter ordenado (cresc) a parte inicial do vetor v
  --- iterativamente, aumentar (de uma unidade) o comprimento da parte inicial que está ordenada
  --- Para i variando de 1 a n-1, considerando que a parte v[0... i-1] ja' esta' ordenada,
         decidir onde encaixar o elemento qu está na posicao i, de modo a ter a parte v[0...i] ordenada:
        -- faz-se aux = v[i],
        -- comecando da posicao i-1 (e decrescendo), cada vez que um elemento maior que aux e' encontrado,
             tal elemento e' deslocado para a direita. Isso e' repetido ate' encontrar a posicao em que aux
             deve ser encaixada.
'''           

def main():
     n = int(input ("Digite o valor de n (inteiro positivo):"))
     v = [ ]  # cria lista vazia
     for i in range(n):
          num = int(input("Digite um termo da sequencia:"))
          v.append(num)
         
    print()
    print(v)
    
    for i in range(1,n):    #  para i variando de 1 a n-1
         aux = v[i]            # ate' a posicao i-1 o vetor esta' ordenado;
                                    # precisa decidir onde encaixar o elemento aux (= v[i])
         j= i-1            # comece verificando a partir da posicao
         i-1
	 
         while (j >= 0 and v[j] > aux):
                v[j+1] = v[j]      # desloca o elemento que esta' na posicao j para a posicao j+1                              
                j = j-1              # continue procurando onde encaixar o elemento aux
		
         v[j+1] = aux
        
    print()    
    print(v)
#-------------------------
main()