AV3 - PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO

Prévia do material em texto

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.
1. Intercalação balanceada de vários caminhos (IBVC): Este método consiste em dividir o arquivo em blocos que cabem na memória interna, ordenar esses blocos e intercalá-los usando várias fitas de saída em um processo recursivo. A ideia é balancear a intercalação, isto é, tentar manter o número de blocos intercalados em cada passo. A vantagem desse método é que ele usa todas as fitas disponíveis e é eficiente mesmo quando há muitos blocos. A desvantagem é que ele pode ser um pouco mais complexo de implementar do que outros métodos.
2. Intercalação polifásica: Este método é semelhante ao IBVC, mas usa apenas duas fitas de saída em um processo iterativo. Ele também divide o arquivo em blocos que cabem na memória interna e intercala-os para formar blocos maiores. A principal diferença é que ele usa uma estratégia de "distribuição" dos blocos nas fitas, de modo que um bloco não seja intercalado com outro que esteja muito longe na ordem. Isso é feito por meio de uma sequência de passos chamada "fase", em que os blocos são distribuídos e depois intercalados em um padrão específico.
Considerando o arquivo fornecido e o método de ordenação externa de vários caminhos com uma memória interna de três registros e seis fitas disponíveis, podemos seguir os seguintes passos:
1. Dividir o arquivo original em blocos que caibam na memória interna (no caso, blocos de três registros) e classificá-los.
(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)
2. Usando a intercalação balanceada de vários caminhos, intercalar esses blocos para criar blocos maiores. Nesse método, é necessário fazer passagens pelos blocos intercalados várias vezes até que todo o arquivo esteja ordenado.
· Fase 0: distribuir os blocos nas fitas
Fita 0: (B, S, M, F, F, J, N)
Fita 1: (T, U, H, Y, Q)
Fita 2: (P, J, B, N, M)
Fita 3: (S, E, F, M, H)
Fita 4: (H, B)
Fita 5: (J, M)
· Fase 1: intercalar os blocos nas fitas
Fita 0: (B, S, T, U, M, H, F, Y, F, J, N, Q)
Fita 1: (P, J, E, B, S, M, F, M, H, N, J)
· Fase 2: intercalar os blocos nas fitas
Fita 0: (B, P, S, J, T, J, U, E, M, B, H, F, F, S, M)