PERGUNTA 1

Prévia do material em texto

PERGUNTA 1
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.
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 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 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; 
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 fita 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 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.
	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