No Description

sorting.py 6.5KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209
  1. # -*- coding: utf-8 -*-
  2. """
  3. Carlos J Corrada Bravo
  4. Este programa calcula el promedio de tiempo de ejecución de cuatro algoritmos de ordenamiento
  5. La variable maxValor define el valor maximo de los elementos de la lista
  6. La variable largoLista define el largo de las listas a ordenar
  7. La variable veces define las veces que se va a hacer el ordenamiento
  8. Al final se imprimen los promedios de cada algortimo
  9. """
  10. from random import randint
  11. import time
  12. def isSorted(lista):
  13. return lista == sorted(lista)
  14. def mergeSort(lista):
  15. if len(lista)>1:
  16. mitad = len(lista)//2
  17. izq = lista[:mitad]
  18. der = lista[mitad:]
  19. mergeSort(izq)
  20. mergeSort(der)
  21. idx_izq = 0
  22. idx_der = 0
  23. idx_lista = 0
  24. while idx_izq < len(izq) and idx_der < len(der):
  25. if izq[idx_izq] <= der[idx_der]:
  26. lista[idx_lista] = izq[idx_izq]
  27. idx_izq += 1
  28. else:
  29. lista[idx_lista] = der[idx_der]
  30. idx_der += 1
  31. idx_lista += 1
  32. while idx_izq < len(izq):
  33. lista[idx_lista] = izq[idx_izq]
  34. idx_izq +=1
  35. idx_lista +=1
  36. while idx_der < len(der):
  37. lista[idx_lista] = der[idx_der]
  38. idx_der += 1
  39. idx_lista += 1
  40. return lista
  41. """La siguiente implementación del algoritmo 'Heapsort'
  42. fue implementada por Miguel E. Cruz Molina, siguiendo
  43. el diseño propuesto en el libro 'Introduction to
  44. Algorithms' (2009, 3rd ed.), de Cormen, T. H. et al."""
  45. def heapSort(lista):
  46. """Esta función toma una lista de números y los ordena
  47. usando el algoritmo 'heapsort', que repetitivamente
  48. convierte a los elementos no-ordenados en un montículo
  49. maximal y sustituye el elemento mayor por el último."""
  50. # El algoritmo primero genera un montículo maximal
  51. # con los elementos en la lista:
  52. buildHeap(lista, len(lista) - 1)
  53. # Por cada uno de los elementos en la lista,
  54. for i in range(len(lista) - 1, 0, -1):
  55. # Se sustituye el elemento en la raíz del montículo
  56. # (el elemento más grande) con el último,
  57. print(lista)
  58. temp = lista[i]
  59. lista[i] = lista[0]
  60. lista[0] = temp
  61. print(lista)
  62. # Y se genera un montículo con los elementos
  63. # restantes, hasta terminar con la lista ordenada.
  64. buildHeap(lista, i)
  65. return lista
  66. def buildHeap(lista, heapsize):
  67. """Esta función toma a una lista de números y la
  68. convierte en una representación lineal de un montículo
  69. maximal, i.e. un árbol binario en el que el contenido
  70. de todo nodo padre (de índice k) es mayor al de sus
  71. hijos (de índices 2k + 1 y 2k + 2). Este proceso se
  72. realiza recursivamente, desde el penúltimo 'nivel'
  73. del árbol hasta la raíz, usando la función auxiliar
  74. 'maxHeapify()'. """
  75. for i in range((heapsize-1)//2, -1, -1):
  76. maxHeapify(lista, i, heapsize)
  77. def maxHeapify(lista, k, heapsize):
  78. """Esta función tiene como propósito garantizar que
  79. la propiedad maximal de un montículo se conserve,
  80. intercambiando el valor de un nodo padre por el mayor
  81. valor de entre sus nodos hijos de ser necesario, y
  82. aplicando el mismo algoritmo sobre el subárbol de ese
  83. hijo de forma recursiva. La función recibe tres
  84. argumentos: la lista que contiene el montículo,
  85. el índice de la raíz del montículo a considerarse,
  86. y el límite del montículo mayor, que no necesariamente
  87. es equivalente al largo de la lista."""
  88. # Primero se identifican los índices hipotéticos
  89. # de los nodos hijos:
  90. l = 2 * k + 1; r = 2 * k + 2; max = k
  91. # Identificar cuál de los tres nodos tiene el mayor
  92. # valor.
  93. if l < heapsize and lista[max] < lista[l]: max = l
  94. if r < heapsize and lista[max] < lista[r]: max = r
  95. # Si el nodo padre no es el mayor, intercambiarlo
  96. # por el nodo hijo con mayor valor, y llamar la
  97. # función de modo recursivo sobre el subárbol de
  98. # ese hijo.
  99. if max != k:
  100. temp = lista[k]
  101. lista[k] = lista[max]
  102. lista[max] = temp
  103. maxHeapify(lista, max, heapsize)
  104. def quickSort(lista):
  105. #definan el algoritmo de ordenamiento quicksort
  106. return lista
  107. def insertionSort(lista):
  108. i = 1
  109. while i < len(lista):
  110. if lista[i - 1] > lista[i]:
  111. j = i - 1
  112. while j >= 0 and lista[j] > lista[j + 1]:
  113. lista[j], lista[j + 1] = lista[j + 1], lista[j]
  114. j -= 1
  115. i += 1
  116. return lista
  117. def shellSort(lista):
  118. gap = len(lista) / 2
  119. while gap >= 1:
  120. i = gap
  121. while i < len(lista):
  122. if lista[i - gap] > lista[i]:
  123. j = i - gap
  124. while j >= 0 and lista[j] > lista[j + gap]:
  125. lista[j], lista[j + gap] = lista[j + gap], lista[j]
  126. j -= gap
  127. i += gap
  128. gap /= 2
  129. #if isSorted(lista):
  130. #print "Lista is sorted"
  131. #else:
  132. #print "Lista is not sorted"
  133. return lista
  134. maxValor=1000 #define el valor maximo de los elementos de la lista
  135. largoLista=1000 #define el largo de las listas a ordenar
  136. veces=100 #define las veces que se va a hacer el ordenamiento
  137. acumulaMerge=0 #variable para acumular el tiempo de ejecucion del mergesort
  138. acumulaHeap=0 #variable para acumular el tiempo de ejecucion del heapsort
  139. acumulaQuick=0 #variable para acumular el tiempo de ejecucion del quicksort
  140. acumulaShell=0 #variable para acumular el tiempo de ejecucion del shellsort
  141. for i in range(veces):
  142. lista = [randint(0,maxValor) for r in range(largoLista)] #creamos una lista con valores al azar
  143. # creamos copias de la lista para cada algoritmo
  144. listaMerge = lista[:]
  145. listaHeap = lista[:]
  146. listaQuick = lista[:]
  147. listaShell = lista[:]
  148. t1 = time.clock() #seteamos el tiempo al empezar
  149. mergeSort(listaMerge) #ejecutamos el algoritmo mergeSort
  150. acumulaMerge+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  151. t1 = time.clock() #seteamos el tiempo al empezar
  152. heapSort(listaHeap) #ejecutamos el algoritmo heapSort
  153. acumulaHeap+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  154. t1 = time.clock() #seteamos el tiempo al empezar
  155. quickSort(listaQuick) #ejecutamos el algoritmo quickSort
  156. acumulaQuick+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  157. t1 = time.clock() #seteamos el tiempo al empezar
  158. shellSort(listaShell) #ejecutamos el algoritmo shellSort
  159. acumulaShell+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  160. #imprimos los resultados
  161. print "Promedio de tiempo de ejecucion de "+ str(veces) +" listas de largo " + str(largoLista)
  162. print "MergeSort " + str(acumulaMerge/veces) + " segundos"
  163. print "HeapSort " + str(acumulaHeap/veces) + " segundos"
  164. print "QuickSort " + str(acumulaQuick/veces) + " segundos"
  165. print "ShellSort " + str(acumulaShell/veces) + " segundos"