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

O que é o algoritmo de ordenação Postman Sort?

0 votos
23 visitas
perguntada Out 8 em Ciência da Computação por Gustavo Medeiros (36 pontos)  

Discorra sobre o algoritmo de ordenação Postman Sort, apresentando a ideia, exemplos, escopo, complexidade e um código para sua implementação.

Compartilhe

1 Resposta

0 votos
respondida Out 8 por Gustavo Medeiros (36 pontos)  
editado Out 9 por Gustavo Medeiros

O Postman Sort é um algoritmo de ordenamento usado por máquinas de classificação de cartas nos correios. Funciona como uma variação do MSD (Most Significant Digit) Radix, pois ele faz a ordenação da esquerda para a direita, na ordem do mais significativo para o menos significativo.

A imagem será apresentada aqui.

O processo representado acima consiste em distribuir os elementos em \( \textit {buckets}\) de acordo com o primeiro caractere/dígito. Em seguida a tarefa de classificação se repete, mas agora considerando o segundo termo dos elementos que estão no mesmo \( \textit {bucket}\) e separando os em novos \( \textit {buckets}\). O processo recursivo ocorre para cada termo seguinte até que se chegue ao comprimento total do maior elemento da lista ou até que se tenha ordenado todos os elementos da lista. Como os elementos não são comparados uns com os outros, a complexidade é \(O(n \times c)\) onde \(c\) depende do comprimento dos elementos e \(n\) é o número de \( \textit {buckets}\).

Note que em casos onde os termos são longos mas são passiveis de serem distinguíveis nos primeiros elementos, ou seja, a parte final é igual, a ordenação da esquerda para direita, apesar de usar mais memória que o método da direita para esquerda, consegue ser mais rápido.

Você provavelmente já fez isso ao separar seu material do ensino médio em matérias e, dentro das matérias, em tópicos. Pode ser usado tanto para ordenamento de números como para ordenamento de palavras.

O algoritmo em Python é apresentado pelo código abaixo. Perceba que neste caso estamos ordenando \( \textit{strings} \) de forma a simular o trabalho feito nos correios, afinal de conta o algoritmo Postman Sort é muito usado para ordenar correspondências. As \( \textit{strings} \) são inventadas, servem apenas para exemplificar. No caso primeiro temos o Estado (SP, DF, RJ BA), depois temos cidade ou município (São Paulo, Barueri, Salvador, Rio de Janeiro e Brasília) e por último temos o bairro (Centro, Morumbi, Sudoeste, Pelourinho, Ipanema). A cada passo da recursão uma característica do local é ordenada, indo da mais geral (significativa) para a mais específica (menos significativa). Dessa forma conseguimos juntar cartas que irão para destinos próximos ou iguais.

def Postman_sort(L, i):

# Caso Lista tenha somente uma key
if len(L) <= 1:
    return L
    #Ordenação lexicográfica em buckets
done_bucket = []
buckets = [ [] for x in range(27) ] # um para cada letra a-z

for s in L:
    if i >= len(s):
        done_bucket.append(s)
    else:
        buckets[ ord(s[i]) - ord('A') ].append(s)

# conquer (recursão)
buckets = [ Postman_sort(b, i + 1) for b in buckets ]

# casar (junta os buckets)
return done_bucket + [ b for blist in buckets for b in blist ]

if __name__ == '__main__':
    L = ['SP-SAO-MOR', 'DF-BSB-SUD', 'RJ-RIO-IPA', 'BA-SSA-PEL', 'SP-BRU-CEN', 'DF-BSB-SUD']
    print (L)
    L = Postman_sort(L, 0)
    print (L)

Resultado:

output #Primeiro a lista original e depois a lista organizada

['SP-SAO-MOR', 'DF-BSB-SUD', 'RJ-RIO-IPA', 'BA-SSA-PEL', 'SP-BRU-CEN', 'DF-BSB-SUD']
['BA-SSA-PEL', 'DF-BSB-SUD', 'DF-BSB-SUD', 'RJ-RIO-IPA', 'SP-BRU-CEN', 'SP-SAO-MOR']

Referência:
https://iq.opengenus.org/postman-sort/

...