Ingen beskrivning

sorting.py 4.3KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113
  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. # If the size of the list is greater than 1 then it enters here
  14. if len(lista) > 1:
  15. # Gets the half of the list
  16. Midd = len(lista) / 2
  17. # Takes only the elements that are in the left of the list
  18. Left = lista[Midd:]
  19. # If the size of left still is not 1 then
  20. if len(Left) != 1:
  21. # it will do a recursive call to the function again
  22. mergeSort(Left)
  23. # Takes only the elements that are in the right of the list
  24. Right = lista[:Midd]
  25. # If the size of right still is not 1 then
  26. if len(Right) != 1:
  27. # it will do a recursive call to the function again
  28. mergeSort(Right)
  29. # Variables define for while and getting space in the list
  30. i = j = k = 0
  31. # While i and j are less than the comparation it enters here
  32. while i < len(Left) and j < len(Right):
  33. # If the compared number in i is less than j it enters here
  34. if Left[i] < Right[j]:
  35. # The less variable is stored in the list again in order
  36. lista[k] = Left[i]
  37. i += 1 # Increments i
  38. # If the compared number in i is greater than j it enters here
  39. else:
  40. # The less variable is stored in the list again in order
  41. lista[k] = Right[j]
  42. j += 1 # Increments j
  43. k += 1 # Increments k
  44. # If there are elements remaining in Left the they are put here
  45. while i < len(Left):
  46. # The variable that was remaining is put here
  47. lista[k] = Left[i]
  48. i += 1 # Increments i
  49. k += 1 # Increments k
  50. # If there are elements remaining in Right the they are put here
  51. while j < len(Right):
  52. # The variable that was remaining is put here
  53. lista[k] = Right[j]
  54. j += 1 # Increments j
  55. k += 1 # Increments k
  56. return lista
  57. # Code was base and taken from GeeksforGeeks
  58. def heapSort(lista):
  59. #definan el algoritmo de ordenamiento heapsort
  60. return lista
  61. def quickSort(lista):
  62. #definan el algoritmo de ordenamiento quicksort
  63. return lista
  64. def shellSort(lista):
  65. #definan el algoritmo de ordenamiento shellsort
  66. return lista
  67. maxValor=1000 #define el valor maximo de los elementos de la lista
  68. largoLista=1000 #define el largo de las listas a ordenar
  69. veces=100 #define las veces que se va a hacer el ordenamiento
  70. acumulaMerge=0 #variable para acumular el tiempo de ejecucion del mergesort
  71. acumulaHeap=0 #variable para acumular el tiempo de ejecucion del heapsort
  72. acumulaQuick=0 #variable para acumular el tiempo de ejecucion del quicksort
  73. acumulaShell=0 #variable para acumular el tiempo de ejecucion del shellsort
  74. for i in range(veces):
  75. mergelista = [randint(0,maxValor) for r in range(largoLista)] #creamos una lista con valores al azar
  76. heaplista=list(mergelista)
  77. quicklista=list(mergelista)
  78. searchlista=list(mergelista)
  79. t1 = time.clock() #seteamos el tiempo al empezar
  80. mergeSort(mergelista) #ejecutamos el algoritmo mergeSort
  81. acumulaMerge+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  82. t1 = time.clock() #seteamos el tiempo al empezar
  83. heapSort(heaplista) #ejecutamos el algoritmo heapSort
  84. acumulaHeap+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  85. t1 = time.clock() #seteamos el tiempo al empezar
  86. quickSort(quicklista) #ejecutamos el algoritmo quickSort
  87. acumulaQuick+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  88. t1 = time.clock() #seteamos el tiempo al empezar
  89. shellSort(searchlista) #ejecutamos el algoritmo shellSort
  90. acumulaShell+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  91. #imprimos los resultados
  92. print "Promedio de tiempo de ejecucion de "+ str(veces) +" listas de largo " + str(largoLista)
  93. print "MergeSort " + str(acumulaMerge/veces) + " segundos"
  94. print "HeapSort " + str(acumulaHeap/veces) + " segundos"
  95. print "QuickSort " + str(acumulaQuick/veces) + " segundos"
  96. print "ShellSort " + str(acumulaShell/veces) + " segundos"