from random import randint
import timeit
import matplotlib as mpl
import matplotlib.pyplot as plt
import itertools as it

listaNum = [10000,20000,30000,40000,50000]
def geraLista(tam):
    lista = []
    i = 0
    while i < tam:
      n = randint(1,1*tam)
      if n not in lista:
        lista.append(n)
        i += 1
    return lista

def insertionSort(alist):
   for i in range(1,len(alist)):
       current = alist[i]
       while (i>0 and alist[i-1]>current):
           alist[i] = alist[i-1]
           i = i-1
           alist[i] = current
   return alist

mpl.use('Agg')
def desenhaGrafico(x,y,ym,yp,xl = "Entradas", yl = "Saídas"):
    fig = plt.figure(figsize=(10, 8))
    ax = fig.add_subplot(111)
    ax.plot(x,y, label = "Medio Tempo")
    ax.plot(x,ym, label = "Melhor Tempo")
    ax.plot(x,yp, label = "Pior Tempo")
    ax.legend(bbox_to_anchor=(1, 1),bbox_transform=plt.gcf().transFigure)
    plt.ylabel(yl)
    plt.xlabel(xl)
    fig.savefig('graph.png')


permutacoes = list(it.permutations([1,2,3,4,5,6],6))
listaX = list(permutacoes)

tempos = []

for i in listaX:

  tempo = timeit.timeit("insertionSort({})".format(list(i)),setup="from __main__ import insertionSort",number=1)

  tempos.append(tempo)

indexPiorCaso = tempos.index(max(tempos))
indexMelhorCaso = tempos.index(min(tempos))

print("Pior caso")
print(permutacoes[indexPiorCaso])
print(max(tempos))
print("Melhor caso")
print(permutacoes[indexMelhorCaso])
print(min(tempos))


tempos = []
temposMelhor = []
temposPior = []
for i in listaNum:
  lista = geraLista(i)
  melhor = sorted(lista)
  pior = sorted(lista, reverse=True)

  tempo = timeit.timeit("insertionSort({})".format(lista),setup="from __main__ import insertionSort",number=1)
  tempos.append(tempo)

  tempoMelhor = timeit.timeit("insertionSort({})".format(melhor),setup="from __main__ import insertionSort",number=1)
  temposMelhor.append(tempoMelhor)

  tempoPior = timeit.timeit("insertionSort({})".format(pior),setup="from __main__ import insertionSort",number=1)
  temposPior.append(tempoPior)


desenhaGrafico(listaNum, tempos, temposMelhor, temposPior)