123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117 |
- """
- 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):
- #definan el algoritmo de ordenamiento heapsort
- return lista
-
- def quickSort(lista):
- #definan el algoritmo de ordenamiento quicksort
- 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
- mergeSort(mergelista) #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"
|