Upload
mauricio-volkweis-astiazara
View
402
Download
1
Embed Size (px)
DESCRIPTION
Baixe mais arquivos em http://pastadomau.wikidot.com. Trabalho que apresenta o algoritmo de ordenação de dados por distribuição de chaves.
Citation preview
UNIVERSIDADE LUTERANA DO BRASILCOMUNIDADE EVANGÉLICA LUTERANA “SÃO PAULO”
Reconhecida pela Portaria Ministerial nº 681 de 07/12/89 – DOU de 11/12/89Campus Torres
Ordenação de Dados por Distribuição de Chaves
Estrutura de Dados II
Igor Casa Nova dos SantosUílson Zanetti Gomes
Mauricio Volkweis AstiazaraHenrique Oliveira
Professor Leonardo PereiraTorres, Abril de 2002
2
Sumário
■ Introdução■ 1 Origem■ 2 Base
– 2.1 Princípio da Limitação de Dígitos– 2.2 Princípio do Valor pela Posição– 2.3 Aplicando os Dois Princípios
■ 3 Algoritmo– 3.1 Código– 3.2 Aplicação
■ 4 Vantagens e Desvantagens■ Conclusão
3
Introdução
■ Existem diversos algoritmos utilizados para a ordenação de dados
■ Cada um apresenta características específicas, com vantagens e desvantagens
■ Veremos um destes algoritmos: ordenação de dados por distribuição de chaves
4
1 Origem
■ Também conhecido como Radixsort, Algoritmo das Raízes e Indexação Direta
■ Criado para máquinas de ordenação de cartões perfurados
■ Resistiu ao tempo e foi utilizado em computadores digitais
5
2 Base
■ Diferente dos outros métodos de ordenação que usam comparação e troca
■ Se baseia em duas características do sistema numérico arábico:– Princípio da Limitação de Dígitos– Princípio do Valor pela Posição
6
2.1 Princípio da Limitação de Dígitos
■ O número de dígitos (caracteres) usados numa base numérica é limitado
■ A quantidade de números que podem representar quando combinados é infinita
Base Numérica Dígitos (Caracteres)Decimal 0, 1, 2, 3, 4, 5, 6, 7, 8, 9Binária 0, 1Hexadecimal 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
7
2.1 Princípio da Limitação de Dígitos
■ O algoritmo já “conhece” a ordem correta dos dígitos da base numérica (decimal)
■ Logo, pode ordenar um vetor com dados de no máximo um dígito
8
2.2 Princípio do Valor pela Posição
■ O valor de cada dígito muda de acordo com a posição em que ocupa no número
■ Exemplos:
■ Logo, qualquer dígito à direita representa mais que qualquer dígito à esquerda
Valor do Dígito na PosiçãoBaseN 3 2 1
B Dígito * B(N – 1) Dígito * B2 Dígito * B1 Dígito * 1Decimal Dígito * 10(N – 1) Dígito * 100 Dígito * 10 Dígito * 1Binária Dígito * 2(N – 1) Dígito * 4 Dígito * 2 Dígito * 1Hexadecimal Dígito * 16(N – 1) Dígito * 256 Dígito * 16 Dígito * 1
9
2.3 Aplicando os Dois Princípios
■ Inicia-se ordenando os dados pelo dígito da posição 1 (menos significativo)
■ Para essa ordenação é usado um algoritmo baseado no Princípio da Limitação de Dígitos
■ Passa-se então para a ordenação pelo dígito da posição 2, depois 3 e assim por diante, até o número máximo de dígitos que os dados podem ter
10
3 Algoritmo
■ Um exemplo de algoritmo em português estruturado e a sua aplicação sobre um vetor exemplo
■ 3.1 CódigoPrograma Principal:InícioPara cada posição começando pela 1 até a máxima que as chaves podem ter {
Ordenar o vetor pelo dígito dessa posição;
}Fim.
11
3.1 Código
SubrotinaOrdenar Vetor pelo Dígito da Posição X:InícioCriar um vetor chamado Fila, da posição 0 até a 9, de filas;Para cada elemento do Vetor {
F = Obter o dígito desse elemento na Posição X;
Colocar esse elemento na Fila F;}
12
3.1 Código
A Posição Atual do Vetor é o início;Para Y = 0 até 9 {
Colocar cada elemento da Fila[Y] no Vetor a partir da Posição Atual;A Posição Atual do Vetor é o seu próprio valor somado ao tamanho da
Fila[Y];}
Fim;
13
3.2 Aplicação
■ Vetor exemplo a ser ordenado:Posição Dado (Chave)
1 152 23 214 115 86 17 308 99 1010 6
14
3.2 Aplicação
■ Passo 1:Programa Principal:InícioPara cada posição começando pela 1 até a máxima que as chaves podem ter {
Ordenar o vetor pelo dígito dessa posição;
}
15
3.2 Aplicação
■ Passo 2:SubrotinaOrdenar Vetor pelo Dígito da Posição X:InícioCriar um vetor chamado Fila, da posição 0 até a 9, de filas;
16
3.2 Aplicação
■ O Vetor de filas “Fila” criado:Fila Elementos0123456789
17
3.2 Aplicação
■ Passo 3:Para cada elemento do Vetor {
F = Obter o dígito desse elemento na Posição X;
Colocar esse elemento na Fila F;}
18
3.2 Aplicação
■ Ao fim do laço:Fila Elementos0 30, 101 21, 11, 12 2345 156 678 89 9
19
3.2 Aplicação
■ Passo 4:Para Y = 0 até 9 {
Colocar cada elemento da Fila[Y] no Vetor a partir da Posição Atual;A Posição Atual do Vetor é o seu próprio valor somado ao tamanho da
Fila[Y];}
Fim;
20
3.2 Aplicação
■ Vetor ordenado pelas unidades:Posição Dado (Chave)
1 302 103 214 115 16 27 158 69 810 9
21
3.2 Aplicação
■ Passo 5:– Com o fim da subrotina de ordenação por dígito,
volta-se ao programa principal e é encerrada a primeira volta do laço descrito no Passo 1
– Segue-se o que foi descrito nos Passos 2 e 3, mas com o parâmetro da rotina de ordenação por dígito 2
22
3.2 Aplicação
■ Vetor ordenado pelas unidades e dezenas:Fila Elementos0 1, 2, 6, 8, 91 10, 11, 152 213 30456789
23
3.2 Aplicação
■ Passo 6:– É repetido o processo do passo 4, que forma o
vetor novamente a partir das filas– É o fim da subrotina e volta-se ao programa
principal– Como foi atingido o número máximo de dígitos (2)
é o fim do laço e do programa
24
3.2 Aplicação
■ Vetor ordenado ao fim do programa:Posição Dado (Chave)
1 12 23 64 85 96 107 118 159 2110 30
25
4 Vantagens e Desvantagens
■ Utiliza pouco processamento (comparações) em relação aos outros algoritmos
■ Rápido para dados com poucos dígitos
■ É necessário saber de antemão o número máximo de dígitos dos dados
■ Os passos intermediários, como a separação do dado em dígitos, podem usar mais processamento que a própria ordenação.
26
Conclusão
■ Deve ser utilizado em situações específicas, como por exemplo:– Quando se sabe o antecipadamente o tamanho
máximo dos dados– Quando o número de dígitos dos dados não é
muito grande■ Se usado em situações genéricas a eficiência
pode não corresponder ao desejado