ATIVIDADE 3 - PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO

Prévia do material em texto

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
	
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 YB 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
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