Jump to content

Este quicksort está "politicamente correto"?


killezio
 Share

Recommended Posts

Não tenho a certeza se fiz bem como é definido o algoritmo, alguém que possa dispensar do seu tempo para me clarificar agradecia 🙂

def quicksort(a):
   for e in range(0,len(a)):
       #print "e = ",e
       if a[e][0][0] != "h":
           #print a[e],"is a list"
           pivot = random.choice(a[e])
           bigger = []
           smaller = []
           #print "pivot is",pivot
           for i in a[e]:
               if biggest(i[1],pivot[1]) == i[1] and i[1] != pivot[1]:
                   bigger.append(i)
                   #print "pivot:",pivot,"bigger:",bigger
               elif biggest(i[1],pivot[1]) == pivot[1] and i[0] != pivot[0]:
                   smaller.append(i)
                   #print "pivot:",pivot,"smaller:",smaller
           smaller = [smaller]
           bigger = [bigger]
           if len(smaller[0]) == 0:
               smaller = []
           if len(bigger[0]) == 0:
               bigger = []
           #print "smaller is: ",smaller
           #print "bigger is:",bigger
           a = a[:e] + smaller + [pivot] + bigger + a[e+1:]
           #print "a:",a
   for e in a:
       if e[0][0] != "h":
               return quicksort(a)
   return a

uma coisa que eu faço é: para qualquer lista que ainda não tenha sido organizada ( lista essa que previne de uma lista bigger ou smaller de um certo pivot) coloco-a dentro de uma lista. o que é que acaba por acontecer, quando estiver um só elemento dessa lista, ela considera-se ordenada e é retirada da lista que estava a mais ( ex. [[a,b]] mantém-se porque falta reorganizar "a" e "b" mas [[a]] passa a [a] e esse [a] já nao vai ser escolhido como pivot porque não está numa lista dentro de uma lista)

Edited by pwseo
syntax highlight, indent.
Link to comment
Share on other sites

o código funciona. e isso é parte de um programa que simula um motor de busca. depois de obter os rankings the cada link preciso de organizar os links , e para isso recorri ao quicksort. (como são links o 'h' vem de "http://.....etc")

mas a minha questão não é o código funcionar. é saber se isto segue o modelo do quicksort ou se estou a fazer alguma coisa diferente

Link to comment
Share on other sites

killezio,

Torna-se difícil interpretar o teu código quando não temos acesso a nenhum contexto (não sei como são os dados que pretendes ordenar) -- isto acontece porque o teu algoritmo está inteiramente dependente e misturado com a estrutura de dados que estás a ordenar (deveria simplesmente ordenar listas). Se calhar poderia demorar um pouco e tentar perceber, mas neste momento é-me pouco conveniente.

Outra questão: um dos motivos para utilizar o algoritmo quicksort é a sua capacidade de ordenar eficientemente no tempo sem utilizar mais espaço do que o que já é ocupado pela lista original. Uma vez que crias listas no teu algoritmo, já não será um quicksort puro.

# Tradução da pág 171 do Introduction to Algorithms, 3rd ed
def quicksort(a, p, r):
   if p < r:
       q = partition(a, p, r)
       quicksort(a, p, q - 1)
       quicksort(a, q + 1, r)

def partition(a, p, r):
   x = a[r]
   i = p - 1
   for j in range(p, r):
       if a[j] <= x:
           i += 1
           a[i], a[j] = a[j], a[i]
   a[i+1], a[r] = a[r], a[i+1]
   return i+1

Se estivermos a pensar num quicksort mais conceptual e ignorando a eficiência no tempo/espaço, podemos escrever essa ideia de forma muito elegante em Python também:

def quicksort(a):
   if len(a) <= 1:
       return a

   pivot = a[-1]
   low   = quicksort([ x for x in a[:-1] if x < pivot  ])
   high  = quicksort([ x for x in a[:-1] if x >= pivot ])

   return low + [pivot] + high

Naturalmente, esta versão é muito menos eficiente em termos de memória, e para listas muito grandes pode até atingir o limite de recursividade do interpretador.

Espero que consigas daqui tirar algumas conclusões que te ajudem a responder à tua pergunta.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.