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

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

+1 voto
44 visitas
perguntada Out 27 em Ciência da Computação por Carlos Piccioni (21 pontos)  
reclassificado Out 28 por Carlos Piccioni

Introduza o algoritmo de ordenação Radix Sort (LSD, MSD e MSD in-place). Discuta a ideia, escopo, complexidade e implemente o algoritmo na linguagem de sua escolha. Use e abuse de exemplos.

Compartilhe

3 Respostas

+1 voto
respondida Out 28 por Carlos Piccioni (21 pontos)  
editado Nov 11 por Carlos Piccioni

Radix Sort LSD

O Radix Sort é um algoritmo da classe de ordenação de inteiros, como o Counting Sort, e não de comparação entre os elementos de entrada, como é o caso de algoritmos como Quick Sort e Merge Sort. Suponha n elementos a serem ordenados, cada um representado por uma chave. Algoritmos como o Counting Sort são muito eficientes para ordenação quando esta chave é representada por inteiros relativamente pequenos. Porém, quando essas chaves crescem em tamanho, pode ser interessante "quebrar" a chave em d pedaços, que chamamos de dígitos, e realizar a ordenação por etapas (dígito a dígito). É essa a ideia principal do Radix Sort, como veremos ao longo desta resposta.

A representação de cada dígito depende da base escolhida. Por exemplo, podemos utilizar base decimal, binária, hexadecimal, etc. A escolha da base determina os k diferentes valores que um dígito pode assumir (e Radix significa exatamente isso, a base em sistemas de numeração posicional). Apesar de ser da classe de algoritmos de ordenação de inteiros, o Radix Sort pode ser utilizado para ordenação de diversos outros tipos de dados. Por exemplo, para strings: basta, para tal, utilizarmos uma base em que o 'dígito' represente adequadamente a ordenação desejada para cada caractere.

O Radix Sort pode ser implementado em duas variantes principais: Radix Sort LSD (Least Significant Digit) e o Radix Sort MSD (Most Significant Digit). Como veremos, as versões básicas de cada algoritmo demandam espaço extra de memória durante o processo de ordenação. Assim, como alternativa, será abordada também uma versão "in-place" do algoritmo MSD.

A ideia por trás de ambos é muito simples. Suponha que queremos ordenar uma lista com 8 registros (n) representados por chaves de 3 dígitos (d), na base decimal \(k=10\), que são inicialmente fornecidos na ordem abaixo:

[506, 818, 088, 938, 457, 412, 002, 289]

O algoritmo Radix Sort LSD inicia o processo de ordenação de cada elemento da lista pelo dígito menos significativo (a princípio pode até parecer contra intuitivo). Um algoritmo de ordenação por contagem estável, como o Counting Sort, com base nesse dígito menos significativo, reordena todos os elementos. Esse processo é repetido então para o próximo dígito menos significativo, até que todos os d dígitos sejam processados, conforme ilustração a seguir:

A imagem será apresentada aqui.

Observe que o Radix Sort LSD exige chaves de mesmo tamanho. Caso contrário, basta acrescentarmos dígitos que representem o menor valor possível à esquerda antes da ordenação total (ou no processamento de cada dígito individualmente).

Esse algoritmo foi empregado em máquinas de classificação de cartões perfurados no início do século passado. Cada cartão era representado por uma chave, cada dígito da chave representado por um inteiro em uma coluna (codificado pelas perfurações no cartão), e cada coluna processada por vez, com o processo iniciando pela coluna que representava o dígito menos significativo. Na versão mais básica, a máquina era capaz de processar apenas uma coluna de forma automática, sendo esta definida por um operador. Ao processa-la, a máquina distribuía os cartões em 'cestas' relativas ao valor do dígito processado para cada cartão (0 a 9, por exemplo). O operador então recolhia as pilhas de cartões de cada cesta, as "concatenava" na ordem adequada (por exemplo, pilhas das cestas de 0 a 9 eram empilhadas pelo operador na ordem da menor cesta para a maior, em uma única pilha de cartões), e alimentava novamente a máquina com essa pilha, configurando-a para processar a próxima coluna.

Observação 1: interessantes informações sobre o funcionamento eletro mecânico de tais máquinas podem ser verificadas em www.righto.com/2016/05/inside-card-sorters-1920s-data.html.

Observação 2: o Radix Sort MSD também pode ser utilizado em tais máquinas, porém o conjunto de cartões separados em cada cesta precisa ser processado novamente de forma independente dos outros, conforme será explicado mais a frente.

Observação 3: Note também que, para que o Radix Sort funcione corretamente, é importante que o algoritmo de ordenação de cada dígito seja estável: na ordenação, em cada etapa, caso dois elementos possuam um mesmo dígito, a ordem relativa da etapa anterior deve ser mantida. A estabilidade garante, por exemplo, que a ordem entre 002 e 088 não seja trocada na última etapa de ordenação em nosso exemplo, já que o último dígito que está sendo processado é igual (0), logo a ordenação relativa entre ambos foi determinada na etapa anterior (0 contra 8).

O algoritmo abaixo em Python implementa o que acabamos de ilustrar, em que admitimos uma lista de inteiros qualquer, a 'padronizamos' para que todos os elementos sejam representados por uma chave de mesmo tamanho (por simplificação, dada a base decimal, representamos internamente todas as chaves como strings, das quais extraímos os dígitos, como inteiros, em cada etapa de processamento. Mas pode-se utilizar outra estrutura de dados, por exemplo, uma lista de dígitos, o que pode mais interessante em casos em que os dígitos estão em bases maiores que 10).

Um algoritmo de Counting Sort, modificado para fazer a ordenação por dígito (e não por cada elemento da lista), é utilizado como sub rotina do Radix Sort LSD. Logo, o que o Radix Sort LSD basicamente faz é utilizar o Counting Sort modificado para ordenação de todos os elementos, dígito por dígito, do menos significativo até o mais significativo:

def padronizar(lista):
    ''' Padroniza todos os elementos da lista para o mesmo número de dígitos,
    acrescentando zeros a esquerda de todo elemento com número de dígitos
    menor que d
    '''
    n = len(lista)
    for i in range(n):
        lista[i] = str(lista[i])
    d = len(max(lista, key=len))
    for i in range(n):
        if(len(lista[i]) < d):
            lista[i] = lista[i].zfill(d)

    return lista, d


def counting_sort(lista_original, digito):

    n = len(lista_original)

    # obtém o maior dígito entre os que estão sendo avaliados:
    k = 0
    for i in range(n):
        if (int(lista_original[i][digito]) > k):
            k = int(lista_original[i][digito])

    # inicializa o que será a lista ordenada final
    lista_ordenada = [None] * n
    # inicializa lista auxiliar com zeros, em que será armazenada a
    # distribuicao acumulada dos dígitos avaliados:
    distribuicao = [0] * (k + 1)

    # para o dígito avaliado de cada elemento j:
    for j in range(n):
        # incrementa sua frequência e armazena na lista distribuicao:
        distribuicao[int(lista_original[j][digito])] = \
            distribuicao[int(lista_original[j][digito])] + 1

    # para cada digito da lista de frequencias, a começar do segundo:
    for i in range(1, k + 1):
        # determina sua distribuição de frequência acumulada:
        distribuicao[i] = distribuicao[i] + distribuicao[i-1]

    # a partir do último elemento da lista original, em direção ao primeiro:
    for j in (range(n-1, -1, -1)):

        # a posição do elemento na lista ordenada será dada pela posição
        # do digito avaliado na distribuição de frequência acumulada:
        lista_ordenada[distribuicao[int(lista_original[j][digito])] - 1] = \
                lista_original[j]

        # reduz em 1, para o elemento em questão, o valor da frequência
        # acumulada, para que o próximo elemento com digito avaliado igual,
        # a ser processado, seja alocado em uma posição imediatamente anterior,
        # garantindo que o algorítmo seja estável
        distribuicao[int(lista_original[j][digito])] =\
            distribuicao[int(lista_original[j][digito])] - 1

    return lista_ordenada


def radix_sort_LSD(lista, d):

    # para cada dígito, iniciando do menos significativo, ordena a lista:
    for digito in range(d - 1, -1, -1):

        lista = counting_sort(lista, digito)

    lista = [int(x) for x in lista]

    return lista


if __name__ == "__main__":

    lista = [506, 818, 88, 938, 457, 412, 2, 289]

    lista, d = padronizar(lista)

    print("Lista ordenada:", radix_sort_LSD(lista, d))

Com relação a complexidade de tempo, a do algoritmo Radix Sort LSD é \(\Theta(d(n+k))\), pois:

  1. Para cada dígito, o Counting Sort executa laços distintos até n (número de elementos da lista) e até k (número de valores que cada dígito pode assumir);

  2. A rotina Counting Sort é chamada pelo Radix Sort LSD, para cada dígito da chave, ou seja, d vezes.

Adicionalmente, supondo a quantidade de dígitos d de cada chave constante, a complexidade de tempo é reduzida para \(\Theta(n+k)\). E se \(k\in\mathcal{O}(n)\), então a complexidade assintótica do Radix Sort é linear em \(n\).

Ou seja, o Radix Sort pode ser vantajoso em relação a outros algoritmos de ordenação, como o Merge Sort ou outros de complexidade \(\mathcal{O}(n\log(n))\), quando \(d<\log(n)\). Por exemplo, conforme exemplo apresentado em [3], suponha que desejamos ordenar uma lista de \(2^{20}\) registros com chaves de <em>64 bits, em que cada chave representa um número de 4 "dígitos" (logo, cada "dígito" é representado por \(64/4=16\) bits, o que nos dá \(k=2^{16}\) valores diferentes possíveis para cada dígito). Então:

  • O Merge Sort realizaria em torno de \(n\log_2(n)=2^{20}\log_2(2^{20})=20\times2^{20}\approx2.1\times10^7\) comparações;

  • O Radix Sort LSD implementado com o Counting Sort realizaria \(d(n+k)=4\times(2^{20}+2^{16})\approx4.5\times10^6\) operações.

Contudo, note que, para o mesmo n e mesmo tamanho da chave anterior, mas para \(d=32\), logo \(k=4\) (a chave de 64 bits composta por 32 dígitos, cada um com capacidade de representar 4 valores diferentes), teremos a mesma complexidade de tempo para o Merge Sort, porém para o Radix Sort teremos na ordem de \(d(n+k)=32\times(2^{20}+2^{2})\approx 3.4 \times 10^7\) operações.

Já a complexidade de espaço do Radix Sort LSD é \(\mathcal{O}(n+k)\), já que o Counting Sort cria listas (ou arrays) auxiliares dessas dimensões no processo de ordenamento.

+1 voto
respondida Out 28 por Carlos Piccioni (21 pontos)  
editado Nov 11 por Carlos Piccioni

Radix Sort MSD

Já o Radix Sort MSD, conforme comentado anteriormente, inicia a ordenação pelo dígito mais significativo. A ideia é separar os elementos com o mesmo dígito avaliado em um 'cesta' específica. Por exemplo, em uma ordenação na base decimal, 'jogaríamos' os diversos elementos em até 10 'cestas' que representariam seu dígito mais significativo. Depois, dentro de cada cesta, o mesmo processo de ordenação ocorre novamente, pelo segundo dígito mais significativo, dividindo os elementos em sub cestas. O processo ocorre sucessivamente até o último dígito (contudo, se há apenas um elemento dentro de determinada cesta, não há mais necessidade de sub divisões). Garantindo que as cestas / sub cestas sejam ordenadas pelo dígito que representam, a ordenação final é garantida pela mera concatenação dessas cestas.

Por exemplo, suponha que desejamos ordenar a seguinte lista:

[089, 818, 038, 457, 039, 452, 032, 096]

O processo de ordenação segue então os seguintes passos:

A imagem será apresentada aqui.

A implementação tradicional do Radix Sort MSD é recursiva, visto que o processo é repetido para cada cesta individualmente. Assim, para inteiros, \(k=10\), implementamos o algoritmo a seguir em Python, conforme lógica descrita até então:

import numpy as np


def padronizar(lista):

    n = len(lista)
    for i in range(n):
        lista[i] = str(lista[i])
    d = len(max(lista, key=len))
    for i in range(n):
        if(len(lista[i]) < d):
            lista[i] = lista[i].zfill(d)

    return lista, d


def radix_sort_MSD(lista, d, digito):

    n = len(lista)

    # condição de término da recursão: paramos se a lista avaliada possuir
    # um ou nenhum elemento, ou se ultrapassamos o último digito que
    # deveria ser verificado (necessário para o caso de elementos iguais):
    if((n <= 1) or (d == digito)):
        return lista

    # inicializa os possíveis "cestas", em que o índice de cestas representa
    # os cestas de 0 a 10:
    cestas = np.empty((10, 0)).tolist()

    # inicializa o que será a lista com as cestas ordenadas:
    cestas_ordenadas = []

    for elemento in lista:

        # aloca o elemento na respectiva cesta, conforme seu dígito mais significativo:
        cestas[int(elemento[digito])].append(elemento)

    for i, cesta in enumerate(cestas):

        # realiza a chamada recursiva, solicitando a ordenação dentro
        # da cesta em específico, indicando que o dígito a ser avaliado é
        # o próximo:
        cestas[i] = radix_sort_MSD(cesta, d, digito + 1)

    # concatena os resultados ordenados, retirando os elementos de dentro
    # das cestas, já que já estão em uma sequência ordenada:
    for cesta in cestas:
        for elemento in cesta:
            cestas_ordenadas.append(elemento)

    return cestas_ordenadas


if __name__ == "__main__":

    lista = [89, 818, 38, 457, 39, 452, 32, 96]

    lista, d = padronizar(lista)

    lista_ordenada = radix_sort_MSD(lista, d, digito=0)

    print("Lista ordenada:", [int(x) for x in lista_ordenada])

Observação 1: Note que no MSD é necessário reordenar os elementos dentro de cada sub-cesta de forma independente das demais. Logo, pode facilmente fazer uso de processamento paralelo: a ordenação dentro de cada cesta poderia ser direcionada a um processador / thread diferente, por exemplo.

A complexidade do Radix Sort MSD é \(\mathcal{O}(d\times n)\): podemos observar no código acima que teremos d níveis de recursão, e em cada nível, no máximo n elementos serão avaliados pelas instâncias diferentes da recursão. Por que no máximo? Caso o elemento seja o único na cesta, não há necessidade de mais níveis de recursão. E se trabalharmos com ordenação de strings de caracteres, por exemplo, teremos menos níveis de recursões para as strings menores, o que torna o MSD interessante para este tipo de ordenação.

Assim, o código a seguir é uma pequena modificação do anterior, para realizar a ordenação de palavras formadas pelos 26 caracteres usuais do alfabeto (sem acentuação). Para isso, a modificação realizada no código anterior é simples: basicamente é utilizado o comando ord() para obtermos um inteiro que representa o valor da letra na codificação utilizada. Por exemplo, em utf-8, 'a' é representado pelo valor decimal 97, e 'z' por 122. Assim, desse valor é subtraído 97 para compormos os 26 índices das cestas em que as palavras serão alocadas em cada etapa.

Se a cesta de palavras, avaliada em determinada recursão, possuir uma palavra de tamanho menor que o dígito que deveria ser avaliado no momento, então essa palavra não precisa mais ser comparada com as palavras maiores. Logo, ela já será adicionada à lista ordenada da etapa (ou seja, no retorno da recursão, ficará em posição anterior as demais palavras, maiores, que ainda serão divididas em cestas e enviadas para o próximo nível de recursão):

import numpy as np


def radix_sort_MSD(lista, digito):

    n = len(lista)

    if((n <= 1) or (len(max(lista, key=len)) == digito)):
        return lista

    # inicializa as possíveis "cestas", em que o índice de cestas representa
    # os caracteres 0('a') a 26('z'):
    cestas = np.empty((26, 0)).tolist()

    cestas_ordenadas = []

    for elemento in lista:
        # se o elemento não tem mais dígitos a serem processados, já o
        # coloca na lista ordenada:
        if(len(elemento) - 1 < digito):
            cestas_ordenadas.append(elemento)
        # se ainda necessária ordenação, aloca o elemento no respectiva cesta
        # conforme seu dígito mais significativo, para ser ordenado na
        # chamada recursiva
        else:
            cestas[ord(elemento[digito]) - 97].append(elemento)

    for i, cesta in enumerate(cestas):
        cestas[i] = radix_sort_MSD(cesta, digito + 1)

    for cesta in cestas:
        for elemento in cesta:
            cestas_ordenadas.append(elemento)

    # retorna a lista ordenada:
    return cestas_ordenadas


if __name__ == "__main__":

    lista = ['casa', 'carro', 'correria', 'canivete', 'correndo', 'aluno',
             'clube', 'aula', 'acima', 'correu', 'cambalhota', 'colegio',
             'correr', 'classe']

    lista_ordenada = radix_sort_MSD(lista, digito=0)

    [print(x) for x in lista_ordenada]

Observe que na implementação do Radix Sort MSD são criadas estruturas adicionais em cada recursão: para cada cesta, criamos um vetor de sub cestas em que organizaremos os elementos em função do dígito avaliado. Assim, a natureza recursiva da versão MSD gera maior uso de espaço de memória extra em relação à versão LSD (\(\mathcal{O}(n+d\times k)\) contra \(\mathcal{O}(n+k)\) [6]). Contudo, é possível implementar o Radix Sort MSD sem espaço extra adicional, ou seja, a versão in-place, se utilizarmos uma base binária para representar cada dígito, como veremos no próximo item.

+1 voto
respondida Out 28 por Carlos Piccioni (21 pontos)  
editado Nov 11 por Carlos Piccioni

Radix Sort MSD in-place

Ao operarmos com base binária, cada dígito pode assumir apenas \(k=2\) valores, ou seja, teremos apenas duas possíveis cestas em cada etapa da recursão. Assim, a ideia do Radix Sort MSD in-place é a seguinte: em cada etapa, dividimos a lista em dois segmentos, e realizamos trocas, elemento com elemento, de forma a alocarmos os elementos cujo dígito avaliado seja 0 à esquerda de determinada posição na lista, e os elementos cujo dígito avaliado seja 1 à direita. Logo, teremos uma divisão virtual entre a cesta 0 e a cesta 1. E aplicamos essa ideia recursivamente, dentro de cada cesta, para o próximo dígito a ser processado, até que todos os elementos sejam ordenados na própria lista (in-place). Assim, não há necessidade de uma estrutura adicional (vetor / array) para armazenar resultados intermediários.

Para tal, o algoritmo Radix Sort MSD in-place:

  1. Inicializa o que seria a cesta 0 como aquela à esquerda do primeiro elemento da lista, e o que seria a cesta 1 como aquele conjunto de elementos que estiver a direita do último elemento da lista, ou seja, ambas as cestas iniciam vazias.

  2. Avalia o primeiro elemento que ainda não pertence a nenhuma cesta:

  • se o seu dígito mais significativo for 0, o limite da cesta 0 avança um elemento para a direita (ou seja, este elemento é incluindo na cesta 0). Note que a cesta 0 cresce para a direita;

  • se o dígito mais significativo por 1, move o elemento para o final da lista, e avança o limite da cesta 1 um elemento à esquerda, o que significa que este elemento será incluído na cesta 1. Note que a cesta 1 cresce para a esquerda.

O item 2 é repetido até os limites de ambas as cestas se encontrem, ou seja, quando os \(n\) elementos forem avaliados. Após isso, para cada cesta, reinicia o processo para o próximo dígito mais significativo, enquanto existirem dígitos a serem processados.

Por exemplo, considere ordenar a seguinte lista:

[010, 110, 100, 001, 111, 011, 000, 101]

A ordenação do dígito mais significativo ocorrerá conforme figura a seguir:

A imagem será apresentada aqui.

O processo acima será repetido dentro de cada cesta, até que todos os dígitos dos registros sejam processados.

Observação: Note que esses elementos representam, na base binária, os números 2, 6, 4, 1, 7, 3, 0, 5, respectivamente, na base decimal. Para verificar a representação binária de um decimal, 7 por exemplo, no Python, você pode utilizar o comando:

import numpy as np
np.base_repr(7, base=2)

O caminho inverso pode ser realizado pelo comando:

int('111', base=2)

Abaixo, a implementação recursiva em Python desse algoritmo. Note que a estrutura é semelhante ao Quick Sort, de forma que essa versão do Radix Sort também é conhecida como Binary Quicksort: a função principal, Radix Sort MSD in-place, chama a função ordena, que implementa a lógica apresentada na figura anterior, para o intervalo da lista e o dígito a ser processado conforme especificado. A lista é ordenada in-place, sem necessidade de estrutura de armazenamento adicional (exceto variável auxiliar para realizar a troca de elementos quando necessário), e a função retorna em que posição está a divisão entre a cesta 0 e a cesta 1.

Em seguida, a função Radix Sort MSD in-place faz duas chamadas recursivas, a primeira para realizar nova ordenação dentro da cesta 0 para o próximo dígito mais significativo, e a segunda para a cesta 1. A recursões continuam até não existirem mais dígitos a serem processados (ou alguma sub lista estar vazia).

def ordena(lista, inf, sup, digito):

    # define o limite da cesta 0 como a esquerda do elemento de posição inf
    # e o limite da cesta 1 como a esquerda do elemento de posição sup+1:
    limite_cesta_0 = inf
    limite_cesta_1 = sup + 1

    for j in range(limite_cesta_0, limite_cesta_1):

        # se o dígito avaliado do elemento a direita da cesta 0 for 0:
        if lista[limite_cesta_0][digito] == '0':

            # avança com o limite da cesta 0 para a direita:
            limite_cesta_0 = limite_cesta_0 + 1

        # se não, o dígito avaliado é 1:
        else:

            # troca o elemento com o elemento anterior anterior ao limite do
            # cesta:
            aux = lista[limite_cesta_0]
            lista[limite_cesta_0] = lista[limite_cesta_1 - 1]
            lista[limite_cesta_1 - 1] = aux

            # avança o limite da cesta 1 à esquerda para incorporar o elemento:
            limite_cesta_1 = limite_cesta_1 - 1

    divisao = limite_cesta_0

    return divisao


def radix_sort_MSD_inplace(lista, inf, sup, d, digito):

    # se ainda há elementos na lista fornecida E ainda há dígitos
    # para processar:
    if((inf < sup) and (digito < d)):

        # reordena a lista pelo "digito", dividindo in-place seus elementos
        # em duas cestas, 0 e 1, e retorna a posição da divisão destes:
        divisao = ordena(lista, inf, sup, digito)

        # chamada recursiva para ordenação, pelo próximo dígito, dentro da
        # cesta 0:
        radix_sort_MSD_inplace(lista, inf, divisao - 1, d, digito + 1)

        # chamada recursiva para ordenação, pelo próximo dígito, dentro da
        # cesta 1:
        radix_sort_MSD_inplace(lista, divisao, sup, d, digito + 1)

    # apenas para fins didáticos:
    else:
        # não há itens a ordenar (lista vazia) ou todos os dígitos já foram
        # processados, então não faz nada.
        pass


if __name__ == "__main__":

    lista = ['010', '110', '100', '001', '111', '011', '000', '101']

    radix_sort_MSD_inplace(lista, 0, len(lista)-1, d=3, digito=0)

    print("Lista ordenada:", lista)

Observação: por simplificação, os elementos estão no formato de strings. Também poderíamos converter outros formatos para uma representação binária que garanta o ordenamento desejado, conforme o problema em questão.

A complexidade do Radix Sort MSD in-place é \(\mathcal{O}(d\times n)\): d níveis de recursão e, em cada nível, n elementos serão avaliados pelas diferentes instâncias recursivas. Como o número de dígitos binários (d) na aplicação do Radix Sort MSD in-place em geral é constante, o algoritmo atinge uma complexidade linear em \(n\).

Referências:

  1. CORMEN, Thomas H. et al. Introduction to algorithms. MIT press, 2009.
  2. www2.dc.ufscar.br/~mario/ensino/2019s1/aed2/aula16.pdf
  3. www.dainf.ct.utfpr.edu.br/~fabro/ensino/EstruturadeDados2/OrdenacaoLinear.pdf
  4. www2.dc.ufscar.br/~mario/ensino/2019s1/aed2/aula16.pdf
  5. en.wikipedia.org/wiki/Radix
  6. www.cs.emory.edu/~cs253002/share/spring2020/0505/msdradixsort.pdf
comentou 5 dias atrás por Gustavo Medeiros (36 pontos)  
Resposta extremamente rica e clara. Acredito que existe um \(\textit typo\) no \(11^o\) parágrafo. Na sentença “o que pode mais interessante” pode estar faltando um “ser” entre pode e mais
A atenção nos detalhes de como os diferentes processos de ordenação ocorrem nos permite compreender as diferenças entre suas complexidades de tempo e de espaço.
A aplicação do Radix MSD com caracteres é, em especial, interessante quando consideramos o PostMan Sort Algorithm. Tal algoritmo é usado nos correios e é uma derivação do Radix MSD justamente pelo fato de não haver a necessidade de padronizar os elementos para que todos tenham a mesma chave, como ocorre com o Radix LSD (nesse caso os elementos seriam \(\textit strings\) de caracteres), fazendo com que \(\it strings\) de menor tamanho sejam classificadas com um numero menor de recursão, tornando a sua adoção para essa atividade mais vantajoso. A separação em \(\textit buckets\) também se mostra útil pelo fato de agrupar correspondências em subconjuntos que representam localidades e, recursivamente, em outros subconjuntos que são outras localidades mais especificas que os subconjuntos anteriores definiam.
...