Baixe o app para aproveitar ainda mais
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.
Compartilhar