Este quicksort está "politicamente correto"?

[killezio]

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.

[pwseo]

killezio,

Tentaste executar o teu código? Logo nas primeiras linhas há problemas, como por exemplo aquela comparação com a string "h".

[killezio]

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

[pwseo]

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.