GRA0251 Atividade A3

Prévia do material em texto

GRA0251 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO
Atividade A3
Parte 1
Intercalação Balanceada de Vários Caminhos
É um tipo de intercalação que forma séries com valores iguais de elementos. A primeira etapa é a quebra do arquivo em blocos menores, do tamanho da memória interna disponível; então, cada bloco é ordenado e escrito em fitas de saída. A segunda etapa é a intercalação dos blocos ordenados, formando blocos ordenados cada vez maiores até a formação de um bloco único e totalmente ordenado.
Essa forma de ordenação pode não ser a mais eficiente, dada a quantidade de vezes que o algoritmo de busca interna é acessado pela busca da menor dentre as chaves de cada bloco. 
Intercalação Polifásica
É um tipo de intercalação que distribui as séries iniciais de forma otimizada, com vistas a que classificação total seja alcançada com menos passos.
Nesse método, os blocos são distribuídos de forma desequilibrada entre as fitas disponíveis. Uma fita é deixada de forma livre e, logo após, a intercalação de blocos ordenados é realizada até que uma das fitas esvazie. Então, uma das fitas de saída troca de função com a fita de entrada. 
O método de interpolação polifásica, mesmo sendo um método mais complexo de implementar, reduz o tempo de ordenação pois evita fazer movimentações desnecessárias entre os arquivos.
Parte 2
Ordenar a fita com 25 registros – com 3 registros e 6 fitas
Método: ordenação externa de vários caminhos
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
Etapa 1
Separar as 6 fitas em 2 grupos de 3, para permitir a mobilidade dos dados.
Os blocos separados em 3 ficam:
Fita 1	B P T - E M N - B F Y
Fita 2	J U S - F H S - M N Q
Fita 3	B H M - H J M – F
Etapa 2
Intercalação ordenada
Formação de blocos de 9
Fita 4	B B J H M P U S T
Fita 5	E F H H J M M N S
Fita 6	B F F M N Q Y
Etapa 3
Intercalação dos três arquivos ordenados em 1 único
Fita 1	 B B B E F F F H H H J J M M M M N N P Q S S T U Y
Enunciado
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.