Tarefa 8: Escola

O último laboratório da disciplina era sobre ordenação externa. Esse é um tópico que é dado na disciplina de estruturas de dados (embora não estivesse na ementa na vez que cursei). O problema é basicamente o seguinte: dado um arquivo muito grande em disco, queremos ordená-lo, sem ter que carregá-lo completamente na memória. A ideia para resolver é subdividir o arquivo em blocos de tamanho fixo e pequenos o suficiente para caberem em memória. Lemos cada bloco de uma vez na memória, ordenamos com um algoritmo de ordenação qualquer e escrevemos de volta no arquivo. Imagine agora que temos vários vetores ordenados e queremos fazer uma intercalação entre eles e gerar um único vetor ordenado. Observe que esta é uma generalização do passo do algoritmo Merge-sort.

No caso básico temos dois vetores ordenados e mantemos apontadores para o começo de cada um deles, Pa e Pb, por exemplo. Sejam a[1] e b[1] os valores dos elementos apontados por tais apontadores. Se a[1] for menor do que b[1], então A deverá vir primeiro no vetor final ordenado. Caso contrário será b[1] (no caso de empate tanto faz). Ou seja, colocamos o menor entre a[1] e b[1] no vetor final. Supondo que a[1] foi colocado, a pergunta que devemos fazer é: qual elemento poderia aparecer depois de a[1] num vetor ordenado? É claro que é b[1] ou a[1], pois estes são os menores elementos maiores do que a[1]. Então andamos com o apontador Pa em 1 posição e repetimos o procedimento.

Como generalizar essa ideia? Suponha agora que temos m vetores, dados em uma matriz a[m][n] e apontadores (P1, …, Pm) para o começo de cada um deles. O primeiro elemento no vetor de saída será o menor entre todos os elementos. Só que como os vetores estão ordenados, sabemos que o menor elemento está na primeira posição de algum dos vetores ou seja, queremos min(a[1][1], a[2][1], ….. a[m][1]). Seja i* o vetor com menor elemento. Colocamos então a[i*][1] na saída. Com argumentação semelhante ao caso base, sabemos que o próximo elemento a aparecer depois de a[i*][1] é min(a[1][1], a[2][1], …, a[i-1][1],a[i][2], a[i+1][1], …, a[m][1]). Que é equivalente a ardamos uma posição com o ponteiro de i*. Achar o menor entre dois elementos é fácil, mas e para n elementos? Bom, para isso podemos utilizar a estrutura de fila de prioridades. Dela conseguimos extrair o menor elemento em O(1) e inserir em O(log n). Assim, extraímos a[i*][Pi*] e inserimos a[i*][Pi*+1].

Qual a complexidade do algoritmo? Seja m o número de blocos e n o tamanho de cada bloco. Para cada bloco devemos realizar uma operação de ordenação sobre O(n) elementos, implicando em uma complexidade de O(m*n*log n). Após isso, temos a etapa de intercalação. Observe que a fila de prioridades nunca tem mais de um elemento por vetor, logo tem tamanho no máximo O(m). Isso é importante porque as complexidades das operações sobre a fila são sobre o número de elementos nela. Logo, a remoção é O(1) e a inserção O(log m). Como todo elemento de cada vetor entra e sai da fila, vamos fazer uma operação de inserção e remoção para cada um dos O(n*m) elementos, resultando na complexidade O(n*m*log m). No total temos O(n*m*(log n + log m)) = O(n*m*log(n*m)). Seja N=n*m o tamanho do arquivo. Então a complexidade desse algoritmo O(N*log N).

Um tira no jardim de infância (velho!)

Para quem leu o enunciado, verá que o problema não está descrito desta forma. Decidi colocar um contexo de treinamento contra incêncios de uma escola. Dá para fazer as seguintes correspondências: a escola representa o arquivo, os alunos representam os elementos do arquivo, as salas correspondem aos blocos em memória e o pátio junto com o diretor representam a fila de prioridades. Minha intenção com isso era tornar o problema mais interessante e quem sabe deixar a ideia por trás do algoritmo mais intuitiva. Não sei se foi devido às provas de fim de semestre ou à dificuldade do problema (ou porque muita gente já tinha passado na parte prática), mas essa foi a tarefa com menor número de submissões.

Os comentários estão fechados.

%d bloggers like this: