Algoritmo de ordenação Radix Sort

Páginas: 6 (1409 palavras) Publicado: 21 de janeiro de 2015
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: 
 
          O(g(n))  =  { f(n)  : existem constantes positivas c e n0 tais que  
                                      0 ≤  f(n)  ≤  c.g(n) para todo n ≥ n0 }  
 
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 
O(1)  

Constante 

O(log(n))  
c

 

Logarítmica 

O((log(n)) )  Polilogarítmica 

O(n)  

Linear 

O(n²)  

Quadrática 

O(nc)  

Polinomial 

O(cn)  

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 ...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • ALGORITMOS DE ORDENAÇÃO BUBBLE SORT e SELECTION SORT
  • Comparação entre os algoritmos de ordenação de dados: buble sort, quick sort, selection sort, inserction sort,...
  • Radix sort
  • Radix Sort
  • Ordenação radix, counting , buket
  • Algoritmos de ordenação
  • Algoritmos de ordenação
  • Algoritmos de ordenação

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!