🚨 Ordenação de Arquivos Grandes de Registros

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 do Professor

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).

🔴 Como utilizar

# 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

🔍 Explicação dos Argumentos

Argumento	Descrição
quantidadeDeRegistros	É a quantidade de registros que serão criados pelo gerador de arquivo desordenado
maximoDeMemoriaDisponivel	Quantidade máxima de memória RAM em bytes disponível para o algoritmo utilizar durante a ordenação
porçãoMemoriaBufferSaida	Divisor que será utilizado para obter a quantidade máxima de bytes do buffer de saída

📸 Exemplo

#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.

📈 Visualize o relatório sobre o funcionamento do algoritmo

🎓 Autores

Jhonatan Cunha

Jessé Pires

📝 Licença

MIT