Created
June 4, 2012 17:03
-
-
Save zerohours/2869551 to your computer and use it in GitHub Desktop.
Cálculo del tiempo en ordenar una lista
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python | |
# -*- coding: utf-8 -*- | |
# | |
# tiempo.py | |
# Cálculo del tiempo de ordenameinto de lista | |
# | |
import time | |
import random | |
def cronometro(funcion): | |
def funcion_a_ejecutar(*argumentos): | |
# Tiempo de inicio de ejecución. | |
inicio = time.time() | |
# Lanzamos función a ejecutar. | |
ret = funcion(*argumentos) | |
# Tiempo de fin de ejecución. | |
fin = time.time() | |
# Tiempo de ejecución. | |
tiempo_total = fin - inicio | |
# Devolvemos el tiempo de ejecución. | |
return tiempo_total | |
# Devolvemos la función que se ejecuta. | |
return funcion_a_ejecutar | |
def funcion_generica(): | |
lista_numeros = [] | |
for i in range(1,100000000): | |
numero = int(random.uniform(0,500)) | |
lista_numeros.append(numero) | |
# Devolvemos lista de números aleatorios. | |
return lista_numeros | |
def quicksort(datos, primero, ultimo, ordenacion = 'asc'): | |
''' | |
Método que implementa el algoritmo QuickSort. Utilizado | |
para clasificación de filas. | |
''' | |
i = primero | |
j = ultimo | |
posicion_pivote = (primero + ultimo) / 2 | |
pivote = datos[posicion_pivote] | |
while i <= j: | |
if ordenacion == 'asc': | |
while datos[i] < pivote: i+=1 | |
while datos[j] > pivote: j-=1 | |
if ordenacion == 'desc': | |
while datos[i] > pivote: i+=1 | |
while datos[j] < pivote: j-=1 | |
if i <= j: | |
aux = datos[i] | |
datos[i] = datos[j] | |
datos[j] = aux | |
i+=1 | |
j-=1 | |
if primero < j: | |
datos = quicksort(datos, primero, j, ordenacion) | |
if ultimo > i: | |
datos = quicksort(datos, i, ultimo, ordenacion) | |
return datos | |
def main(): | |
lista_numeros = funcion_generica() | |
tiempo1 = cronometro(quicksort)(lista_numeros,0,99998) | |
tiempo2 = cronometro(quicksort)(lista_numeros,0,99998,'desc') | |
tiempo3 = cronometro(quicksort)(lista_numeros,0,99998) | |
print "Cálculo total de tiempos del algoritmo QuickSort" | |
print "Se ordena una lista de 99999 elementos." | |
print "" | |
print "Lista no ordenada: ", tiempo1, " segundos" | |
print "Lista ordenada ascendente: ", tiempo2, " segundos" | |
print "Lista ordenada descendente: ", tiempo3, " segundos" | |
return 0 | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment