Radix Sort, aplicação e exemplos

Prévia do material em texto

Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Algoritmo de Ordenação Radix Sort
Conceitos, Análise e aplicações
Adriano Jorge, Diogenes Laertius, João Vitor,
José Arnóbio, Pedro Victor
Universidade Federal de Alagoas
17 de Dezembro de 2014
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 1 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Agenda
1
Introdução
2
O algoritmo Radix Sort
Funcionamento
3
Comparações
4
Aplicações
5
Conclusão
6
Referências
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 2 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Introdução
Os algoritmos de ordenação surgiram com a crescente
urgência em organizar um conjunto de informações.
A principal razão para se ordenar é poder acessar seus
dados de maneira eficiente.
As maneiras como se organizar podem variar, porém
muitas vezes têm em comum o tipo de ordem, sendo
númerica ou lexicográfica.
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 3 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
O algoritmo Radix Sort - Funcionamento
Foi inventado por Harold H. Seward em 1954.
A necessidade de manter a ordenação em Máquinas de
cartões perfurados.
Organizava e identificava itens a partir de uma chave única.
Possui estabilidade e rápida ordenação.
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 4 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
O algoritmo Radix Sort
Figura : Harold H. Seward
Figura : Máquinas de cartões perfurados
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 5 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
O algoritmo Radix Sort
Os 2 subtipos de Radix mais usados são o LSD e o MSD.
Ambos distinguem na prioridade dos dígitos na ordenação.
LSD ou Last Significant Digit:
Começa do dígito menos significativo até o mais
significativo.
Chaves curtas vem antes de chaves longas.
Chaves de mesmo tamanho são ordenadas
lexicograficamente (ordem alfabética).
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 6 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
O algoritmo Radix Sort
MSD ou Most Significant Digit:
Sentido contrário ao LSD.
Usa sempre a ordem lexicográfica.
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 7 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Funcionamento
Sequência Original: 170, 045, 075, 090, 002, 024, 802, 066
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 8 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Funcionamento
Tabela : 1
o
Passo - Digito Menos significativo: 170, 090, 002, 802,
024, 045, 075, 066
Dígito Quantidade Valores
0 2 170
2 2 002, 802
4 1 024
5 2 045, 075
6 1 066
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 9 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Funcionamento
Tabela : 2
o
Passo - Anda uma casa para esquerda, e faz o mesmo
processo do 1
o
passo: 002, 802, 024, 045, 066,170, 075, 090
Dígito Quantidade Valores
0 2 002, 802
2 1 024
4 1 045
6 1 066
7 2 17,075
9 1 090
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 10 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Funcionamento
Tabela : 3
o
Passo - e último passo, para este exemplo, anda uma
casa para à esquerda e repete o passo 1: 002, 024,045,066,075,
090,170,802
Dígito Quantidade Valores
0 6 002,045,075,090,066
1 1 170
8 1 802
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 11 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Figura : Implementação do Algoritmo em C++
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 12 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Comparações entre algoritmos não-comparacionais
Nome Caso Médio Pior Caso n � 2 e k
Bucket Sort O(n.k) O(n
2.k) N ão
Radix Sort O(n.k/s) O(n.k/s) Não
Tabela : Bucket Vs. Radix
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 13 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro VictorIntrodução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Vantagens e Desvantagens
Bucket Sort
Estável e Rápido.
Válido apenas para valores bem definidos.
Usado em casos onde é possível calcular a chave a partir
do endereço do conjunto.
Radix Sort
Estável, padrão para ordenar chaves.
Mal funcionamento quando a chave é muito grande.
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 14 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Comparações entre algoritmos não-comparacionais
Nome Caso Médio Pior Caso n � 2 e k
Counting Sort O(n+2k) O(n+2k) Sim
Radix Sort O(n.k/s) O(n.k/s) Não
Tabela : Counting Sort Vs. Radix
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 15 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Vantagens e Desvantagens
Counting Sort
Estável, usado para valores repetidos.
Comumente usado como subrotina do RadixSort.
Válido no intervalo [0, k].
Radix Sort
Estável, padrão para ordenar chaves.
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 16 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Comparações entre algoritmos não-comparacionais
Nome Caso Médio Pior Caso n � 2 e k
MSD Radix Sort O(n.k/s) O(n.k/s) Não
Radix Sort O(n.k/s) O(n.k/s) Não
Tabela : MSD Radix Sort Vs. Radix
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 17 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Vantagens e Desvantagens
MSD Radix Sort
Melhora a ordenação do radix, porém instável.
Eficiente para ordenar grandes quantidade de chaves sem
que ocorra deadlock.
No pior dos casos pode ocorrer fragmentação dos dados.
Inspeciona apenas o dígito mais significante.
Radix Sort
Estável, padrão para ordenar chaves.
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 18 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Comparações entre algoritmos não-comparacionais
Nome Caso Médio Pior Caso n � 2 e k
LSD Radix Sort O(n.k/s) O(n.k/s.2s) Não
Radix Sort O(n.k/s) O(n.k/s) Não
Tabela : LSD Radix Sort Vs. Radix
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 19 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Vantagens e Desvantagens
LSD Radix Sort
Método de ordenação estável.
Inspeciona todos os caracteres da entrada.
Radix Sort
Estável, padrão para ordenar chaves.
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 20 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Aplicações
Máquinas de ordenação de cartões perfurados.
Figura : IBM 082 Máquina ordenadora de cartões que utiliza Radix
Sort
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 21 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Aplicações
Implementação de GPUs.
Figura : Testes envolvendo o algoritmo e GPU's
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 22 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Aplicações
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 pelo Radix Sort.
Figura : Testes envolvendo o algoritmo e GPU's
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 23 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Conclusão
Ordenação é um processo computacional de arranjamento
de coleções de itens e dados em uma dada ordem.
O algoritmo Radix Sort demonstra grande eficiência
quando lida com um número não tão grandes de chaves.
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.
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 24 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Referências
Aditya Dev Mishra Deepak Garg. (2008)
Selection of Best Sorting Algorithm ", International journal of
intelligent information Processing II. pp.363-368.
Journal Name Disponível em :
http://academia.edu/1976253/Selection
o
f
B
est
S
orting
A
lgorithm.
Bonan Huang, Jinlan Gao et. al. Xiaoming Li. (2009)
An Empirically Optimized Radix Sort for GPU
IEE 2009 IEEE International Symposium on Parallel and Distributed
Processing with Applications.
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 25 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
ConclusãoReferências
Dúvidas?
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 26 / 27
Algoritmo de
Ordenação
Radix Sort
Adriano
Jorge,
Diogenes
Laertius,
João Vitor,
José
Arnóbio,
Pedro Victor
Introdução
O algoritmo
Radix Sort
Funcionamento
Comparações
Aplicações
Conclusão
Referências
Fim.
Adriano Jorge, Diogenes Laertius, João Vitor, José Arnóbio, Pedro Victor (UFAL)Algoritmo de Ordenação Radix Sort 17 de Dezembro de 2014 27 / 27
	Introdução
	O algoritmo Radix Sort
	Funcionamento
	Comparações
	Aplicações
	Conclusão
	Referências