Atividade 3 tecnicas de armazenamento

Prévia do material em texto

Atividade 3 - Pesquisa, Ordenação e Técnicas de armazenamento.
Nome: Matheus Silva Vasconcelos
RA: 2019104047
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 vez que passa sobre o arquivo, as informações são quebradas em blocos do tamanho 
da memória interna disponível, após isso cada sub-bloco é ordenado na memória interna, os blocos ordenados 
são intercalados através de várias passadas sobre o arquivo e a cada passada, blocos ordenados cada vez 
maiores são criados. Para o bom desempenho, é fundamental a redução do número de passadas sobre o 
arquivo.
IMPLEMENTAÇÃO POR MEIO DE SELEÇÃO POR SUBSTITUIÇÃO: A 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 
pode ser utilizada na primeira passada sobre arquivo para quebrar em blocos e na intercalação. Na primeira 
passada, pega a menor chave na memória (utilizando heap), lê o próximo item do arquivo, verifica se o próximo 
item é menor que o item que está saindo, caso seja menor, marca o item para o próximo bloco, este item 
estando marcado, ele vai para o topo da fila de prioridades, o bloco corrente é encerrado e um novo bloco 
ordenado é iniciado. Ao final, vários blocos ordenados são obtidos.
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.
Considerando a memória interna com capacidade de armazenamento para três registros:
FITA 1: BTP EMN YBF
FITA 2: JSU SFH QMN
FITA 3: BMH JHM F
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