Em 1890 Hermann Hollerith, funcionário do United StatesCensus Bureau que é a agência governamental encarregada pelo censo nos Estados Unidos e um dos fundadores da IBM, desenvolveu, em 1890, uma máquina para realizar as operações de recenseamento da população. A máquina fazia a leitura de cartões de papel perfurados em código BCD (BinaryCoded Decimal). A informação perfurada no cartão era lida em uma tabuladora que dispunha de uma estação de leitura equipada com uma espécie de pente metálico em que cada dente estava conectado a um circuito elétrico.
Antes da utilização da máquina de cartões perfurados, o censo nos Estados Unidos era realizado em 10 anos, o que prejudicava o bom andamento das políticas públicas que precisavam dos dados dos censos para serem melhor planejadas. Após a máquina de Herman Hollerith o censo passou a ser realizado em 1 ano.
O algoritmo RadixSort surgiu com a necessidade de manter a ordenação dos cartões perfurados e isso ocorreu porque o número de cartões que eram necessários cresceu bastante, o que dificultava o controle. Além disso, uma vez perfurados, as folhas ou cartões precisavam ser interpretados para ter algum significado. Era necessário uma forma de interpretar e manter a ordem das folhas, caso contrário, a máquina, que também interpretava os dados, receberia dados errados no processamento das informações.
Foi então que surgiu o algoritmo RadixSort que ordenava cartões perfurados a partir de uma chave única processada por partes. Nesse caso, a chave era um número de 3 dígitos contido no cartão. A ordenação ocorria em 3 fases: na primeira fase, os cartões eram ordenados considerando o dígito menos significativo (mais à direita do número); na segunda fase, considerava-se o dígito do meio e, na terceira fase, o dígito mais significativo. Vejam na imagem a seguir, uma execução do algoritmo com vários números de 3 dígitos.
A forma como o algoritmo funciona pode ser resumida na seguinte estratégia:
Realiza p iterações, onde p é o número de dígitos. E utiliza dois vetores: vOcor, que corresponde ao número de ocorrências de elementos, e vTemp, que é um vetor temporário que mantém os elementos ordenados por um certo dígito.
1 - Inicializa vOcor;
2 - O vetor vOcor recebe o número de ocorrências de cada i-ésimo dígito;
3 - Uma vez preenchido o vOcor, são contabilizados nele os offsets para cada dígito (posições onde iniciam os elementos que possuem certo valor de dígito);
4 - Com base nesses offsets, vTemp recebe os elementos do vetor ordenado pelo i-ésimo dígito;
5 - Transfere-se os elementos de vTemp para vetor;
Uma forma mais divertida de ver o funcionamento do RadixSort é através do vídeo abaixo, que mostra uma dança baseada nas regras desse algoritmo de ordenação:
O RadixSort foi um dos primeiros algoritmos de ordenação a serem desenvolvidos e largamente utilizado nas máquinas de cartões perfurados. Todavia, é necessário destacar que, por ser estável e não efetuar várias comparações, torna-se eficiente quando comparado a outros algoritmos de ordenação, sendo então utilizado até os dias atuais. Porém, possui algumas desvantagens pois nem sempre é fácil otimizar a inspeção de dígitos e só se torna plausível quando o número de dígitos é pequeno.
REFERÊNCIAS
Material da Disciplina Estruturas de Dados e Algortimos - UFCG
Material da Disciplina Algoritmos e Estruturas de Dados II - UFMG
Material da Disciplina Estruturas de Dados - UFS
Grupo PET Computação UFCG, 2013. All rights reserved.
