Com o objetivo de ordenar arquivos com grande quantidade de bytes utilizando uma quantidade limitada de memoria principal, utilizamos a técnica de particionamento. Onde cada partição é ordenada pelo algoritmo de quicksort e terá um buffer de entrada auxiliar, iremos então utilizar intercalação por k-vias para preencher o buffer de saída.

Feedback atribuído em nosso trabalho pelo Professor Doutor Juliano Henrique Foleis que ministra a matéria de Algoritmos e Estruturas de Dados 2 na Universidade Tecnologia Federal do Paraná (UTFPR/CM).

# Clone este repositório
$ git clone https://github.com/jhonatancunha/ed2_k-way_merge

# Acesse a pasta do projeto no terminal/cmd
$ cd ed2_k-way_merge

# Execute o makefile (windows)
$ mingw32-make

# Execute o makefile (linux)
$ make

# Por fim inicie o executavel
#Windows
$ main quantidadeDeRegistros maximoDeMemoriaDisponivel porçãoMemoriaBufferSaida
#Linux
$ ./main quantidadeDeRegistros maximoDeMemoriaDisponivel porçãoMemoriaBufferSaida

#Executei passando os seguintes argumentos
#Windows
$ main 256000 8388608 2
#Linux
$ ./main 256000 8388608 2

• Recebemos 256000 em argv[1], então teremos um arquivo com 250 MB's
• Recebemos 8388608 em argv[2], então teremos um limite máximo de memoria disponivel de 8 MB'.
• Dividimos o mesmo em 32 vezes, então cada uma terá 7.81 MB's
• Antes de salvar cada partição, ordenamos a mesma utilizando o algoritmo de QuickSort
• Recebemos 2 em argv[3], então eremos um buffer de saída com 4 MB's, ou seja, 8/2
• Teremos 32 buffers de entrada cada um com 0,125 MB's
• Criamos e preenchemos os buffers de entrada, reenchemos o mesmo caso necessario
• Utilizamos o algoritmo de intercalação em k-vias para preencher o buffer de saida, quando o mesmo estiver cheio, realizamos um dump no arquivo saida.dat
• Por fim quando todos os buffers estiverem vazios teremos um arquivo saida.dat, onde todos nossos dados estarão ordenados.

Obtemos as seguintes informações como saida do algoritmo.

Jhonatan Cunha

Jessé Pires

MIT