Pesquisa e ordenação

Prévia do material em texto

Impresso por Carlos, CPF 072.898.164-55 para uso pessoal e privado. Este material pode ser protegido por direitos autorais e não pode
ser reproduzido ou repassado para terceiros. 01/04/2020 11:32:29
 PERGUNTA 1 
 1. Os algoritmos do �po 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 disposi�vos 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 i sto, considere um arquivo 
 armazenado em uma �ta 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 classi�cados e colocados em uma �ta de saída, usando o método de ordenação externa de vários 
 caminhos. A atividade tem como obje�vo principal ordenar essa �ta com 25 registros, colocando-os em 
 uma �ta de saída, considerando a memória interna com capacidade de três registros e que tenha seis 
 unidades de �ta magnética disponível. 
 
 
 INTERCALAÇÃO BALANCEADA DE VÁRIOS CAMINHOS 
 Conceito e aplicabilidade: Intercalação balanceada de vários caminhos combina dois ou mais 
 blocos ordenados em único bloco ordenado selecionando apropriadamente os itens dos 
 blocos. 
  Na primeira passada sobre arquivo: quebra em blocos do tamanho da 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 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 
 Conceito e aplicabilidade: Implementação por meio de Seleção por subs�tuiçã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 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 menor chave na memória (usando heap); 
  Lê próximo item do arquivo; 
  Se próximo item é menor que o item que está saindo, marca item para próximo bloco; 
Impresso por Carlos, CPF 072.898.164-55 para uso pessoal e privado. Este material pode ser protegido por direitos autorais e não pode
ser reproduzido ou repassado para terceiros. 01/04/2020 11:32:29
  Quando item marcado vai para topo da fila de prioridades, bloco corrente é encerrado 
 e novo bloco ordenado é iniciado; 
  Ao final, vários blocos ordenados são obtidos. 
 
 Arquivo armazenado em uma �ta de entrada considerando 25 registros 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 obje�vo 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. 
 
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: B T P E M N Y B F 
 Fita 2: J S U S F H Q M N 
 Fita 3: B M H J H M F 
 
 B J B B 
 
 S B H J 
 
U P S 
 M J B B B H U M P T 
J B H H H U T P U 
 
 Fita 4: B B H J M P S T U 
 Fita 5: E F H H J M M N S 
 Fita 6: B F F M N Q Y 
 
 
 Fita 1: B B B B E F F F H H H J J M M M M N N P Q S T U Y 
 Fita 2: 
 Fita 3: 
 Fita 4: B M J B B H T U P 
 Fita 5: E F H H J M M N S 
 Fita 6: B F F M N Q Y