"""
Carlos J Corrada Bravo
Este programa calcula el promedio de tiempo de ejecucion de cuatro algoritmos de ordenamiento
La variable maxValor define el valor maximo de los elementos de la lista
La variable largoLista define el largo de las listas a ordenar
La variable veces define las veces que se va a hacer el ordenamiento 
Al final se imprimen los promedios de cada algortimo
"""
from random import randint
import time

def mergeSort(lista):
    #definan el algoritmo de ordenamiento mergesort
    # se vieron videos y se leyo sobre el algoritmo en GeekforGeeks, educative.io y medium.com el codigo fue basado en esto


    # si tiene al menos un elemento
    if len(lista) > 1:
        # buscar mitad de lista
        middle = len(lista)//2
        # llamada recursiva de mitad izq de lista
        Left = mergeSort(lista[:middle])
        # llamada recursiva de mitad derecha de lista
        Right = mergeSort(lista[middle:])

        # return y llamada recursiva merge para combinar ambas listas
        return merge(Right, Left, lista)

    # se devuelve cuando solamente haya un elemento
    return lista

def merge(Right, Left, lista):
    # acumuladores 
    i = 0
    j = 0
    k = 0

    # comparar las dos listas y ordenar de manera ascendiente 
    while i < len(Left) and j < len(Right):
        # si el elemento de la izq es menor que la derecha
        # añadelo a la lista
        if Left[i] < Right[j]:
            lista[k] = Left[i]
            i += 1
            k += 1
        # si el elemento de la derecha es menor que la derecha
        # añadelo a la lista
        else:
            lista[k] = Right[j]
            j += 1
            k += 1

    # si quedan elementos en la lista izq añadelos en la lista
    while i < len(Left):
        lista[k] = Left[i]
        i += 1
        k += 1

    # si quedan elementos en la lista derecha añadelos en la lista
    while j < len(Right):
        lista[k] = Right[j]
        j += 1
        k += 1
    
    return lista

def heapSort(lista):
	#trabajado por Andrel Fuentes
	#definan el algoritmo de ordenamiento heapsort

	#crear el "max heap"
	for i in range(largoLista // 2, -1, -1):
		heapify(lista, largoLista, i)

	for i in range(largoLista - 1, 0, -1):
		lista[i], lista[0] = lista[0], lista[i]

		heapify(lista, i, 0)

	return lista

def quickSort(lista, bajo, alto):
    if bajo < alto:
        p = partition(lista, bajo, alto)
        quickSort(lista, bajo, p - 1)
        quickSort(lista, p + 1, alto)
    return lista
	

def partition(lista, bajo, alto):
    pivot = lista[alto]
    i = bajo - 1
    for j in range(bajo, alto):
        if lista[j] <= pivot:
            i += 1
            lista[i], lista[j] = lista[j], lista[i]
    lista[i + 1], lista[alto] = lista[alto], lista[i + 1]
    return i + 1

def shellSort(lista):
	# definan el algoritmo de ordenamiento shellsort
	div = len(lista) // 2
	# verifica si no se puede dividir mas
	while div != 0:
	# dividir lista en sub listas
		for j in range(div):
			# hacer insertion sort en sub listas
			for x in range(div + j, len(lista), div):
				key = lista[x]
				pos = x - div
				while pos >= 0 and key < lista[pos]:
					lista[pos + div] = lista[pos]
					pos -= div
				lista[pos + div] = key
		div //= 2
	return lista

def heapify(lista, largo, raiz):
	#trabajado por Andrel Fuentes
	#encontrar cual el valor mayor entre de los hijos y raiz
	#define las posiciones de los hijos
	largest_value = raiz
	left_child = raiz * 2 + 1
	right_child = raiz * 2 + 2

	#se verifica si el hijo izquierdo es mayor, actualizar variable de mayor
	#si fuera necesario
	if left_child < largoLista and lista[left_child] > lista[raiz]:
		largest_value = left_child

	#se verifica si el hijo derecho es mayor, actualizar variable de mayor
	#si fuera necesario
	if right_child < largoLista and lista[right_child] > lista[largest_value]:
		largest_value = right_child

	#se verifica si la posicion inicial sigue siendo la misma/mayor, swap si necesario
	#y continuar con heapify
	if largest_value != raiz:
		lista[raiz], lista[largest_value] = lista[largest_value], lista[raiz]
		heapify(lista, largo, largest_value)


maxValor=1000 	#define el valor maximo de los elementos de la lista
largoLista=1000 #define el largo de las listas a ordenar
veces=100 		#define las veces que se va a hacer el ordenamiento 

acumulaMerge=0 	#variable para acumular el tiempo de ejecucion del mergesort
acumulaHeap=0 	#variable para acumular el tiempo de ejecucion del heapsort
acumulaQuick=0 	#variable para acumular el tiempo de ejecucion del quicksort
acumulaShell=0 	#variable para acumular el tiempo de ejecucion del shellsort

for i in range(veces):
	mergelista = [randint(0,maxValor) for r in range(largoLista)] # creamos una lista con valores al azar
	heaplista = list(mergelista)
	quicklista = list(mergelista)
	searchlista = list(mergelista)

	t1 = time.process_time() 				#seteamos el tiempo al empezar
	mergeSort(mergelista) 				#ejecutamos el algoritmo mergeSort
	acumulaMerge+=time.process_time()-t1 	#acumulamos el tiempo de ejecucion

	t1 = time.process_time() 				#seteamos el tiempo al empezar
	heapSort(heaplista)					#ejecutamos el algoritmo heapSort
	acumulaHeap+=time.process_time()-t1 	#acumulamos el tiempo de ejecucion

	t1 = time.process_time() 				#seteamos el tiempo al empezar
	quickSort(quicklista,0 , len(quicklista)-1)				#ejecutamos el algoritmo quickSort
	acumulaQuick+=time.process_time()-t1 	#acumulamos el tiempo de ejecucion

	t1 = time.process_time()				#seteamos el tiempo al empezar
	shellSort(searchlista)				#ejecutamos el algoritmo shellSort
	acumulaShell+=time.process_time()-t1 	#acumulamos el tiempo de ejecucion

#imprimos los resultados
print ("Promedio de tiempo de ejecucion de "+ str(veces) +" listas de largo " + str(largoLista))
print ("MergeSort " + str(acumulaMerge/veces) + " segundos")
print ("HeapSort " + str(acumulaHeap/veces) + " segundos")
print ("QuickSort " + str(acumulaQuick/veces) + " segundos")
print ("ShellSort " + str(acumulaShell/veces) + " segundos")