Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar o algoritmo de ordenação Pigeonhole Sort?

+2 votos
21 visitas

1 Resposta

+2 votos
respondida Jul 7 por Monica Guo (41 pontos)  

O algoritmo de ordenação conhecido como Pigeonhole Sort é útil para ordenar listas em que o número de elementos (n) e o range da lista (N) são relativamente parecidos. A complexidade desse algoritmo é da ordem de \(O(n+N)\). O passo a passo do algoritmo é:

1) Determinar os elementos máximo e mínimo da lista a ser ordenada;
2) Calcular o range, dado por \(range = max - min + 1\) que representa o número de pigeonholes;
3) Criar uma lista auxiliar que irá conter os pigeonholes;
4) Percorrer a lista original e colocar o elemento \(i\) da lista original na posição \(i - min\) da lista auxiliar;
5) Copiar os elementos da lista auxiliar (agora já ordenados) para a lista original.

Implementei o algoritmo em Python da seguinte forma:

def pigeonhole(lista):

    # Encontrar o máximo e o mínimo da lista
    max_elemento = max(lista)
    min_elemento = min(lista)

    # Calcular o range da lista
    num_pigeonholes = max_elemento - min_elemento + 1

    # Criando uma lista auxiliar com o número de pigeonholes
    lista_aux = [0]*num_pigeonholes      

    # Verificando cada elemento da lista original e colocando no pigeonhole
    # correspondente na lista auxiliar
    for i in lista:
        lista_aux[i - min_elemento] = i 
    print(lista_aux)

    # Reinicializando a lista original
    lista = []

    # Retornando os elementos para a lista original
    for j in lista_aux:
        if j != 0:
            lista.append(j)

    return lista

Agora vamos avaliar o algoritmo com um exemplo:

if __name__ == '__main__':

    lista = [1, 6, 3, 5, 8, 2, 7]

    print(pigeonhole(lista)

O resultado obtido é:

[1, 2, 3, 5, 6, 7, 8]

Uma referência bem didática que me ajudou a entender o algoritmo foi o seguinte vídeo:

https://www.youtube.com/watch?v=nVQz0kZNC64

comentou Jul 13 por Pedro Duque (51 pontos)  
Excelente, Mônica! Consegui implementar seu código no meu computador!!

Faltou só um parênteses pra fechar a última linha, mas de toda forma, seu código está sucinto, bem organizado e eficiente. Parabéns!
...