Projeto e Análise de Algorítimos - Radix Sort

Prévia do material em texto

Algoritmo de ordenação Radix Sort: Conceitos, Análise e Aplicações
Adriano Jorge Vitorino Melo Júnior1, Diogenes Laertius Silva Oliveira Filho1, João Vitor Silva Oliveira1, José Arnóbio de Oliveira Júnior1, Pedro Victor Vieira de Paiva1
1Universidade Federal de Alagoas (UFAL)
CEP: 57309-005 – Arapiraca – AL – Brazil
{adrianobatalha, diogeneslaertiussof, joao130693, arnobiojroliveira, enemy537}@gmail.com
	 	
Abstract. Sorting Algorihm are increasingly used because the amount of information that is generate every day, requiring it to be retrieved with satisfatory efficiency. In this article, will be discuss a study about Radix Sort sorting algorithm among its features and efficiency.
Resumo. Algoritmos de ordenação são cada vez mais utilizados devido a quantidade de informações que são geradas a cada dia, sendo assim necessário que esta seja recuperada com uma eficiência satisfatória. Nesse artigo será discutido um estudo relativo ao método de ordenação Radix Sort dentre suas características e eficiência.
1. Introdução
Os algoritmos de ordenação surgiram com a crescente urgência em organizar um conjunto de informações. Com o passar do tempo suas utilidades e aplicações em diversas áreas o tornaram cada vez mais objeto de estudo, visando um aprimoramento e descobertas de novos algoritmos que forneçam uma velocidade de processamento cada vez maior que os anteriormente propostos.
	O procedimento utilizado no Radix Sort consiste em ordenar um vetor de n números inteiros com uma quantidade constante de dígitos, por meio de ordenações parciais, dígito a dígito. Este funcionamento, comparações com outros algoritmos e suas aplicações serão detalhadamente discutidos ao longo deste artigo.
1.1. Análise de algoritmo
Existem inúmeros algoritmos de ordenação e propostas de abordagem para ordenar sequências diversas, no entanto se faz necessário quantificar a eficiência das técnicas utilizadas para que estas façam uma análise realmente significativa ao estudo. Para isso, a análise de algoritmo propõe ideias usadas para determinar as características de performance de algoritmos e possibilitar uma escolha inteligente entre métodos concorrentes [Knuth 1998].
Para mensurar a complexidade de dois algoritmos é conveniente utilizar uma notação que descreva o tempo de execução assintótico dos mesmos. Entre várias maneiras de dimensionar esta complexidade, a que indica que a função de crescimento é limitada superiormente por outra é a notação O(n) (O-grande), definida por:
Fórmula 1. Definição da notação Big-O.
Fazendo uso dessa notação é possível classificar o quão rápido é o crescimento de uma função:
	Notação
	Nome
	
	Constante
	
	Logarítmica
	
	Polilogarítmica
	
	Linear
	
	Quadrática
	
	Polinomial
	
	Exponencial
Tabela 1. Ordem de crescimento de funções assintóticas big-O.
2. Revisão Bibliográfica
Bentley, McIlroy e Bostic (1993) em Engineering Radix Sort, descrevem um algoritmo de excelente performance assintótica para tratar strings com comparações sem relação com o valor mas sim com chaves, sendo de implementação mais simples e que lida de forma mais fácil com grandes endereços de memória. Nesse mesmo artigo também são descritas as formas de ordenamento usando o dígito mais significativo (MSD) e ao se comparar com o método QuickSort, houve uma diferença de 100% no ganho de desempenho.
	Em Fast Algorithms for Sorting and Searching Strings, de Bentley e Sedgewick (1997), são apresentados conceitos teóricos para ordenação e busca de informações multichaveadas e é proposto o comparativo entre a implementação em linguagem C dos métodos QuickSort e RadixSort exemplificando de forma prática os conceitos de ordenação baseada em chaves.
3. Radix Sort
O algoritmo de ordenação Radix Sort (ou ordenação de raiz) é usado pelas máquinas de ordenação de cartões que agora são encontradas apenas em museus. Os cartões eram organizados em 80 colunas, e em cada coluna pode ser feita uma perfuração de 13 posições [Guimarães 2013]. 
No caso dos cartões, o ordenador poderia ser disposto em ordem mecanicamente para averiguar uma determinada coluna de cartões em uma estrutura de dados pilha e distribuir o mesmo em uma das 13 caixas, dependendo de onde o cartão foi perfurado. Logo após, um operador pode juntar os cartões caixa por caixa, de maneira que onde foi perfurado com a primeira posição fique sobre os que foram perfurados na segunda e assim sucessivamente.
3.1. Conceito
O Radix Sort pertence a classe dos algoritmos de ordenação e foi criado a partir da necessidade de manter a ordenação de cartões perfurados que usavam código BCD (Binary Coded Decimal) que além de serem organizados deveriam ser interpretados para obterem seu respectivo significado. Com isso surgiu o Radix Sort que organizava e identificava itens a partir de uma chave única. Dentre seus principais atributos estão a estabilidade e a rápida ordenação, apesar disso o mesmo não é tão popular como outros pertencentes a mesma classe de algoritmos [Guimarães 2013].
Devido ao processamento de dígitos individuais, números pertencentes a classe dos inteiros podem representar palavras compostas e pontos flutuantes. O Radix Sort pode ser classificado em dois tipos, sendo de acordo com o modo de ordenação, são eles: LSD (Least Significant Digit - Digito Menos Significativo) e MSD (Most Significant Digit - Digito Mais Significativo).
O Radix Sort do tipo LSD, como o próprio nome já diz, começa sua ordenação priorizando as chaves pequenas em relação as longas e quando duas ou mais possuírem o mesmo tamanho, serão priorizadas de acordo com a ordem lexicográfica assim como nos dicionários. A ordem desse algoritmo é de O(nk), em que n corresponde a quantidade de chaves e k ao tamanho da chave média. Quando se tratam de várias chaves de tamanhos diferentes, as mesmas podem ser organizadas ainda em conjuntos de mesmo comprimento evitando grande fluxo de informações em forma de lista. 
A sequência de como os dígitos são processados nesse tipo de algoritmo é apresentada de maneira inversa no Radix Sort MSD. Consiste em ir buscando uma ordenação de acordo com a ordem lexicográfica, que não é a primeira opção na hierarquia de ordenação no tipo LSD. Nos casos como 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 a ordenação irá ser apresentada da seguinte forma: 1, 10, 2, 3, 4, 5, 6, 7, 8, 9 uma vez que o dígito 10 sendo o maior de todos, como contém o dígito ‘1’, algoritmo utiliza este elemento. Devido a isso seu uso é mais indicado para ordenação de strings.
A eficiência do algoritmo está diretamente relacionada a técnica de partição das chaves usadas. Assim como demais algoritmos de ordenação o Radix Sort não possui uma grande eficiência quando se trata de uma pequeno número de chaves, devido a isso não é aconselhável ordena-ló com um valor inferior a 16 chaves [ELIS 1985]. O algoritmo examina cada byte presente em uma chave ao menos duas vezes, uma quando efetua a contagem da frequência dos valores dos bytes presentes e outra quando efetua o particionamento dos mesmos. Um grande número de partições pode ser estruturado, podendo ainda as mesmas serem separados internamente por subconjuntos.
Algumas das vantagens deste tipo de ordenação são que: é um algoritmo estável, preserva a ordem de chaves iguais, apresenta tempo linear e é bastante eficiente quando o número de registro é grande mas o tamanho da chave é pequeno.
Por outro lado, existem determinadas desvantagens como: ter um mal funcionamento quando a chave é muito grande, uma vez que o custo do algoritmo é proporcional ao tamanho da chave e o número de elementos a serem ordenados. Além disso, precisam de memória auxiliar para ordenar o conjunto.
Figura 1. Pseudo-código do algoritmo Radix Sort
4. Comparações
Comparar algoritmos que realizam ordenação em busca do “melhor” não é uma tarefa fácil pois não existe um único método que seja ótimo em todos os cenários possíveis, já que para uma lista de valores existem diversas organizações como: parcialmenteordenados, ordenação decrescente, semi-ordenado ou posicionamento aleatório. 
Da mesma forma que são inúmeros os melhores algoritmos para as determinadas situações das listas de valores a serem ordenados, são muitas as formas de comparar o quão melhor uma forma de ordenação é em relação a outra, seja analisando o número de comparações, o número de trocas entre os elementos ou mesmo a complexidade total do método.
4.1. Comparações entre algoritmos não-comparacionais
Nesse artigo, tratamos da análise de um algoritmo que não realiza comparações entre os valores propriamente ditos, mas sim comparando o comprimento das chaves que são usadas para referenciar valores. Métodos como o Counting, Bucket, Radix, Radix MSD e Radix LSD são alguns exemplos de técnicas que atacam a ordenação verificando as chaves.
Sendo assim, na tabela abaixo serão comparados esses mesmo algoritmos organizados segundo a pior, melhor e média situação em relação a quantidade de permutações dos valores e além disso serão descritas algumas vantagens e desvantagens.
	Alguns desses algoritmos assumem que os valores são referenciados por chaves únicas, denotados por n << 2k .
	Nome
	Caso Médio
	Pior Caso
	n << 2k
	Vantagens e Desvantagens
	Bucket Sort
	
	
	Não
	1. Estável e Rápido. 
2. Válido apenas para intervalos bem definidos para as chaves.
3. Usado em casos onde é possível calcular a chave a partir do endereço do conjunto.
	Counting Sort
	
	
	Sim
	1. Estável, usado para valores repetidos
2. Comumente usado como subrotina do RadixSort.
3. Válido no intervalo 
	Radix Sort
	)
	)
	Não
	1. Estável, padrão para ordenar chaves.
	Nome
	Caso Médio
	Pior Caso
	n << 2k
	Vantagens e Desvantagens
	MSD Radix Sort
	)
	)
	Não
	1. Melhora a ordenação do radix, porém instável. 
2. Eficiente para ordenar grandes quantidade de chaves sem que ocorra deadlock.
3. No pior dos casos pode ocorrer fragmentação dos dados.
4. Inspeciona apenas o dígito mais significante.
	LSD Radix Sort
	)
	.2s)
	Não
	1. Método de ordenação estável.
2. Inspeciona todos os caracteres da entrada.
Tabela 2. Comparação entre ordenamento não-Comparacional (ADITYA, 2008).
	Com base na tabela acima, é possível aferir que o RadixSort é virtualmente o melhor algoritmo de ordenação para chaves não necessariamente únicas já que tanto em casos onde o cenário é favorável ou não, a ordem de complexidade da ordenação não se altera, e em comparação com o RadixSort MSD, que se utiliza do dígito mais significativo para ordenar os valores associadas as chaves, o RadixSort perde em alguns aspectos como a dificuldade (custo) de lidar com chaves extensas em relação ao MSD, que otimiza a complexidade das chaves. Mesmo com essas complicações o RadixSort ainda se sobressai sobre os demais devido a sua estabilidade e resultado já comprovados e garantidos.
4.2. Comparações entre as implementações dos algoritmos
Com sua implementação realizada na linguagem de programação Java o mesmo demonstra maior robustez e rapidez em comparação a outros algoritmos de ordenação como HeapSort e QuickSort, preservando a existência de ordem em chaves iguais.
Apesar dos vastos adjetivos o algoritmo, assim como outros, não funcionam 100% em todos os casos, existe casos como no complemento de pequenas chaves, por exemplo, no qual tornam o uso do algoritmo discutível, além de que o uso do mesmo requer uma forma padrão de dividir as chaves de tamanhos fixos, sempre. 
	
5. Aplicações
O Radix Sort foi desenvolvido inicialmente para máquinas de ordenação de cartões perfurados. Hoje é um dos algoritmos de ordenação mais utilizados, devido à sua rapidez e simplicidade de implementação. Em casos como: Dada uma seqüência de caracteres N, encontrar a maior substring repetida, algoritmos paralelos, entre outros, o referido procedimento é muito eficiente.
	Dentre vários cenários em que o algoritmo Radix Sort é utilizado, a melhor situação de sua aplicação é em casos que a ordenação em tempo linear é o método mais adequado, uma vez que o procedimento ordena vetores de números inteiros com uma quantidade constante de dígitos, fazendo ordenações parciais, digito a digito.
	Uma grande área de pesquisa com foco na implementação do algoritmo de ordenação Radix Sort está sendo feita na optimização de GPU’s (Graphics Processing Units) NVIDIA para proporcionar altas performances de computação. No entanto a diferença fundamental de arquitetura entre CPU e a GPU é a complexidade por trás da GPU e a diversidade de específicações da CPU. As grandes dificuldades entre a CPU e a GPU é que o tempo consumido para se ter resultados passa a ser mais difícil de ser corrigido e atualizado. O Radix Sort é intitulado como o primeiro e mais importante algoritmo de ordenação demonstrando grande eficiência para um número representativo de GPU’s NVIDIA com uma grande variedade de arquivos, de maneira que quando o algoritmo é executado na GPU com grande frequência de processamento, o número de elementos por thread deve ser incrementado porque a frequência do processador é rápido como as operações que podem ser computadas.
	Figura 2. Comparativo do algoritmo melhorado em detrimento a outros dois outros Radix Sort implementados para CUDPP and Satish usuários. O exemplo acima conta com apenas uma GPU. 
Figura 3. IBM 082 - Máquina ordenadora de cartões
A série 80 de máquinas ordenadoras de cartões perfurados da IBM poderia receber até 13 unidades e utilizava o algoritmo Radix Sort para realizar o processo de ordenação. A IBM 082 foi criada em 1949, onde foi projetada para empresas de pequeno porte e comportava 1200 cartões e conseguia passar 650 cartões por minuto. 
Assim como a ordenação é uma das áreas que busca estudar problemas que as envolve, da mesma forma é a computação paralela. Zagha e Blelloch (1991) em Radix Sort For Vector Multiprocessors propõe uma versão do Radix Sort para multiprocessamento de vetores, visando assim melhorar a área de teorias da ordenação paralela. Pensando na projeção do algoritmo voltado para o contexto da paralelização e implementado-o em 8 processadores da máquina CRAY Y-MP (supercomputadores desenvolvidos e manufaturados pela Cray Research), o estudo provou que o algoritmo Radix Sort é extremamente eficiente se utilizado junto ao CRAY Y-MP, trazendo grandes benefícios no que se refere a multiprocessos. 
Este estudo foi iniciado analisando desde as bases do Radix Sort até elevar-se ao nível de multiprocessamento, apresentando um alto grau de paralelismo do algoritmo. No artigo, o tipo de algoritmo usado é o LSD (Least Significant Digit) que transforma as chaves em dígitos e ordena um a um. A partir desse momento, o Distribution Sort (ou Counting Sort, que também é um algoritmo de ordenação e dentre suas qualidades está a simplicidade e rapidez) [ELIS 1985] é utilizado para ordenar cada dígito já separado, começando pelo menos significativo. Algumas técnicas para mapear o algoritmo são citadas durante o processo como: processadores virtuais, ranking de loop e layout de memória de processo.
	Figura 4 - Algoritmo em execução com três dígitos ao mesmo tempo, na qual são quebrados em partes e o Distribution Sort entra em execução.
6. Conclusão
Levando-se em consideração os aspectos apresentados relativos ao algoritmo de ordenação Radix Sort, deixa claro que mesmo anos após sua criação o algoritmo ajudou na derivação de outros preservando ainda suas características originais não desviando de seus objetivos que são ordenação e rapidez, além da simplicidade e intuitividade na implementação que sofreu inclinações com o passar dos anos. Proposto nos anos 90 [McIlroy e Bostic, 1993], o Radix Sort foi de fundamental importância para a ordenação de valores não numéricos e referenciados por chaves extensas, e quando comparada com métodos denotados comparacionais, como Quick Sort, demonstrou eficiência e robustez maiores.
O algoritmo Radix Sort demonstra grande eficiência quando lida com um número não tão grandesde chaves devido ao tempo total de ordenação será diretamente proporcional ao tamanho da maior chave e a quantidade das mesmas. As comparações entre o Radix e outros métodos não-Comparacionais demonstra que mesmo sendo a forma tradicional de organizar valores por chaves, ainda é a maneira mais confiável e robusta de se realizar.
	Ordenação é o processo computacional de arranjamento de coleções de itens de dados em uma ordem pré-determinada fazendo com que a frequente performance dos computadores seja melhorada. Tais algoritmos podem ser classificados atráves de sua ordenação de duas maneiras, particionamento de dados e triagem por algoritmos de comparação (Lau, 1992). Além das duas grandes categorias comumente usadas do Radix Sort como o MSD e o LSD outras categorias estão sendo desenvolvidas como o ARL que tem como característica a remoção do espaço extra requerido por subgrupos pequenos e o MSL (Map Shuffle Loop) que é uma modificação do ARL. A categoria MSL se mostrou tão rápido quanto outros algoritmos comparados em outros estudos.
Essas quatro categorias compõem os estudos atuais que são feitos em torno desse grande algoritmo de ordenação que tem uma execução pseudo linear. 
Referências
[1] Knuth, E. Donald. The art of computer programming, volume3: (2nd ed.) sorting and searching, p. 3.,1998.
[2] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., ALGORITMOS – Tradução da 2º edição americana – Teoria e Prática, Editora CAMPUS, Rio de Janeiro, 2002. 
[3] O Algoritmo RadixSort - Jornal PETNews , Gleyser Guimarães 
[http://www.dsc.ufcg.edu.br/~pet/jornal/junho2013/materias/historia_da_computacao.htm]
[4] M. Zagha and G. E. Blelloch, “Radix Sort for vector multiprocessors,”in Proc. ACM/IEEE Conference on Supercomputing, 1991, pp. 712–721.
[5] ELLIS, J. K. (1985). Distribution counting as a method for sorting test scores. Belulvior Research Methods, Instruments, & Computers, 17, 419-420.
[6]Davis,I.J. A Fast Radix Sort. The Computer Journal 35, 6, 636-642 - August 1992.
[7] Aditya Dev Mishra & Deepak Garg.(2008,DEC). “Selection of Best Sorting Algorithm ", International journal of intelligent information Processing II. pp.363-368. Disponível em : http://academia.edu/1976253/Selection_of_Best_Sorting_Algorithm. 
[8] Bonan Huang, Jinlan Gao et. al. Xiaoming Li “An Empirically Optimized Radix Sort for GPU”, 2009 IEEE International Symposium on Parallel and Distributed Processing with Applications.
[9] McIlroy, P.M. e Bostic, K., M.D. Engineering Radix Sort. Computing Systems 6, 1 (1993), 5-27.
[10] Bentley, J. L., e Sedgewick, R. 1997. Fast algorithms for sorting and searching strings. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, pp. 360–369.
[11] Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest . Introduction to Algorithms 3rd Edition.
[12] Amer AL-BADARNEH et.al. Fouad EL-AKER. Efficient Adaptive In-Place Radix Sorting. INFORMATICA, 2004, Vol. 15, No. 3, 295–302.