"""
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 merge(lista, start, middle, end):
	# Create Temp arrays with specifically needed sizes foe the given array
	sizeOfHalf1 = middle - start + 1
	sizeOfHalf2 = end - middle
	half1 = [0] * (sizeOfHalf1)
	half2 = [0] * (sizeOfHalf2)
    # Copy data from the received array to the temporary working arrays
	for i in range(0, sizeOfHalf1):
		half1[i] = lista[start + i]
	for t in range(0,sizeOfHalf2):
		half2[t] = lista[middle + 1 + t] 
	
	# Merge the temporary arrays back into the recieved list
	i = 0 # initial index of firs subarray 
	t = 0 # initial index of second subarray
	k = start # initial index of merged subarray

	while i < sizeOfHalf1 and t < sizeOfHalf2:
		if half1[i] <= half2[t]:
			lista[k] = half1[i]
			i += 1
		else:
			lista[k] = half2[t]
			t += 1
		k += 1
	# Copy the remaining elements on half1 if there are any
	while i < sizeOfHalf1:
		lista[k] = half1[i]
		i += 1
		k += 1

	# Copy the remaining elements on half2 if there are any
	while t < sizeOfHalf2:
		lista[k] = half2[t]
		t += 1
		k += 1

# start is for left index and end is the right index of the subarray
# of lista to be stored 

def mergeSort(lista,l,r):
	#definan el algoritmo de ordenamiento mergesort
	if l < r:
		# Same as (l+r)//2, but avoids overflow for
        # large l and h
		m = l+(r-l)//2

		# Sort each half
		mergeSort(lista, l, m)
		mergeSort(lista, m+1, r)
		# Merge the sorted halves
		merge(lista, l, m, r)

	return lista

# https://en.wikipedia.org/wiki/Heapsort
def heapify(lista, n, i):
	largest = i
	l = 2 * i + 1
	r = 2 * i + 2
	if l < n and lista[i] < lista[l]:
		largest = l
	if r < n and lista[largest] < lista[r]:
		largest = r
	if largest != i:
		lista[i], lista[largest] = lista[largest], lista[i]
		heapify(lista, n, largest)

def heapSort(lista):
	n = len(lista)

	for i in range(n//2, -1, -1):
		heapify(lista, n, i)

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

def quickSort(lista):
    #definan el algoritmo de ordenamiento quicksort
    elements = len(lista)

    #Base case
    if elements < 2:
        return lista

    current_position = 0 #Position of the partitioning element

    for i in range(1, elements): #Partitioning loop
         if lista[i] <= lista[0]:
              current_position += 1
              temp = lista[i]
              lista[i] = lista[current_position]
              lista[current_position] = temp

    temp = lista[0]
    lista[0] = lista[current_position]
    lista[current_position] = temp #Brings pivot to it's appropriate position

	left = quickSort(lista[0:current_position]) #Sorts the elements to the left of pivot
	right = quickSort(lista[current_position+1:elements]) #sorts the elements to the right of pivot

	lista = left + [lista[current_position]] + right #Merging everything together
    
	return lista

def shellSort(lista):
	#definan el algoritmo de ordenamiento shellsort
	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):
	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.clock() 				#seteamos el tiempo al empezar
	l = 0
	r = len(mergelista) - 1
	finished = mergeSort(mergelista, l,r) 				#ejecutamos el algoritmo mergeSort
	acumulaMerge+=time.clock()-t1 	#acumulamos el tiempo de ejecucion
	
	t1 = time.clock()				#seteamos el tiempo al empezar
	heapSort(heaplista)					#ejecutamos el algoritmo heapSort
	acumulaHeap+=time.clock()-t1 	#acumulamos el tiempo de ejecucion
	
	t1 = time.clock()				#seteamos el tiempo al empezar
	quickSort(quicklista)				#ejecutamos el algoritmo quickSort
	acumulaQuick+=time.clock()-t1 	#acumulamos el tiempo de ejecucion
	
	t1 = time.clock()				#seteamos el tiempo al empezar
	shellSort(searchlista)				#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"