"""
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
import math

def mergeSort(lista):
	#definan el algoritmo de ordenamiento mergesort
	return lista

def MAX_HEAPIFY(lista, index):
	# funcion para mantener la propiedad lista[PARENT(i)] >= lista[i]
	# para todo nodo excepto la raiz en el heap

	 lefti = 2 * index + 1		# index hijo izquierdo
	 righti =  2 * index + 2	# index hijo derecho

	 largo = len(lista) - 1

	 # Si el hijo izq es mayor que el padre
	 if lefti <= largo and lista[lefti] > lista[index]:
	 	largest = lefti
	 else:
	 	largest = index

	 # Si el hijo derecho es mayor que el padre
	 if righti <= largo and lista[righti] > lista[largest]:
	 	largest = righti

	 # Si el index seleccionado no es el del numero mas grande
	 if largest != index:
	 	# swap de los numeros en los indexes
	 	lista[index], lista[largest] = lista[largest], lista[index]
	 	MAX_HEAPIFY(lista, largest)

def BUILD_MAX_HEAP(lista):
	largo = len(lista) - 1
	index = math.floor(largo/2)
	while index >= 1:
		MAX_HEAPIFY(lista,index)
		index = index - 1

def heapSort(lista):
	#definan el algoritmo de ordenamiento heapsort

	BUILD_MAX_HEAP(lista)
	largo = len(lista)
	while largo >= 2:
		# swap del primer numero y el ultimo
		lista[0], lista[largo-1] = lista[largo-1], lista[0]
		largo = largo - 1
		MAX_HEAPIFY(lista,0)

	return lista

def quickSort(lista):
	#definan el algoritmo de ordenamiento quicksort
	return lista

def shellSort(lista):
	#definan el algoritmo de ordenamiento shellsort
	return lista

def main():
	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.perf_counter() 				#seteamos el tiempo al empezar
		mergeSort(mergelista) 				#ejecutamos el algoritmo mergeSort
		acumulaMerge+=time.perf_counter()-t1 	#acumulamos el tiempo de ejecucion
		
		t1 = time.perf_counter()			#seteamos el tiempo al empezar
		heapSort(heaplista)					#ejecutamos el algoritmo heapSort
		acumulaHeap+=time.perf_counter()-t1 	#acumulamos el tiempo de ejecucion
		
		t1 = time.perf_counter()				#seteamos el tiempo al empezar
		quickSort(quicklista)				#ejecutamos el algoritmo quickSort
		acumulaQuick+=time.perf_counter()-t1 	#acumulamos el tiempo de ejecucion
		
		t1 = time.perf_counter()				#seteamos el tiempo al empezar
		shellSort(searchlista)				#ejecutamos el algoritmo shellSort
		acumulaShell+=time.perf_counter()-t1 	#acumulamos el tiempo de ejecucion

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

if __name__ == "__main__":
	main()