AVA UFAL: Inicio

def main():
	lista = [2,1]
	print(quick_sort(lista,0,len(lista)-1))
	print(shell_sort(lista))

def selection(lista):
	for i in range(len(lista)-1):
		menor = i
		for j in range(i,len(lista)):
			if lista[j]<lista[menor]:
				menor = j

				aux = lista[i]
				lista[i] = lista[menor]
				lista[menor] = aux
	return lista

def insertion(lista):

	for i in range(1,len(lista)):
		j = i
		while lista[j]< lista[j-1] and j>0:
			aux = lista[j]
			lista[j] = lista[j-1]
			lista[j-1] = aux
			j -=1
		return lista

def bubble(lista):
	for i in range(len(lista)-1):
		for j in range(len(lista)-1-i):
			if lista[j]>lista[j+1]:
				lista[j],lista[j+1]=lista[j+1],lista[j]
	return lista


main()

##

def merge_sort(lista):
	return divisao(lista)

def divisao(lista):
	#dividir a lista
	lista1 = lista2= []
	if len(lista)>1:
		meio = len(lista)//2
		lista1 = divisao(lista[0:meio])
		lista2 = divisao(lista[meio:])
		return combinacao(lista1,lista2)
	else:
		return lista

def combinacao(lista1,lista2):
	i = j = 0
	lista = []
	for c in range(len(lista1)+len(lista2)):
		if i == len(lista1):
			lista.append(lista2[j])
			j+=1

		elif j == len(lista2):
			lista.append(lista1[i])
			i+=1

		elif lista1[i]<lista2[j]:
			lista.append(lista1[i])
			i+=1
		else:
			lista.append(lista2[j])
			j+=1
	return lista

##

def shell_sort(lista):
	h = 1
	while h<len(lista):
		h = 3*h+1
	print('h: ',h)
	while h!=1:
		h = h//3
		print('h: ',h)
		for i in range(h,len(lista)):
			aux = lista[i]
			j = i
			while lista[j-h]>aux:
				lista[j] = lista[j-h]
				j-=h
				if j<h:
					break
			lista[j] = aux
	return lista

##

def quick_sort(lista,p,r):
	if p<r:
		q = particao(lista,p,r)
		quick_sort(lista,p,q)
		quick_sort(lista,q+1,r)
	return lista

def particao(lista,p,r):
	pivo = lista[(p+r)//2]
	i = p-1
	j = r+1
	while i < j:
		j-=1
		while lista[j]>pivo:
			j-=1
		i +=1
		while lista[i]<pivo:
			i+=1
		if i<j:
			lista[i],lista[j] = lista[j],lista[i]
	return j

##

class Celula:
    item = None
    proximo = None

    def __init__(self,item):
        self.item = item

class PilhaEncadeada:
    topo = None
    tamanho = 0

    def estaVazia(self):
        return True if self.tamanho==0 else False

    def empilhar(self,item):
        aux = self.topo
        self.topo = Celula(item)
        self.topo.proximo = aux
        self.tamanho +=1


    def desempilhar(self):
        if not self.estaVazia():
            item = self.topo.item
            self.topo = self.topo.proximo
            self.tamanho -=1
            return item
        else:
            return ''

    def verTamanho(self):
        return self.tamanho


    def imprimir(self):
        aux = self.topo
        while aux!=None:
            print(aux.item)
            aux = aux.proximo

##

class Celula:
    item = None
    proximo = None

    def __init__(self,item):
        self.item = item

class FilaEncadeada:
    inicio = None
    fim = None
    tamanho = None

    def __init__(self):
        self.tamanho = 0

    def estaVazia(self):
        return self.tamanho == 0


    def enfileirar(self,item):
        if self.estaVazia():
            self.inicio = Celula(item)
            self.fim = self.inicio
        else:
            self.fim.proximo = Celula(item)
            self.fim = self.fim.proximo
        self.tamanho +=1

    def desenfileirar(self):
        if not self.estaVazia():
            aux = self.inicio
            self.inicio = self.inicio.proximo
            item = aux.item
            del aux
            self.tamanho -= 1
            return item
        else:
            print('Está vazia')





    def imprimir(self):
        aux = self.inicio
        while aux!=None:
            print(aux.item)
            aux = aux.proximo
        print('---')


###

class Celula:
    item = None
    proximo = None

    def __init__(self,item):
        self.item  = item

class Lista_Encadeada:
    inicio = None
    quantidade = None

    def __init__(self):
        self.quantidade = 0


    def estaVazia(self):
        return self.quantidade == 0

    def inserir(self,pos,item):
        if self.estaVazia():
            self.inicio = Celula(item)
            self.quantidade+=1
        else:
            if pos <= self.quantidade + 1:
                p = self.inicio
                for i in range(pos-1):
                    p = p.proximo
                aux = Celula(item)
                aux.proximo = p.proximo
                p.proximo = aux
                self.quantidade +=1
            else:
                print('operacao invalida')


    def remover(self,pos):
        if not self.estaVazia():
            if pos <= self.quantidade:
                if pos == 0:
                    aux = self.inicio
                    self.inicio = aux.proximo
                    item = aux.item
                    del aux
                    self.quantidade -= 1
                    return item
                else:
                    p = self.inicio
                    for i in range(pos-1):
                        p = p.proximo
                    aux = p.proximo
                    item = aux.item
                    p.proximo = aux.proximo
                    self.quantidade -=1
                    del aux
                    return item
            else:
                print('operacao invalida')
        else:
            print('operacao invalida')


    def imprimir(self):
        p = self.inicio
        while p!= None:
            print(p.item,end=' ')
            p = p.proximo
        print('\n---')