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

Prévia do material em texto

ATIVIDADE 3.1 (A3)
07.1 (PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO)
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.
7 SEMESTRE DE 2023 (BLOCO 1) - 1o PROVA
ATIVIDADE 3.2 (PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO)
7 SEMESTRE DE 2023 (BLOCO 1) - 1o PROVA
RESPOSTA
Intercalação Balanceada de Vários Caminhos
Intercalação balanceada de vários caminhos combina dois ou mais blocos ordenados em um único bloco 
ordenado selecionando apropriadamente os itens dos blocos.
• Na primeira passada sobre o arquivo quebra em blocos do tamanho da memória internadisponível;
• Cada bloco é ordenado na memória interna;
• Blocos ordenados são intercalados através de várias passadas sobre o arquivo;
• A cada passada, blocos ordenados cada vez maiores s ão criados.
É fundamental reduzir o número de passadas sobre o arquivo.
Implementação Por Meio de Seleção Por Substituição
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 prioridade,implementadas por uma heap. A 
implementação é eficiente e elegante e pode ser utilizada na primeira passada sobre o arquivo para quebrar em 
blocos e na intercalação.
• Na primeira passada pega a menor chave na memória (usando o heap);
• Lê o próximo item do arquivo;
• Se o próximo item é menor que o item que está saindo, marca para o próximo bloco;
• Quando o item marcado vai para o topo da fila de prioridades, o bloco corrente é encerr ado eo novo bloco 
ordenado é iniciado.
• Ao finais vários blocos ordenados são obtidos.
O arquivo armazenado em uma fita de entrada considerando vinte e cinco registros. Estes devem estar 
classificados e colocados em uma fit a de saída, usando o método de ordenação externade vários caminhos. A 
atividade tem como objetivo principal ordenar essa fita com vinte e cincoregistros, colocando-os em uma fita de 
saída, considerando a memória interna com capacidade detrês registros e que tenha seis unidades de fita magnética
disponível.
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
Considerando a memória interna com capacidade de três registros;
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
Fita 1: BPT EMN BFY
Fita 2: JSU SFH QMN
Fita 3: BMH JHM F
BJB B SBH J UP S
MJB B BHU M P T
JBH H HUT P U
Fita 4: BBHJMPSTU
Fita 5: EFHHJMMNS
Fita 6: BFFMNQY
Fita 1: BBBBEFFFHHHJJMMMMNNPQSTUY
Fita 2:
Fita 3:
Fita 4: BMJBBHTUP
Fita 5: EFHHJMMNS
Fita 6: BFFMNQY
7 SEMESTRE DE 2023 (BLOCO 1) - 1o PROVA
ATIVIDADE 3.2 (PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO)
7 SEMESTRE DE 2023 (BLOCO 1) - 1o PROVA
RESPOSTA DO PROFESSOR
Avaliação final do texto: 10 
Comentários
7 SEMESTRE DE 2023 (BLOCO 1) - 1o PROVA