ATIVIDADE III - PESQUINA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO

Prévia do material em texto

Os algoritmos do tipo ordenação e intercalação dividem os arquivos em
pequenas frações, ordenando e intercalando os resultados em duas fases:
ordenação e intercalação. Podemos listar os métodos de intercalação
externa como: Intercalação balanceada de vários caminhos; seleção por
substituição e intercalação polifásica. (FERRAZ, 2003).Ao longo da
unidade, verificamos que boa parte dos métodos de ordenação externa
usa a seguinte estratégia geral: passar primeiro pelo arquivo a ser
ordenado, dividindo-o em blocos sobre o tamanho da memória interna e
classificar esses blocos. Em seguida, mesclar os blocos ordenados,
fazendo várias passagens pelo arquivo, criando blocos ordenados
sucessivamente maiores até que todo o arquivo seja classificado. Os
dados são acessados de maneira sequencial com mais frequência, uma
propriedade que torna esse método apropriado para a maioria dos
dispositivos externos. Como a maior parte do custo de um método de
ordenação externa é para entrada e saída, podemos obter uma medida
aproximada do custo de uma ordenação de mesclagem contando o
número de vezes que cada palavra no arquivo é lida ou gravada.
(FERRAZ, 2003)
Referência:FERRAZ, I. N. Programação com arquivos. Barueri, São Paulo:
Manole, 2003.
Considerando essas informações e os conteúdos estudados, escolha dois
métodos de intercalação externa e elenque sobre os conceitos e
diferenças de sua aplicabilidade. Após isto, considere um arquivo
armazenado em uma fita de entrada: (B T P S U J M H B M E N F S H J M
H F Y B N Q M F); estes devem ser classificados e colocados em uma fita
de saída, usando o método de ordenação externa de vários caminhos. A
atividade tem como objetivo principal ordenar essa fita com 25 registros,
colocando-os em uma fita de saída, considerando a memória interna com
capacidade de três registros e que tenha seis unidades de fita magnética
disponível.
Resposta:
INTERCALAÇÃO BALANCEADA DE VÁRIOS CAMINHOS
Conceito e aplicabilidade: Intercalação balanceada de vários caminhos
combina dois ou mais blocos.
● Na primeira passada sobre o arquivo: quebra em blocos do tamanho
de memória interna disponível;
● Cada bloco é ordenado na memória interna;
● Blocos ordenados são intercalados através de várias passadas
sobre arquivo;
● A cada passado, blocos ordenados cada vez maiores são criados.
É fundamental reduzir o número de passada de arquivo.
IMPLEMENTAÇÃO POR MEIO DE SELEÇÃO POR SUBSTITUIÇÃO
Conceito e aplicabilidade: Implementação por meio de seleção por
substituição, é uma implementação muito parecida com a intercalação
balanceada, porém, sofre um acréscimo da abordagem de filas por
prioridades, implementadas por um heap. A implementação é eficiente e
elegante e pode ser utilizada na primeira passada sobre arquivo para
quebrar em blocos e na intercalação.
● Na primeira passada: Pega a menor chave em memória (usando
heap);
● Lê próximo item do arquivo;
● Se o próximo item é menor que o item que está saindo, marca o item
para o próximo bloc;
Sobre os métodos de intercalação podemos dizer que as classificações
no que tange os métodos de ordenação são conhecidos como: ordenação
interna, onde o arquivo pode ser ordenado em uma memória principal, e a
ordenação externa, não cabe na memória principal.
A diferença entre os métodos está no registro onde uma pode ser
imediatamente acessada, no caso da ordenação interna, e a outra os
registros são acessados de maneira sequencial.