killezio Posted January 21, 2016 at 04:42 PM Report Share #592273 Posted January 21, 2016 at 04:42 PM (edited) 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 January 21, 2016 at 05:35 PM by pwseo syntax highlight, indent. Link to comment Share on other sites More sharing options...
pwseo Posted January 24, 2016 at 10:58 PM Report Share #592463 Posted January 24, 2016 at 10:58 PM killezio, Tentaste executar o teu código? Logo nas primeiras linhas há problemas, como por exemplo aquela comparação com a string "h". Link to comment Share on other sites More sharing options...
killezio Posted January 27, 2016 at 02:42 PM Author Report Share #592609 Posted January 27, 2016 at 02:42 PM 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 More sharing options...
pwseo Posted January 30, 2016 at 03:33 PM Report Share #592808 Posted January 30, 2016 at 03:33 PM 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 More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now