import matplotlib as mpl
mpl.use('Agg')
import matplotlib.pyplot as plt
from random import randint

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

def desenhaGrafico(x, a, b, c, d, xl="Nº de Elementos", yl="Operações"):
    fig = plt.figure(figsize=(10, 10))
    ax = fig.add_subplot(111)
    plt.plot(x, a, label="bubbleSort")
    ax.plot(x, c, label="insertionSort")
    ax.plot(x, b, label="selectionSort")
    ax.plot(x, d, label="quickSort")
    ax.legend(bbox_to_anchor=(1, 1), bbox_transform=plt.gcf().transFigure)
    plt.ylabel(yl)
    plt.xlabel(xl)
    fig.savefig('operacoes.png')

def bubbleSort(array):
	op = 0
	for j in range(0,len(array)):
		for i in range(0,len(array)-1):
			if array[i]>array[i+1]:
				aux = array[i+1]
				array[i+1] = array[i]
				array[i] = aux
				op += 1
	return op

def selectionSort(array):
    op = 0
    for j in range(len(array) - 1, 0, -1):
        x = 0
        for i in range(1, j + 1):
            if array[i] > array[x]:
                x = i
        array[j], array[x] = array[x], array[j]
        op += 1
    return op


def insertionSort(array):
    op = 0
    for i in range(1,len(array)):
        x = array[i]
        j = i-1
        while j>=0 and x<array[j]:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = x
        op += 1
    return op


def quickSort(array):
	op = 0
	aux = []
	i = (0, len(array) - 1)
	aux.append(i)
	for i in aux:
		idx = i[0]
		temp = i[1]
		while temp > idx:
			pivo = array[temp]
			elem = array[idx]
			if elem > pivo:
				array[temp] = elem
				array[idx] = array[temp - 1]
				array[temp - 1] = pivo
				temp -= 1
				op += 1
			else:
				idx += 1
		esq = i[0]
		d = i[1]
		if temp > 1 and esq < temp - 1:
			aux.append((esq, temp - 1))
		if temp < len(array) -1 and temp + 1 < d:
			aux.append((temp + 1, d))
	return op

qntes = []
bubble = []
insertion = []
selection = []
quick = []
for i in range(3000, 24001, 3000):
	qntes.append(i)
	bubble.append(bubbleSort(geraLista(i)))
	insertion.append(insertionSort(geraLista(i)))
	selection.append(selectionSort(geraLista(i)))
	quick.append(quickSort(geraLista(i)))

desenhaGrafico(qntes, bubble, insertion, selection, quick)