No Description

sorting.py 3.9KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133
  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. def heapSort(lista):
  42. #definan el algoritmo de ordenamiento heapsort
  43. return lista
  44. def quickSort(lista):
  45. #definan el algoritmo de ordenamiento quicksort
  46. return lista
  47. def insertionSort(lista):
  48. i = 1
  49. while i < len(lista):
  50. if lista[i - 1] > lista[i]:
  51. j = i - 1
  52. while j >= 0 and lista[j] > lista[j + 1]:
  53. lista[j], lista[j + 1] = lista[j + 1], lista[j]
  54. j -= 1
  55. i += 1
  56. return lista
  57. def shellSort(lista):
  58. gap = len(lista) / 2
  59. while gap >= 1:
  60. i = gap
  61. while i < len(lista):
  62. if lista[i - gap] > lista[i]:
  63. j = i - gap
  64. while j >= 0 and lista[j] > lista[j + gap]:
  65. lista[j], lista[j + gap] = lista[j + gap], lista[j]
  66. j -= gap
  67. i += gap
  68. gap /= 2
  69. #if isSorted(lista):
  70. #print "Lista is sorted"
  71. #else:
  72. #print "Lista is not sorted"
  73. return lista
  74. maxValor=1000 #define el valor maximo de los elementos de la lista
  75. largoLista=1000 #define el largo de las listas a ordenar
  76. veces=100 #define las veces que se va a hacer el ordenamiento
  77. acumulaMerge=0 #variable para acumular el tiempo de ejecucion del mergesort
  78. acumulaHeap=0 #variable para acumular el tiempo de ejecucion del heapsort
  79. acumulaQuick=0 #variable para acumular el tiempo de ejecucion del quicksort
  80. acumulaShell=0 #variable para acumular el tiempo de ejecucion del shellsort
  81. for i in range(veces):
  82. lista = [randint(0,maxValor) for r in range(largoLista)] #creamos una lista con valores al azar
  83. # creamos copias de la lista para cada algoritmo
  84. listaMerge = lista[:]
  85. listaHeap = lista[:]
  86. listaQuick = lista[:]
  87. listaShell = lista[:]
  88. t1 = time.clock() #seteamos el tiempo al empezar
  89. mergeSort(listaMerge) #ejecutamos el algoritmo mergeSort
  90. acumulaMerge+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  91. t1 = time.clock() #seteamos el tiempo al empezar
  92. heapSort(listaHeap) #ejecutamos el algoritmo heapSort
  93. acumulaHeap+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  94. t1 = time.clock() #seteamos el tiempo al empezar
  95. quickSort(listaQuick) #ejecutamos el algoritmo quickSort
  96. acumulaQuick+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  97. t1 = time.clock() #seteamos el tiempo al empezar
  98. shellSort(listaShell) #ejecutamos el algoritmo shellSort
  99. acumulaShell+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  100. #imprimos los resultados
  101. print "Promedio de tiempo de ejecucion de "+ str(veces) +" listas de largo " + str(largoLista)
  102. print "MergeSort " + str(acumulaMerge/veces) + " segundos"
  103. print "HeapSort " + str(acumulaHeap/veces) + " segundos"
  104. print "QuickSort " + str(acumulaQuick/veces) + " segundos"
  105. print "ShellSort " + str(acumulaShell/veces) + " segundos"