UAM - Pesquisa, ordenação e técnicas de armazenamento - Unidade 3 - Atividade 2

Prévia do material em texto

UAM – Pesquisa, ordenação e técnicas de armazenamento – Unidade 3 – Atividade 2
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.



 
 
!
"# " 
$#%&'#( 
%)#* %
#!(# # 
%&+#* %
#!( # 
%, #* %
#!(- # 
%.* %
#!(% # 
#!#/0-#1
 !
 
RESPOSTA
1. Intercalação Balanceada de Vários Caminhos
A intercalação balanceada de vários caminhos é um método de ordenação externa que utiliza várias fitas para intercalar os registros ordenados. Este método divide o arquivo original em blocos menores que caibam na memória interna, ordena esses blocos e os grava em várias fitas. Na fase de intercalação, são utilizadas várias fitas para ler os blocos ordenados e escrever a saída em uma fita de destino. Esse processo é repetido até que todos os registros estejam intercalados em uma única fita.
Características:
· Utiliza várias fitas para distribuir a leitura e a escrita dos blocos ordenados.
· Reduz o número de passagens pelo arquivo ao intercalar vários blocos simultaneamente.
· Eficiência de E/S melhorada devido à leitura e escrita em paralelo nas fitas.
2. Intercalação Polifásica
A intercalação polifásica é outro método de ordenação externa que também utiliza várias fitas, mas de uma maneira diferente. Neste método, o número de fitas utilizadas é igual ao número de fases mais uma. A fase inicial consiste em dividir o arquivo em blocos menores, ordená-los e distribuí-los pelas fitas. Na fase de intercalação, uma fita é deixada vazia, e as outras fitas são usadas para intercalar os blocos, alternando a fita de saída em cada fase até que todos os blocos estejam ordenados em uma única fita.
Características:
· Menor número de fases comparado à intercalação balanceada de vários caminhos.
· Maior complexidade na gestão das fitas devido à alternância constante da fita de saída.
· Potencialmente mais eficiente em termos de E/S, pois minimiza a quantidade de gravações intermediárias.
Comparação
· Intercalação Balanceada de Vários Caminhos: Melhor para situações onde a leitura e escrita simultâneas podem ser realizadas em várias fitas, distribuindo a carga de E/S.
· Intercalação Polifásica: Mais eficiente em termos de número de fases e potencialmente em E/S, mas requer uma gestão mais complexa das fitas.
Ordenação do Arquivo Usando Intercalação Balanceada de Vários Caminhos
Dados:
Arquivo 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)
Memória interna: Capacidade de 3 registros
Unidades de fita magnética: 6
Passo a Passo:
1. Divisão em blocos: Dividimos o arquivo em blocos de 3 registros e os ordenamos.
· Bloco 1: (B T P) -> (B P T)
· Bloco 2: (S U J) -> (J S U)
· Bloco 3: (M H B) -> (B H M)
· Bloco 4: (M E N) -> (E M N)
· Bloco 5: (F S H) -> (F H S)
· Bloco 6: (J M H) -> (H J M)
· Bloco 7: (F Y B) -> (B F Y)
· Bloco 8: (N Q M) -> (M N Q)
· Bloco 9: (F) (não completo)
2. Distribuição nas fitas:
· Fita 1: (B P T), (B H M), (B F Y)
· Fita 2: (J S U), (E M N), (M N Q)
· Fita 3: (F H S), (H J M), (F)
3. Intercalação:
Primeira passagem:
· Fita 1 + Fita 2 + Fita 3 -> Fita 4 (Intercalando os primeiros blocos de cada fita)
· Fita 1: (B P T), (B H M)
· Fita 2: (J S U), (E M N)
· Fita 3: (F H S)
· Fita 4: (B B B E F H J M P S T U Y)
Segunda passagem:
· Fita 4 + Fita 1 + Fita 2 -> Fita 5
· Fita 4: (B B B E F H J M P S T U Y)
· Fita 1: (B H M)
· Fita 2: (E M N)
· Fita 5: (B B B E E F H J M M N P S T U Y)
Terceira passagem:
· Fita 5 + Fita 4 -> Fita 6
· Fita 5: (B B B E E F H J M M N P S T U Y)
· Fita 4: (B B B E F H J M P S T U Y)
· Fita 6: (B B B B B B E E E F F H H J J M M M N P S T U U Y Y)
Assim, o arquivo é ordenado em uma única fita, utilizando a intercalação balanceada de vários caminhos.