Keine Beschreibung

sorting.py 2.9KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
  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. return lista
  14. def heapSort(lista):
  15. #definan el algoritmo de ordenamiento heapsort
  16. return lista
  17. def quickSort(lista, bajo, alto):
  18. if bajo < alto:
  19. p = partition(lista, bajo, alto)
  20. quickSort(lista, bajo, p - 1)
  21. quickSort(lista, p + 1, alto)
  22. def partition(lista, bajo, alto):
  23. pivot = lista[alto]
  24. i = bajo - 1
  25. for j in range(bajo, alto):
  26. if lista[j] <= pivot:
  27. i += 1
  28. lista[i], lista[j] = lista[j], lista[i]
  29. lista[i + 1], lista[alto] = lista[alto], lista[i + 1]
  30. return i + 1
  31. def shellSort(lista):
  32. #definan el algoritmo de ordenamiento shellsort
  33. return lista
  34. maxValor=1000 #define el valor maximo de los elementos de la lista
  35. largoLista=1000 #define el largo de las listas a ordenar
  36. veces=100 #define las veces que se va a hacer el ordenamiento
  37. acumulaMerge=0 #variable para acumular el tiempo de ejecucion del mergesort
  38. acumulaHeap=0 #variable para acumular el tiempo de ejecucion del heapsort
  39. acumulaQuick=0 #variable para acumular el tiempo de ejecucion del quicksort
  40. acumulaShell=0 #variable para acumular el tiempo de ejecucion del shellsort
  41. for i in range(veces):
  42. mergelista = [randint(0,maxValor) for r in range(largoLista)] #creamos una lista con valores al azar
  43. heaplista=list(mergelista)
  44. quicklista=list(mergelista)
  45. searchlista=list(mergelista)
  46. t1 = time.clock() #seteamos el tiempo al empezar
  47. mergeSort(mergelista) #ejecutamos el algoritmo mergeSort
  48. acumulaMerge+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  49. t1 = time.clock() #seteamos el tiempo al empezar
  50. heapSort(heaplista) #ejecutamos el algoritmo heapSort
  51. acumulaHeap+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  52. t1 = time.clock() #seteamos el tiempo al empezar
  53. quickSort(quicklista) #ejecutamos el algoritmo quickSort
  54. acumulaQuick+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  55. t1 = time.clock() #seteamos el tiempo al empezar
  56. shellSort(searchlista) #ejecutamos el algoritmo shellSort
  57. acumulaShell+=time.clock()-t1 #acumulamos el tiempo de ejecucion
  58. #imprimos los resultados
  59. print "Promedio de tiempo de ejecucion de "+ str(veces) +" listas de largo " + str(largoLista)
  60. print "MergeSort " + str(acumulaMerge/veces) + " segundos"
  61. print "HeapSort " + str(acumulaHeap/veces) + " segundos"
  62. print "QuickSort " + str(acumulaQuick/veces) + " segundos"
  63. print "ShellSort " + str(acumulaShell/veces) + " segundos"