counting.py

import random
from timeit import timeit
import matplotlib.pyplot as plt

idade = 24
temposMedios = []
temposOtimos = []
temposPiores = []
tamanhos = [100, 300, 600, 900, 1200, 1500, 1800, 2100]

for i in range(len(tamanhos)):
	tamanhos[i] = tamanhos[i] * idade

def listaAleatoria(tam):
	lista = []
	while len(lista) < tam:
		n = random.randint(1, 1*tam)
		lista.append(n)
	return lista

def listaCrescente(tam):
	lista = []
	for i in range(tam):
		lista.append(i)
	return lista

def listaDecrescente(tam):
	lista = []
	for i in range(tam):
		lista.append(i)
	lista.reverse
	return lista

def countingSort(array):
	countI = max(array) + 1
	countA = [0]*countI
	position = 0
	for freq in array:
		countA[freq] += 1
	for freq in range(countI):
		for i in range(countA[freq]):
			array[position] += 1
			position += 1
	return array

def testaOrdenamento(quant = 5, tam = 10):
	for i in range(quant):
		casoTeste = listaAleatoria(tam)
		saida = sorted(casoTeste[: ])
		assert countingSort(casoTeste) == saida, "Erro {} =/= {} ".format(countingSort(casoTeste), saida)

def grafico(x,y1,y2,y3,xl = "Numeros(und)", yl = "Tempo(seg)"):
	plt.plot(x, y1, label = "Medio Caso")
	plt.plot(x, y2, label = "Melhor Caso")
	plt.plot(x, y3, label = "Pior Caso")
	legend = plt.legend(loc='upper center', shadow=True)
	frame = legend.get_frame()
	frame.set_facecolor('0.90')
	plt.xlabel(xl)
	plt.ylabel(yl)
	plt.show()

for i in tamanhos:

    lista = listaAleatoria(i)

    tempoMedio = timeit("countingSort({})".format(lista), setup="from __main__ import countingSort", number=1)
    temposMedios.append(tempoMedio)
    listaOtimo = lista[:]
    listaOtimo.sort()
    tempoOtimo = timeit("countingSort({})".format(listaOtimo), setup="from __main__ import countingSort", number=1)
    temposOtimos.append(tempoOtimo)
    listaPior = listaOtimo[:]
    listaPior.reverse()
    tempoPior = timeit("countingSort({})".format(listaPior), setup="from __main__ import countingSort", number=1)
    temposPiores.append(tempoPior)


testaOrdenamento()
grafico(tamanhos, temposMedios,  temposOtimos, temposPiores)