Algoritmo Quicksort: como implementar em Python

Já 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:

Escolheremos um pivô (no caso, o primeiro item da lista) e vamos trocá-lo de posição com o item do meio;
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.

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?