Entrar Ainda não tem acesso?
2
respostas

Quick sort no Python (erro de retorno)

por Estudante
| 51.9k xp | 8 posts

boa tarde, estou tentando programar um algoritmo quicksort baseado em um modelo que ví num vídeo. O problema é que na minha função partition o programa está me retornando o valor incorreto para usar na recursão do quicksort.

def partition(array):
    pivot = array[-1]
    i = 0
    j = len(array)-1
    while i<j:
        while array[i]<pivot and i<len(array)-1:
            i+=1
        while array[j]>=pivot and j>0:
            j-=1
        if i<j:
            array[i],array[j] = array[j],array[i]
    if array[i]>array[-1]:
        array[i],array[-1] = array[-1],array[i]
        #aqui mandei imprimir o valor de i para ver se estava saindo corretamente o novo índice do pivô e está
        print(i)
    #mas aqui ele retorna o valor do último índice da lista
    return i

#aqui chamei a funçao e imprimi o retorno pra conferência. Ele organiza a lista de acordo com o pivô e reposiciona o pivô mas não retorna o seu indice corretamente

array = [7,9,8,12,4,5,7,52,43,64,21,19,40]
partition(array)
print(partition(array))
print(array)

alguém tem alguma ideia do motivo pra isso?

Desde já, agradeço!

2 respostas
por Thiago Matos
| 212.6k xp | 179 posts
Desenvolvedor 
partition(array)

Na primeira execução do seu método, na linha mencionada acima, ele realmente retorna o "i" com valor 9, da mesma forma que é mostrado no print() interno que você colocou.

Após isso seu array passa a ter outra ordem:

# antes =   [7, 9, 8, 12, 4, 5, 7, 52, 43, 64, 21, 19, 40]
# depois = [7, 9, 8, 12, 4, 5, 7, 19, 21, 40, 43, 52, 64]

Aí na segunda execução nessa linha: print(partition(array)) o "pivot" passa a ter o valor 64, não 40 como anteriormente, e no segundo loop while:

while array[i]<pivot and i<len(array)-1:
            i+=1

a variável "i" é incrementada até o valor 12, que é o que ele retorna no terminal para você.

Só para efeito de agilidade no entendimento, eu mostrei acima o que ele está retornado, mas qual é o retorno que você está querendo? Por hora o diagnóstico é falha na lógica ^^

por Estudante
| 51.9k xp | 8 posts

Nossa... obrigado! Ta certo, não percebi que estava executando a função pela segunda vez quando chamei ela dentro do print(). O valor que eu queria que ela retornasse era i mesmo. Meu problema é que meu quicksort não está funcionando e quando fui puxar o retorno da partition para ver se era lá o problema recebi esse retorno 12 e deduzi que era esse o problema. Masss, se não é isso, você poderia dar uma olhada no restante e ver se entende porque ele só ordena um pedaço da lista?

def partition(array):
    pivot = array[-1]
    i = 0
    j = len(array)-1
    while i<j:
        while array[i] < pivot and i < len(array)-1:
            i+=1
        while array[j] >= pivot and j > 0:
            j-=1
        if i<j:
            array[i], array[j] = array[j], array[i]
    if array[i] > array[-1]:
        array[i], array[-1] = array[-1], array[i]

    return i


def quicksort(array):
    if len(array)>1:
        partition_pos = partition(array)

        quicksort(array[0:partition_pos])
        quicksort(array[partition_pos+1:])
    return array


array = [7,9,8,12,4,5,7,52,43,64,21,19,40]

quicksort(array)
print(array)

do 12 (índice 3) em diante ela está ordenada, e não entendi porque.. eu baseei esse código em outro que entra com parametros esquerda e direita pro primeiro e último índice também, e daquela forma funcionava, mas queria simplificar o código para não precisar passar esses parametros. Desde já agradeço.