ATIVIDADE-03 - Pesquisa, Ordenação e Técnicas de Armazenamento

Prévia do material em texto

ATIVIDADE UNIDADE 03
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
	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 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 é encerrado e o 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 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í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