Algoritmo MergeSort: como implementar em Python

Anteriormente implementamos duas soluções de busca e em nossa segunda abordagem, tivemos que ordenar nossa lista de alunos utilizando a função sorted() do Python. Mas imagine se não tivéssemos essa opção, como poderíamos ordenar a lista?

Primeiramente vamos implementar a ordenação de maneira mais intuitiva. Para isso vamos percorrer a lista e para cada posição dessa iteração, percorreremos o restante da lista em busca do menor valor. Caso ele exista, vamos realizar a troca de posições. E chamaremos essa solução de SelectionSort:

from array import array

def ordena(lista):
    tamanho_da_lista = len(lista) - 1

    for posicao_atual in range(0, tamanho_da_lista):
        posicao_menor = posicao_atual
        menor_nome = lista[posicao_menor]

        for posicao_busca in range(posicao_atual, tamanho_da_lista):
            nome_busca = lista[posicao_busca + 1]

            if menor_nome > nome_busca:
                menor_nome = nome_busca
                posicao_menor = posicao_busca + 1

        if posicao_menor != posicao_atual:
            menor_nome = lista[posicao_menor]
            lista[posicao_menor] = lista[posicao_atual]
            lista[posicao_atual] = menor_nome

    return lista

def main():
    lista_de_alunos = ["Brendo", "Erica", "Monica", "Nico", "Paulo", "Rodrigo", "Wanessa"]

    for nome in lista_de_alunos:
        print(nome)

if __name__ == "__main__":
    main()

Tudo vai funcionar perfeitamente com a nossa pequena lista de 7 alunos! Agora, que tal usarmos a lista de aproximadamente 85 mil alunos? É melhor não, a não ser que possamos esperar um bom tempo pelo retorno.

Mas por que tivemos um desempenho tão ruim para executar essa pequena ordenação?

Podemos perceber que para cada aluno da lista, nós a percorremos novamente em busca do menor nome. Ou seja, para ordenar uma lista de n alunos, nós executamos n² operações e no nosso caso (85000²) = 7.225.000.000 operações, sim, mais de 7 trilhões de operações.

Então consideramos esse algoritmo como O(n²) ou um algoritmo quadrático. Neste artigo falamos mais sobre a notação Big O.

Então, vamos implementar uma outra solução de ordenação mais eficiente?

Vamos recorrer mais uma vez às técnicas de divisão e conquista para resolver o problema de encontrar o menor nome da lista.

Na função de ordenar, vamos chamar a função merge_sort(), que recebe como parâmetros:

• A lista de alunos;
• Uma lista temporária com o tamanho pré-definido da lista de alunos;
• O índice inicial; e
• O índice final da lista.

E serão executados os seguintes passos:

• Dividiremos a lista em duas e chamaremos, de forma recursiva a função merge_sort(), passando como parâmetros:
  1. Os dados da primeira lista;
  2. Os dados segunda lista,

Por fim, chamaremos a função merge() para mesclar as duas listas ordenadas com o apoio da lista temporária, reescrevendo a lista original.

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)
    lista_temporaria = [0] * tamanho_da_lista
    merge_sort(lista, lista_temporaria, 0, tamanho_da_lista - 1)

def merge_sort(lista, lista_temporaria, inicio, fim):
    if inicio < fim:
        meio = (inicio + fim) // 2
        merge_sort(lista, lista_temporaria, inicio, meio)

        merge_sort(lista, lista_temporaria, meio + 1, fim)

        merge(lista, lista_temporaria, inicio, meio + 1, fim)

def merge(lista, lista_temporaria, inicio, meio, fim):
    fim_primeira_parte = meio - 1
    indice_temporario = inicio
    tamanho_da_lista = fim - inicio + 1

    while inicio <= fim_primeira_parte and meio <= fim:
        if lista[inicio] <= lista[meio]:
            lista_temporaria[indice_temporario] = lista[inicio]
            inicio += 1
        else:
            lista_temporaria[indice_temporario] = lista[meio]
            meio += 1
        indice_temporario += 1

    while inicio <= fim_primeira_parte:
        lista_temporaria[indice_temporario] = lista[inicio]
        indice_temporario += 1
        inicio += 1

    while meio <= fim:
        lista_temporaria[indice_temporario] = lista[meio]
        indice_temporario += 1
        meio += 1

    for i in range(0, tamanho_da_lista):
        lista[fim] = lista_temporaria[fim]
        fim -= 1

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()

Ao executar o algoritmo vemos que o desempenho foi muito melhor. Vamos entender o que aconteceu?

Quando dividimos a lista pela metade e executamos isso de forma recorrente para realizar as comparações, isso nos lembra bastante o algoritmo de busca binária, certo? Sim! Então,por ora, vamos considerar este algoritmo como O(lg N).

Também levaremos em conta que realizamos a intercalação que percorre as duas metades da lista para comparar e preencher a lista temporária de forma ordenada. Então esse algoritmo é linear, ou seja, O(N). Como ambos os algoritmos são executados juntos, podemos considerar o MergeSort O(N lg N).

Lembrando que temos um artigo explicando melhor como funciona a notação Big O.

Enfim, vimos que o desempenho do MergeSort é muito superior ao SelectionSort, mas será que essa é a nossa melhor solução? Será que podemos resolver ordenações de outras formas?

E a resposta é: há inúmeras maneiras de resolver problemas de ordenação e no próximo artigo.da série vamos trabalhar em mais uma forma de resolver o problema de ordenação.