• Jueves 30 de Octubre de 2014, 15:23

Autor Tema: [Código Fuente] Tiempo de ejecución métodos de búsqueda: BUBBLE - MERGE - QUICK SORT  (Leído 1837 veces)

luis.bmw2000

  • Nuevo Miembro
  • *
  • Mensajes: 1
    • Ver Perfil
[Código Fuente] Tiempo de ejecución métodos de búsqueda: BUBBLE - MERGE - QUICK SORT
« en: Sábado 2 de Abril de 2011, 10:31 »
0

Publicidad 
Soy nuevo en lenguaje Python. He tenido experiencia anteriormente en lenguaje C C++ y lex pero ahora me gustaria expandirme un poco mas hacia lo que es Python y sus caracteristicas.

El codigo a mostrar ordena arreglos de cualquier tamanio (uno mismo lo indica) pero ademas de ordenarlos indica el tiempo que demoro en hacerlo guardandolo en un archivo .txt.

Se guarda algo asi:

.txt
[largo_del_arreglo] [tiempo_demorado]

Pues cualquier acotacion mejora o concejo al codigo lo recibire de la mejor manera.
Gracias y comenten harto

Código: [Seleccionar]
# -*- coding: utf-8 -*-

#Carrera:      Licenciatura en Ciencias de la Computación
#Universidad:    Universidad de Santiago de Chile
#Fecha:        02/04/2011

#función que genera número aleatorios
def generador_numeros ():
  y = random.randint (-50005000)
  return y
 
#función que ordena arreglo con el método de bubble sort
def bubble_orden (lista max):
  for n in lista:
    pos = 0
    for i in range (1 max):
      pos = lista[i]
      if lista[i] < lista[i-1]:
        lista[i] = lista[i-1]
        lista[i-1] = pos
       
#función que ordena arreglo con el método de merge sort
def merge_orden (lista inicio ultimo):
  if inicio < ultimo:
    medio = (inicio + ultimo)/2
    merge_orden (lista inicio medio)
    merge_orden (lista medio + 1 ultimo)
    merge (lista inicio ultimo medio)
   
#función que apoya a método merge sort
def merge (lista inicio ultimo medio):
  lista_ayuda = []
  i = inicio
  j = medio + 1
  while i <= medio and j <= ultimo:
    if lista [i] <= lista [j]:
      lista_ayuda.append (lista[i])
      i += 1
    else:
      lista_ayuda.append (lista [j])
      j += 1
  while i <= medio:
    lista_ayuda.append (lista[i])
    i +=1
  while j <= ultimo:
    lista_ayuda.append (lista[j])
    j += 1
  for k in range (0 ultimo - inicio + 1):
    lista[inicio + k] = lista_ayuda [k]
   
#función que ordena arreglo con el método de quick sort
def quick_orden (lista izdo dcho) :
  if izdo < dcho:
    pivote = lista[(izdo+dcho)/2]
    i = izdo
    d = dcho
    while i <= d:
      while lista[i] < pivote:
        i+=1
      while lista[d] > pivote:
        d-=1
      if i <= d:
        lista[i]lista[d]=lista[d]lista[i]
        i+=1
        d-=1
    if izdo    if i  return lista
 
#comienza codigo
#se usa "time" para poder calcular tiempos de demora de código
import time
#se usa "random" para poder generar números aleatorios entre cierto intervalo
import random
#se abre acceso a archivos en modo: "agregar al final del archivo"
archivo1 = open("bubble_graficar.txt" "a");
archivo2 = open("merge_graficar.txt" "a");
archivo3 = open("quick_graficar.txt" "a");
#cabe destacar que la forma en que se envian los datos a cada archivo salen en el siguiente formato:
#[largo_del_arreglo] [tiempo_promediado_de_las_10_pruebas]
#se generan las listas vací­as cada una para ser ordenada por cada método
lista1 = []
lista2 = []
lista3 = []
#se asigna un valor 1 válido solo para poder entrar a "while"
largo = 1
print "**************PROGRAMA QUE CALCULA TIEMPO QUE DEMORAN MÉTODOS EN ORDENAR ARREGLOS**************\n"
while 0 < largo:
  #consulta a usuario el largo del arreglo (común para todos los métodos) cada vez que sale del ciclo "while cte < 10:"
  print " Largo del arreglo (si ingresas un número menor a 1 es SALIR):"
  largo = input()
  #se asigna "cte=0" para llevar la cuenta de las 10 tomas de datos diferentes y reinicia valores después de salir del ciclo "while cte < 10:"
  cte = 0
  #se asignan valores previamente a las variables que se usarán para promediar los casos a analizar y reinicia valores después de salir del ciclo "while cte < 10:"
  suma_bubble = 0
  suma_merge = 0
  suma_quick = 0
  #dependiendo del valor que adquiera "largo" será el largo que tenga el arreglo pero si se ingresa un valor menor a 1 se dará por terminado el programa
  if 1 <= largo:
    #ciclo que ayuda a tomar 10 muestras diferentes de datos
    while cte < 10:
      print "\n  Vuelta Nº" + str(cte+1)
     
      #ciclo que ayuda llenar cada arreglo
      for i in range (largo):
        valor = generador_numeros ()
        #función del sistema "append" ayuda agregar un valor al final del arreglo
        lista1.append (valor)
        lista2.append (valor)
        lista3.append (valor)
      #------------------bubble sort
      #se toma segundo del sistema y se guarda en variable "t_inicial"
      t_inicial = time.time ()
      #se llama a ordenar por bubble sort
      bubble_orden (lista1 largo)
      #se toma segundo del sistema y se guarda en variable "t_final"
      t_final = time.time ()
      #se calcula tiempo de ejecución de función "bubble_orden" y se guarda en variable "t_trans"
      t_trans = t_final - t_inicial
      print "   El tiempo transcurrido en ordenar por bubble-sort es de: %f" % t_trans  "seg(s)."
      #variable que guarda suma de los 10 tiempos a analizar
      suma_bubble = suma_bubble + t_trans
      #si se cumplen 10 ciclos podemos entrar a enviar el promedio de la variable "suma_bubble" a archivo especificado
      if cte == 9:
        suma_bubble = suma_bubble/10
        archivo1.write("%d" % largo +" %f\n" % suma_bubble)
      #------------------merge sort
      #se toma segundo del sistema y se guarda en variable "t_inicial"
      t_inicial = time.time ()
      #se llama a ordenar por merge sort
      merge_orden (lista2 0 largo-1)
      #se toma segundo del sistema y se guarda en variable "t_final"
      t_final = time.time ()
      #se calcula tiempo de ejecución de función "merge_orden" y se guarda en variable "t_trans"
      t_trans = t_final - t_inicial
      print "   El tiempo transcurrido en ordenar por merge-sort es de: %f" % t_trans  "seg(s)."
      #variable que guarda suma de los 10 tiempos a analizar
      suma_merge = suma_merge + t_trans
      #si se cumplen 10 ciclos podemos entrar a enviar el promedio de la variable "merge_bubble" a archivo especificado
      if cte == 9:
        suma_merge = suma_merge/10
        archivo2.write("%d" % largo +" %f\n" % suma_merge)
      #------------------quick sort
      #se toma segundo del sistema y se guarda en variable "t_inicial"
      t_inicial = time.time ()
      #se llama a ordenar por quick sort
      quick_orden (lista3 0 largo-1)
      #se toma segundo del sistema y se guarda en variable "t_final"
      t_final = time.time ()
      #se calcula tiempo de ejecución de función "quick_orden" y se guarda en variable "t_trans"
      t_trans = t_final - t_inicial
      print "   El tiempo transcurrido en ordenar por quick-sort es de: %f" % t_trans  "seg(s)."
      #variable que guarda suma de los 10 tiempos a analizar
      suma_quick = suma_quick + t_trans
      #si se cumplen 10 ciclos podemos entrar a enviar el promedio de la variable "quick_bubble" a archivo especificado
      if cte == 9:
        suma_quick = suma_quick/10
        archivo3.write("%d" % largo +" %f\n" % suma_quick)
      #al terminar cada ciclo se vacía cada lista para poder llenarlas con nuevos datos aleatorios
      list([lista1.pop() for z in xrange(len(lista1))])
      list([lista2.pop() for z in xrange(len(lista2))])
      list([lista3.pop() for z in xrange(len(lista3))])
      #si se cumplen 10 ciclos imprimimos el promedio que se envió a cada archivo
      if cte == 9:
        print "\t----------------------------------------------------------------------------------------------------------------------------------------------------------------"
        print "\t-->\tEl promedio del tiempo demorado de 10 muestras por el método BUBBLE ha sido agregado al archivo: \"bubble_graficar.txt\"  (%f" % suma_bubble  " seg(s).)"
        print "\t-->\tEl promedio del tiempo demorado de 10 muestras por el método MERGE ha sido agregado al archivo: \"merge_graficar.txt\"    (%f" % suma_merge  " seg(s).)"
        print "\t-->\tEl promedio del tiempo demorado de 10 muestras por el método QUICK ha sido agregado al archivo: \"quick_graficar.txt\"    (%f" % suma_quick  " seg(s).)"
        print "\t----------------------------------------------------------------------------------------------------------------------------------------------------------------"
      cte = cte + 1

Autor: Luis