Métodos de intercalação externa

Prévia do material em texto

Métodos de intercalação externa 
Os métodos de intercalação externa são utilizados para ordenar arquivos que não podem ser 
mantidos completamente na memória principal de um computador. Dois métodos comuns são o de 
intercalação balanceada e o de intercalação polifásica. 
No método de intercalação balanceada, os registros são divididos em blocos e intercalados em fases 
sucessivas até que o arquivo esteja completamente ordenado. Esse método é adequado para 
arquivos de tamanho grande e é eficiente na utilização de memória. 
Já o método de intercalação polifásica é uma variação do método de intercalação balanceada em 
que os blocos são divididos em fases sucessivas e os registros são ordenados em grupos menores. 
Esse método é mais adequado para arquivos de tamanho médio e oferece um equilíbrio entre 
eficiência e utilização de memória. 
 
Escolha dos métodos 
Para o exemplo dado, o método de intercalação externa de vários caminhos é o mais adequado, pois 
utiliza diversas fitas magnéticas para dividir e ordenar os registros, permitindo uma eficiência maior 
do que os outros métodos de intercalação. 
 
Conceitos e diferenças 
O método de intercalação externa de vários caminhos é um método de ordenação externa que 
utiliza várias fitas magnéticas para dividir e ordenar os registros. Ele é adequado para arquivos 
grandes e pode ser executado em paralelo, permitindo uma maior eficiência. 
A principal diferença desse método em relação aos outros métodos de intercalação externa é o uso 
de múltiplas fitas magnéticas, o que permite a divisão e ordenação simultânea dos registros. Além 
disso, ele pode ser executado em paralelo, o que aumenta ainda mais a eficiência. 
 
Exemplo de aplicação 
Para ordenar a 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) com o método de 
intercalação externa de vários caminhos e uma memória interna com capacidade de três registros e 
seis unidades de fita magnética disponível, o processo seria o seguinte: 
 
1. Dividir o arquivo em seis blocos iguais, cada um contendo quatro registros. Os registros de 
cada bloco são ordenados internamente. 
2. Os registros dos blocos são intercalados em pares, formando três novos blocos de oito 
registros cada. Cada bloco é ordenado internamente. 
3. Os registros dos blocos de oito registros são intercalados em trios, formando dois novos 
blocos de 12 registros cada. Cada bloco é ordenado internamente. 
4. Os registros dos blocos de 12 registros são intercalados em quartetos, formando um novo 
bloco de 24 registros. Esse bloco é ordenado internamente. 
5. O bloco de 24 registros é dividido em dois blocos de 12 registros e intercalado internamente. 
6. O bloco resultante é dividido em três blocos de oito registros e intercalado internamente. 
7. O resultado é um único bloco