No Description

sorting.py 6.1KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184
  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. import utils.qsortUtils as qsortUtils
  12. def mergeSort(lista):
  13. #definan el algoritmo de ordenamiento mergesort
  14. # If the size of the list is greater than 1 then it enters here
  15. if len(lista) > 1:
  16. # Gets the half of the list
  17. Midd = len(lista) // 2
  18. # Takes only the elements that are in the left of the list
  19. Left = lista[Midd:]
  20. # If the size of left still is not 1 then
  21. if len(Left) != 1:
  22. # it will do a recursive call to the function again
  23. mergeSort(Left)
  24. # Takes only the elements that are in the right of the list
  25. Right = lista[:Midd]
  26. # If the size of right still is not 1 then
  27. if len(Right) != 1:
  28. # it will do a recursive call to the function again
  29. mergeSort(Right)
  30. # Variables define for while and getting space in the list
  31. i = j = k = 0
  32. # While i and j are less than the comparation it enters here
  33. while i < len(Left) and j < len(Right):
  34. # If the compared number in i is less than j it enters here
  35. if Left[i] < Right[j]:
  36. # The less variable is stored in the list again in order
  37. lista[k] = Left[i]
  38. i += 1 # Increments i
  39. # If the compared number in i is greater than j it enters here
  40. else:
  41. # The less variable is stored in the list again in order
  42. lista[k] = Right[j]
  43. j += 1 # Increments j
  44. k += 1 # Increments k
  45. # If there are elements remaining in Left the they are put here
  46. while i < len(Left):
  47. # The variable that was remaining is put here
  48. lista[k] = Left[i]
  49. i += 1 # Increments i
  50. k += 1 # Increments k
  51. # If there are elements remaining in Right the they are put here
  52. while j < len(Right):
  53. # The variable that was remaining is put here
  54. lista[k] = Right[j]
  55. j += 1 # Increments j
  56. k += 1 # Increments k
  57. return lista
  58. # Code was base and taken from GeeksforGeeks
  59. def MAX_HEAPIFY(lista, index, largo):
  60. # funcion para mantener la propiedad lista[PARENT(i)] >= lista[i]
  61. # para todo nodo excepto la raiz en el heap
  62. largest = index
  63. lefti = 2 * index + 1 # index hijo izquierdo
  64. righti = 2 * index + 2 # index hijo derecho
  65. # Si el hijo izq es mayor que el padre
  66. if lefti < largo and lista[lefti] > lista[largest]:
  67. largest = lefti
  68. # Si el hijo derecho es mayor que el padre
  69. if righti < largo and lista[righti] > lista[largest]:
  70. largest = righti
  71. # Si el index seleccionado no es el del numero mas grande
  72. if largest != index:
  73. # swap de los numeros en los indexes
  74. lista[index], lista[largest] = lista[largest], lista[index]
  75. MAX_HEAPIFY(lista, largest, largo)
  76. def BUILD_MAX_HEAP(lista, largo):
  77. index = largo//2 - 1
  78. while index > -1:
  79. MAX_HEAPIFY(lista,index,largo)
  80. index -= 1
  81. def heapSort(lista):
  82. #definan el algoritmo de ordenamiento heapsort
  83. largo = len(lista)
  84. BUILD_MAX_HEAP(lista, largo)
  85. while largo > 0:
  86. # swap del primer numero y el ultimo
  87. lista[0], lista[largo-1] = lista[largo-1], lista[0]
  88. largo -= 1
  89. MAX_HEAPIFY(lista,0,largo)
  90. return lista
  91. def quickSort(lista):
  92. # Se aplica quicksort a la lista desde el primer elemento hasta el último
  93. qsortUtils.qSort(lista, 0, len(lista) - 1)
  94. return lista
  95. def shellSort(lista):
  96. #definan el algoritmo de ordenamiento shellsort
  97. Size = len(lista) # Contains the complete size of the list
  98. Diff = Size//2 # Contains the number of half of the list
  99. # Does a insertion sort by ordering in base of the Diff.
  100. while Diff > 0:
  101. # Begins a loop to sort the elements added to sorted array.
  102. for i in range(Diff, Size):
  103. # Saves the element sorted in a temporary variable
  104. Tmp = lista[i]
  105. j = i # Shifts the location of the elements
  106. # Looks for the locations
  107. while j >= Diff and lista[j - Diff] > Tmp:
  108. # Gives the new element to the location
  109. lista[j] = lista[j - Diff]
  110. # The size of the array is ajusted
  111. j -= Diff
  112. # Puts the Tmp variable in is correct location
  113. lista[j] = Tmp
  114. # Reduces again the list
  115. Diff //= 2
  116. return lista
  117. # Code was taken from GeeksforGeeks
  118. def main():
  119. maxValor=1000 #define el valor maximo de los elementos de la lista
  120. largoLista=1000 #define el largo de las listas a ordenar
  121. veces=100 #define las veces que se va a hacer el ordenamiento
  122. acumulaMerge=0 #variable para acumular el tiempo de ejecucion del mergesort
  123. acumulaHeap=0 #variable para acumular el tiempo de ejecucion del heapsort
  124. acumulaQuick=0 #variable para acumular el tiempo de ejecucion del quicksort
  125. acumulaShell=0 #variable para acumular el tiempo de ejecucion del shellsort
  126. for i in range(veces):
  127. mergelista = [randint(0,maxValor) for r in range(largoLista)] #creamos una lista con valores al azar
  128. heaplista=list(mergelista)
  129. quicklista=list(mergelista)
  130. searchlista=list(mergelista)
  131. t1 = time.perf_counter() #seteamos el tiempo al empezar
  132. mergeSort(mergelista) #ejecutamos el algoritmo mergeSort
  133. acumulaMerge+=time.perf_counter()-t1 #acumulamos el tiempo de ejecucion
  134. t1 = time.perf_counter() #seteamos el tiempo al empezar
  135. heapSort(heaplista) #ejecutamos el algoritmo heapSort
  136. acumulaHeap+=time.perf_counter()-t1 #acumulamos el tiempo de ejecucion
  137. t1 = time.perf_counter() #seteamos el tiempo al empezar
  138. quickSort(quicklista) #ejecutamos el algoritmo quickSort
  139. acumulaQuick+=time.perf_counter()-t1 #acumulamos el tiempo de ejecucion
  140. t1 = time.perf_counter() #seteamos el tiempo al empezar
  141. shellSort(searchlista) #ejecutamos el algoritmo shellSort
  142. acumulaShell+=time.perf_counter()-t1 #acumulamos el tiempo de ejecucion
  143. #imprimos los resultados
  144. print (f"Promedio de tiempo de ejecucion de {veces} listas de largo {largoLista}")
  145. print (f"MergeSort {str(acumulaMerge/veces)} segundos")
  146. print (f"HeapSort {str(acumulaHeap/veces)} segundos")
  147. print (f"QuickSort {str(acumulaQuick/veces)} segundos")
  148. print (f"ShellSort {str(acumulaShell/veces) }segundos")
  149. if __name__ == "__main__":
  150. main()