Atividade 3 pesquisa e armazenamento

Prévia do material em texto

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 interna disponí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 primeiro 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 é encerrado e o novo bloco ordenado é iniciado. 
· Ao final, 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 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 vinte e cinco 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íveis. 
	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