#coding=utf-8

"""
Programadores:
Carlos J Corrada Bravo
Diego Rodríguez
Joel González
Javier Santiago
Luis Jusino
"""
"""
Este programa calcula el promedio de tiempo de ejecución 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 merge(lista, p, q, r):
	left = lista[p:q+1] # copy the left subarray
	right = lista[q+1:r+1] # copy the right subarray
	i = 0 # index for the left subarray
	j = 0 # index for the right subarray
	k = p # index for the sorted list

	# Keep adding to the sorted list, while both lists have elements
	while i < len(left) and j < len(right):
		if left[i] <= right[j]: 
			lista[k] = left[i]
			i += 1
		else:
			lista[k] = right[j]
			j += 1            

		k += 1

	# If right finished first, then fill up the rest with the left subarray
	while i < len(left):
		lista[k] = left[i]
		i += 1
		k += 1

	# If left finished first, then fill up the rest with the right subarray
	while j < len(right):
		lista[k] = right[j]
		j += 1
		k += 1        


def mergeSortAux(lista, p, r):
	# If array has one element or less, return
	if p >= r:
		return 
	# Else, split the array in half
	q = int((p+r)/2) # find the middle
	mergeSortAux(lista, p, q) # Sort the left subarray
	mergeSortAux(lista, q+1, r) # Sort the right subarray
	merge(lista, p, q, r) # Combine both subarrays 


def mergeSort(listaMerge):
	#definan el algoritmo de ordenamiento mergesort
	mergeSortAux(listaMerge, 0, len(listaMerge)-1)
	return listaMerge

#===============================
#Modificación a código: Diego
#Añado función heapify
#===============================
def heapify(listaHeap, largoLista, i):
	largest = i
	left = 2 * i + 1
	right = 2 * i + 2

	if left < largoLista and listaHeap[i] < listaHeap[left]:
		largest = left

	if right < largoLista and listaHeap[largest] < listaHeap[right]:
		largest = right

	if largest != i:
		listaHeap[i], listaHeap[largest] = listaHeap[largest], listaHeap[i]
		heapify(listaHeap, largoLista, largest)
#Fin de función heapify
#===============================

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

	for i in range(len(listaHeap) / 2, -1, -1):
		heapify(listaHeap, len(listaHeap), i)

	for i in range(len(listaHeap) - 1, 0, -1):
		listaHeap[i], listaHeap[0] = listaHeap[0], listaHeap[i]
		heapify(listaHeap, i, 0)
	return listaHeap

	return lista
#Se le da credito al programador de la funcion al final del codigo

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

def shellSort(lista):
	# Subarrays are sorted according to intervals
	# After each set of subarrays is sorted, interval value is updated and process repeats
	# Function stops once iteration with interval = 1 has executed
	# print(lista)
	interval = len(lista) // 2
	while interval > 0:
		# Process repeats for each value between 1 -> interval
		for i in range(0, interval):
			# Starting index determines initial portion of the array that is sorted
			sortedIndex = i
			# Process repeats as long as the current value being considered is greater than the value to its left
			# Being greater than the value to its left means that it is not in the correct location
			j = i
			while j + interval < len(lista):
				if lista[j] > lista[j + interval]:
					# Swapping values so that smaller value is to the left
					temp = lista[j]
					lista[j] = lista[j + interval]
					lista[j + interval] = temp
					# print(lista)
					n = j
					# Continue comparing value that was swapped left to other values to the left to make sure it is placed in the correct location
					while n - interval >= 0 and lista[n] < lista[n - interval]:
						# Swapping values so that smaller value is to the left
						temp = lista[n]
						lista[n] = lista[n - interval]
						lista[n - interval] = temp
						n -= interval
				# print(lista)
				# Update index to continue comparison with the next value in the sub array
				j += interval
		interval //= 2
	# print(lista)
	return lista

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):
	#Creamos una lista con valores al azar
	lista = [randint(0,maxValor) for r in range(largoLista)]

	listaMerge = lista[:]
	listaHeap = lista[:]
	listaQuick = lista[:]
	listaShell = lista[:]

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

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

	t1 = time.clock()				#seteamos el tiempo al empezar
	quickSort(listaQuick)			#ejecutamos el algoritmo quickSort
	acumulaQuick+=time.clock()-t1 	#acumulamos el tiempo de ejecucion

	t1 = time.clock()				#seteamos el tiempo al empezar
	shellSort(listaShell)			#ejecutamos el algoritmo shellSort
	acumulaShell+=time.clock()-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"