No Description

sorting.py 5.1KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161
  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 merge(lista, start, middle, end):
  12. # Create Temp arrays with specifically needed sizes foe the given array
  13. sizeOfHalf1 = middle - start + 1
  14. sizeOfHalf2 = end - middle
  15. half1 = [0] * (sizeOfHalf1)
  16. half2 = [0] * (sizeOfHalf2)
  17. # Copy data from the received array to the temporary working arrays
  18. for i in range(0, sizeOfHalf1):
  19. half1[i] = lista[start + i]
  20. for t in range(0,sizeOfHalf2):
  21. half2[t] = lista[middle + 1 + t]
  22. # Merge the temporary arrays back into the recieved list
  23. i = 0 # initial index of firs subarray
  24. t = 0 # initial index of second subarray
  25. k = start # initial index of merged subarray
  26. while i < sizeOfHalf1 and t < sizeOfHalf2:
  27. if half1[i] <= half2[t]:
  28. lista[k] = half1[i]
  29. i += 1
  30. else:
  31. lista[k] = half2[t]
  32. t += 1
  33. k += 1
  34. # Copy the remaining elements on half1 if there are any
  35. while i < sizeOfHalf1:
  36. lista[k] = half1[i]
  37. i += 1
  38. k += 1
  39. # Copy the remaining elements on half2 if there are any
  40. while t < sizeOfHalf2:
  41. lista[k] = half2[t]
  42. t += 1
  43. k += 1
  44. # start is for left index and end is the right index of the subarray
  45. # of lista to be stored
  46. def mergeSort(lista,l,r):
  47. #definan el algoritmo de ordenamiento mergesort
  48. if l < r:
  49. # Same as (l+r)//2, but avoids overflow for
  50. # large l and h
  51. m = l+(r-l)//2
  52. # Sort each half
  53. mergeSort(lista, l, m)
  54. mergeSort(lista, m+1, r)
  55. # Merge the sorted halves
  56. merge(lista, l, m, r)
  57. return lista
  58. # https://en.wikipedia.org/wiki/Heapsort
  59. def heapify(lista, n, i):
  60. largest = i
  61. l = 2 * i + 1
  62. r = 2 * i + 2
  63. if l < n and lista[i] < lista[l]:
  64. largest = l
  65. if r < n and lista[largest] < lista[r]:
  66. largest = r
  67. if largest != i:
  68. lista[i], lista[largest] = lista[largest], lista[i]
  69. heapify(lista, n, largest)
  70. def heapSort(lista):
  71. n = len(lista)
  72. for i in range(n//2, -1, -1):
  73. heapify(lista, n, i)
  74. for i in range(n-1, 0, -1):
  75. lista[i], lista[0] = lista[0], lista[i]
  76. heapify(lista, i, 0)
  77. def quickSort(lista):
  78. #definan el algoritmo de ordenamiento quicksort
  79. elements = len(lista)
  80. #Base case
  81. if elements < 2:
  82. return lista
  83. current_position = 0 #Position of the partitioning element
  84. for i in range(1, elements): #Partitioning loop
  85. if lista[i] <= lista[0]:
  86. current_position += 1
  87. temp = lista[i]
  88. lista[i] = lista[current_position]
  89. lista[current_position] = temp
  90. temp = lista[0]
  91. lista[0] = lista[current_position]
  92. lista[current_position] = temp #Brings pivot to it's appropriate position
  93. left = quickSort(lista[0:current_position]) #Sorts the elements to the left of pivot
  94. right = quickSort(lista[current_position+1:elements]) #sorts the elements to the right of pivot
  95. lista = left + [lista[current_position]] + right #Merging everything together
  96. return lista
  97. def shellSort(lista):
  98. #definan el algoritmo de ordenamiento shellsort
  99. return lista
  100. maxValor=1000 #define el valor maximo de los elementos de la lista
  101. largoLista=1000 #define el largo de las listas a ordenar
  102. veces=100 #define las veces que se va a hacer el ordenamiento
  103. acumulaMerge=0 #variable para acumular el tiempo de ejecucion del mergesort
  104. acumulaHeap=0 #variable para acumular el tiempo de ejecucion del heapsort
  105. acumulaQuick=0 #variable para acumular el tiempo de ejecucion del quicksort
  106. acumulaShell=0 #variable para acumular el tiempo de ejecucion del shellsort
  107. for i in range(veces):
  108. mergelista = [randint(0,maxValor) for r in range(largoLista)] #creamos una lista con valores al azar
  109. heaplista=list(mergelista)
  110. quicklista=list(mergelista)
  111. searchlista=list(mergelista)
  112. t1 = time.clock() #seteamos el tiempo al empezar
  113. l = 0
  114. r = len(mergelista) - 1
  115. finished = mergeSort(mergelista, l,r) #ejecutamos el algoritmo mergeSort
  116. acumulaMerge+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  117. t1 = time.clock() #seteamos el tiempo al empezar
  118. heapSort(heaplista) #ejecutamos el algoritmo heapSort
  119. acumulaHeap+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  120. t1 = time.clock() #seteamos el tiempo al empezar
  121. quickSort(quicklista) #ejecutamos el algoritmo quickSort
  122. acumulaQuick+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  123. t1 = time.clock() #seteamos el tiempo al empezar
  124. shellSort(searchlista) #ejecutamos el algoritmo shellSort
  125. acumulaShell+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  126. #imprimos los resultados
  127. print "Promedio de tiempo de ejecucion de " + str(veces) +" listas de largo " + str(largoLista)
  128. print "MergeSort " + str(acumulaMerge/veces) + " segundos"
  129. print "HeapSort " + str(acumulaHeap/veces) + " segundos"
  130. print "QuickSort " + str(acumulaQuick/veces) + " segundos"
  131. print "ShellSort " + str(acumulaShell/veces) + " segundos"