Algoritmo Quicksort: como implementar em Python

Algoritmo Quicksort: como implementar em Python
Brendo Rodrigo Souza de Matos
Brendo Rodrigo Souza de Matos

Compartilhe

implementamos a solução de ordenação da lista de alunos de duas formas diferentes e vimos que o MergeSort tem um desempenho muito superior em comparação ao SelectionSort.

Então será que o MergeSort é a melhor solução de ordenação que existe?

Agora vamos implementar outra solução e depois realizaremos uma pequena comparação.

Seguiremos os seguintes passos para chegar ao nosso objetivo:

  1. Escolheremos um pivô (no caso, o primeiro item da lista) e vamos trocá-lo de posição com o item do meio;
  2. Vamos percorrer toda a lista e verificar item a item, comparando-os com o pivô. A partir de então:
  • Caso o item esteja numa posição menor do que o pivô pela ordem alfabética, será transferido ou mantido à lista da esquerda;
  • Caso o item esteja numa posição maior do que o pivô pela ordem alfabética, será transferido ou mantido à lista da direita.

Fazendo isso de forma recursiva, ao final teremos uma lista ordenada

Vamos implementar?

from array import array

def importa_lista(arquivo):
    lista = []
    with open(arquivo) as tf:
        lines = tf.read().split('","')
    for line in lines:
        lista.append(line)
    return lista

def ordena(lista):
    tamanho_da_lista = len(lista)
    if tamanho_da_lista > 0:
        quick_sort(lista, 0, tamanho_da_lista - 1)

def quick_sort(lista, inicio, fim):
    if inicio > fim:
        return
    anterior = inicio
    posterior = fim
    pivo = lista[inicio]

    while anterior < posterior:
        while anterior < posterior and lista[posterior] > pivo:
            posterior = posterior - 1

        if anterior < posterior:
            lista[anterior] = lista[posterior]
            anterior = anterior + 1

        while anterior < posterior and lista[anterior] <= pivo:
            anterior = anterior + 1

        if anterior < posterior:
            lista[posterior] = lista[anterior]
            posterior = posterior - 1

        lista[anterior] = pivo

    quick_sort(lista, inicio, anterior - 1)
    quick_sort(lista, anterior + 1, fim)

def main():
    lista_de_alunos = importa_lista('../data/lista_alunos')

    ordena(lista_de_alunos)

    for nome in lista_de_alunos:
        print(nome)

if __name__ == "__main__":
    main()

Notamos que o desempenho com o qual o QuickSort executou é bem similar ao do MergeSort, não é? E quanto a complexidade? Vamos compará-los?

Como no MergeSort, nós dividimos a lista recursivamente, mas não necessariamente ao meio e sim a partir de um pivô. Isso nos lembra a notação O(lg N), certo? Certo!

Além disso, devemos considerar que, a cada chamada recursiva, percorremos toda a lista para garantir que todos os alunos cujos nomes estejam numa posição menor do que o pivô na ordem alfabética encontrem-se à sua esquerda. Já os alunos com nomes em posições maiores do que o pivô na ordem alfabética, devem estar à sua direita (como é mostrado na imagem abaixo), o que nos lembra um algoritmo linear, certo? Mais uma vez, certíssimo. Então podemos determinar que isso nos dá a complexidade O(N lg N) assim como no MergeSort.

Na primeira linha, lemos a sequência de nomes de Nico, em destaque, e respectivamente Paula, Erica, Brendo, Mônica, Wanessa e Rodrigo nas demais posições.
Na segunda linha, lemos os nomes de Paula, Erica, Brendo, Nico, em destaque, Mônica, Wanessa e Rodrigo. Acima do nome de Nico, uma seta aponta para a direita. Abaixo do nome Nico, uma seta aponta para a esquerda. Na terceira linha, há os nomes de Paula, Erica, Brendo, Nico, em destaque, Mônica, Wanessa e Rodrigo.

Agora, será que em qualquer cenário o algoritmo QuickSort executa em O(N lg N)? Quais seriam as diferenças de eficiência entre o QuickSort e MergeSort, visto que aparentam sempre ter a mesma complexidade? Qual é o melhor algoritmo?

Explicamos de forma mais aprofundada essa comparação entre os algoritmos QuickSort e MergeSort depois de entender melhor sobre a Notação BigO.

Brendo Rodrigo Souza de Matos
Brendo Rodrigo Souza de Matos

Engenheiro de Software apaixonado pelo que faz, amante de novos desafios e sedento por conhecimento. Atualmente sou Engenheiro de Software no Méliuz (B3: CASH3) e mestrando em Ciências da Computação pela Universidade Federal do Amazonas.

Veja outros artigos sobre Programação