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:
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:
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);
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.