from random import randint

from timeit import timeit

import matplotlib.pyplot as plt

def desenhaGrafico(time,time2, tam):
    plt.title("quick Sort")
    plt.plot(tam, time, label="Tempo Médio", color = 'blue')
    plt.plot(tam, time2 , label="Pior Tempo", color='red')
    plt.legend(bbox_to_anchor=(1, 1), bbox_transform=plt.gcf().transFigure)
    xl = "N"
    yl = "Tempo"
    plt.ylabel(yl)
    plt.xlabel(xl)
    plt.show()

def geraLista(tam):
    lista = []
    for i in range(tam):
        lista.append(randint(1,1*tam))
    return lista

def geraListaInversa(tam):
    lista=[]
    for i in range(tam,0,-1):
        lista.append(i)
    return lista

def quick_sort(lista):
    if len(lista) <= 1:
        return lista

    u = int(len(lista)/2)
    pivo = lista[u]

    meio=[]
    esquerda=[]
    direita=[]

    for i in lista:
        if i == pivo:
            meio.append(i)
        elif i < pivo:
            esquerda.append(i)
        else:
            direita.append(i)

    return quick_sort(esquerda) + meio + quick_sort(direita)


tam = [1000,10000,20000,30000,40000,50000,100000]

def caso_medio():
    temp=[]
    for i in tam:
        lista=geraLista(i)

        tempo = timeit("quick_sort({})".format(lista),setup="from __main__ import quick_sort",number=1)
        temp.append(tempo)
        print(tempo)

    print('\n')
    return temp

def pior_caso():
    temp=[]
    for i in tam:
        lista=geraListaInversa(i)

        tempo = timeit("quick_sort({})".format(lista),setup="from __main__ import quick_sort",number=1)
        temp.append(tempo)
        print(tempo)
    return temp

desenhaGrafico(caso_medio(), pior_caso(), tam)