No Description

sorting.py 3.3KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
  1. """
  2. Carlos J Corrada Bravo
  3. Este programa calcula el promedio de tiempo de ejecucion de cuatro algoritmos de ordenamiento
  4. La variable maxValor define el valor maximo de los elementos de la lista
  5. La variable largoLista define el largo de las listas a ordenar
  6. La variable veces define las veces que se va a hacer el ordenamiento
  7. Al final se imprimen los promedios de cada algortimo
  8. """
  9. from random import randint
  10. import time
  11. def mergeSort(lista):
  12. #definan el algoritmo de ordenamiento mergesort
  13. return lista
  14. def heapSort(lista):
  15. #definan el algoritmo de ordenamiento heapsort
  16. #Andrea V. Nieves
  17. #function def
  18. def heapify(lista, n, i):
  19. biggest = i
  20. left = 2*i + 1
  21. right = 2*i + 2
  22. if left < n and lista[left] > lista[i]:
  23. biggest = left
  24. else:
  25. biggest = i
  26. if right< n and lista[right] > lista[biggest]:
  27. biggest = right
  28. if biggest != i:
  29. lista[i], lista[biggest] = lista[biggest], lista[i]
  30. heapify(lista,n,biggest)
  31. #actual call
  32. n = len(lista)
  33. for i in range(n // 2 - 1, -1, -1):
  34. heapify(lista, n, i)
  35. for i in range(n - 1, 0, -1):
  36. lista[i], lista[0] = lista[0], lista[i]
  37. heapify(lista, i, 0)
  38. return lista
  39. def quickSort(lista):
  40. #definan el algoritmo de ordenamiento quicksort
  41. return lista
  42. def shellSort(lista):
  43. #definan el algoritmo de ordenamiento shellsort
  44. return lista
  45. maxValor=1000 #define el valor maximo de los elementos de la lista
  46. largoLista=1000 #define el largo de las listas a ordenar
  47. veces=100 #define las veces que se va a hacer el ordenamiento
  48. acumulaMerge=0 #variable para acumular el tiempo de ejecucion del mergesort
  49. acumulaHeap=0 #variable para acumular el tiempo de ejecucion del heapsort
  50. acumulaQuick=0 #variable para acumular el tiempo de ejecucion del quicksort
  51. acumulaShell=0 #variable para acumular el tiempo de ejecucion del shellsort
  52. for i in range(veces):
  53. mergelista = [randint(0,maxValor) for r in range(largoLista)] #creamos una lista con valores al azar
  54. heaplista=list(mergelista)
  55. quicklista=list(mergelista)
  56. searchlista=list(mergelista)
  57. t1 = time.clock() #seteamos el tiempo al empezar
  58. mergeSort(mergelista) #ejecutamos el algoritmo mergeSort
  59. acumulaMerge+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  60. t1 = time.clock() #seteamos el tiempo al empezar
  61. heapSort(heaplista) #ejecutamos el algoritmo heapSort
  62. acumulaHeap+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  63. t1 = time.clock() #seteamos el tiempo al empezar
  64. quickSort(quicklista) #ejecutamos el algoritmo quickSort
  65. acumulaQuick+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  66. t1 = time.clock() #seteamos el tiempo al empezar
  67. shellSort(searchlista) #ejecutamos el algoritmo shellSort
  68. acumulaShell+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  69. #imprimos los resultados
  70. print "Promedio de tiempo de ejecucion de "+ str(veces) +" listas de largo " + str(largoLista)
  71. print "MergeSort " + str(acumulaMerge/veces) + " segundos"
  72. print "HeapSort " + str(acumulaHeap/veces) + " segundos"
  73. print "QuickSort " + str(acumulaQuick/veces) + " segundos"
  74. print "ShellSort " + str(acumulaShell/veces) + " segundos"