Algoritmo QuickSort [RESOLVIDO]

1. Algoritmo QuickSort [RESOLVIDO]

Thiago Giroto Milani
thiagogmilani

(usa Debian)

Enviado em 22/09/2016 - 19:52h

Estou com um problema com o quicksort que fiz, ele não está rodando quando a lista já está ordenada ou quando está inversamente ordenada. Tive que implementar para um trabalho de faculdade, mais não consigo achar o erro.

def partition(myList, start, end):
pivot = myList[start]
left = start+1
right = end
done = False
while not done:
while left <= right and myList[left] <= pivot:
left = left + 1
while myList[right] >= pivot and right >=left:
right = right -1
if right < left:
done= True
else:
temp=myList[left]
myList[left]=myList[right]
myList[right]=temp
temp=myList[start]
myList[start]=myList[right]
myList[right]=temp
return right

def quicksort(myList, start, end):
if start < end:
split = partition(myList, start, end)
quicksort(myList, start, split-1)
quicksort(myList, split+1, end)
return myList

### a lista que estou gerando é essa:

N = 100
B = range (N)
A=[]
for i in reversed(B):
A.append (B[i])


C = quicksort(A,0,len(A)-1)
print C



  


2. Re: Algoritmo QuickSort [RESOLVIDO]

Lisandro Guerra
Lisandro

(usa Arch Linux)

Enviado em 22/09/2016 - 20:17h

Oi Thiago. Quando for colar código aqui coloque um code antes e um /code depois, sempre entre Colchetes como uma lista [ ].
tipo [c0de] seu código aqui [/c0de]
Usei zero no lugar da letra 'o' aqui que é para evitar que seja interpretado ok?
Esta sua postagem já coloquei os marcadores de código pra ti, então se quiser ver é só editar.

Abraço e sucesso ai no trabalho.


3. Re: Algoritmo QuickSort [RESOLVIDO]

Thiago Giroto Milani
thiagogmilani

(usa Debian)

Enviado em 22/09/2016 - 20:20h

Obrigado pela dica.

se puder me ajudar com a resposta agradeço.


att.



4. Re: Algoritmo QuickSort [RESOLVIDO]

Lisandro Guerra
Lisandro

(usa Arch Linux)

Enviado em 26/09/2016 - 21:36h

thiagogmilani escreveu:

Obrigado pela dica.

se puder me ajudar com a resposta agradeço.


att.


Então, estava meio atrapalhado aqui com meus afazeres e só agora pude olhar. Espero que não seja tarde.
Bom rodei aqui usando Python 3.5.2, só tive que colocar os parenteses no print pra rodar: print(C)
Rodando gerou uma lista em ordem reversa e depois ordenou imprimindo o resultado, depois retirei o reverse e gerou uma lista já ordenada e rodou o ordenador normalmente imprimindo o resultado.
Parece que está funcionando. Qual é o problema que eu não entendi?

Abraço


5. Re: Algoritmo QuickSort [RESOLVIDO]

Thiago Giroto Milani
thiagogmilani

(usa Debian)

Enviado em 26/09/2016 - 21:39h

opa obrigado pelas dicas.

então exatamente isso, quando a lista passada para o quick sort ja está ordenada, ou está inversamente ordenada, ele não consegue retornar o resultado, porém esse problema está se apresentando apenas com listas maiores que 30000.

PS: estou usando python 2.7


obrigado.


6. Re: Algoritmo QuickSort

Lisandro Guerra
Lisandro

(usa Arch Linux)

Enviado em 27/09/2016 - 19:16h

thiagogmilani escreveu:

opa obrigado pelas dicas.

então exatamente isso, quando a lista passada para o quick sort ja está ordenada, ou está inversamente ordenada, ele não consegue retornar o resultado, porém esse problema está se apresentando apenas com listas maiores que 30000.

PS: estou usando python 2.7


obrigado.

Então, rodei com Python 2.7.12 e 3.5.2 lista com 310000 elementos.
Demorou vários minutos usou muita RAM, mas no final foi bem e apresentou as listas.
De repente pode ser que se está rodando no IDLE ele arrie ou a própria máquina...

EDIT:
Acho que já sei o que pode estar acontecendo, está limitado pelo número de recursividades.
Coloca lá antes do teu código:

import sys

sys.setrecursionlimit(40000)


Isso vai ajustar para até 40 mil.
Aí tenta com 31 mil elementos que deve dar certo.

Abraço



7. Re: Algoritmo QuickSort [RESOLVIDO]

Thiago Giroto Milani
thiagogmilani

(usa Debian)

Enviado em 27/09/2016 - 19:34h

Obrigado pela ajuda, é foi o que pensei, estou estourando a memória do meu PC para rodar e não está dando conta, por isso crio que não consigo o retorno, obrigado.





8. Re: Algoritmo QuickSort [RESOLVIDO]

Perfil removido
removido

(usa Nenhuma)

Enviado em 27/09/2016 - 19:36h

thiagogmilani escreveu:

Obrigado pela ajuda, é foi o que pensei, estou estourando a memória do meu PC para rodar e não está dando conta, por isso crio que não consigo o retorno, obrigado.


Só por curiosidade, de quanto é a memória total do equipamento?

----------------------------------------------------------------------------------------------------------------
Nem direita, nem esquerda. Quando se trata de corrupção o Brasil é ambidestro.
(anônimo)

Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden



9. Re: Algoritmo QuickSort [RESOLVIDO]

Thiago Giroto Milani
thiagogmilani

(usa Debian)

Enviado em 27/09/2016 - 19:38h

Cara estou rodando em um MacBook Pro com proc, i5 e 12Gb de ram.

até uma lista de 20.000 números ele rodou perfeitamente.


10. Re: Algoritmo QuickSort [RESOLVIDO]

Perfil removido
removido

(usa Nenhuma)

Enviado em 27/09/2016 - 19:40h

Valeu! 12 GB é memória prá caramba.
Usou tudo o que tinha e ainda faltou.

----------------------------------------------------------------------------------------------------------------
Nem direita, nem esquerda. Quando se trata de corrupção o Brasil é ambidestro.
(anônimo)

Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden



11. Re: Algoritmo QuickSort [RESOLVIDO]

Lisandro Guerra
Lisandro

(usa Arch Linux)

Enviado em 27/09/2016 - 19:42h

thiagogmilani escreveu:

Obrigado pela ajuda, é foi o que pensei, estou estourando a memória do meu PC para rodar e não está dando conta, por isso crio que não consigo o retorno, obrigado.




Acho que já sei o que pode estar acontecendo, está limitado pelo número de recursividades.
Coloca lá antes do teu código:

import sys

sys.setrecursionlimit(40000)


Isso vai ajustar para até 40 mil.
Aí tenta com 31 mil elementos que deve dar certo.
Aqui foi muito mais rápido assim, já que o Python não tem que fazer malabarismo para lidar com a limitação.

Abraço


12. Re: Algoritmo QuickSort [RESOLVIDO]

Lisandro Guerra
Lisandro

(usa Arch Linux)

Enviado em 27/09/2016 - 19:54h

thiagogmilani escreveu:

Cara estou rodando em um MacBook Pro com proc, i5 e 12Gb de ram.

até uma lista de 20.000 números ele rodou perfeitamente.


Minha máquina só tem 4GB mais de RAM, tem que rodar se fizer o import que coloquei no post anterior.


import sys

sys.setrecursionlimit(40000)


Faz lá e diz se deu certo.

Abraço



01 02



Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts