Decidimos organizar o código em vários arquivos para facilitar a leitura e separá-lo de acordo com o objetivo de cada implementação. O resultado final consiste em dois arquivos (um .c e um .h) que contêm toda a lógica do programa principal, dois arquivos (um .c e um .h) que contêm vários algoritmos vistos nas aulas de Algoritmos e Estruturas de Dados II que são usados e testados no programa principal. Também percebemos que não seria interessante incluir as bibliotecas padrões em todos os headers, portanto criamos um arquivo utils.h para definir constantes - até mesmo o tipo bool, true e false - e incluir bibliotecas que são usadas ao longo do código inteiro. Fizemos também um par de arquivos apenas para definir o log e suas ações, pois elas são bastante chamadas no programa principal, além de outro par de arquivos que servem como biblioteca para a manipulação do tempo no programa. Tivemos cuidado na hora de comentar o código e nomear as variáveis e funções, para facilitar tanto na correção do trabalho quanto nos momentos que foi necessário reler o que já foi feito.

O arquivo algoritmos tem dois algoritmos de busca e quatro de ordenação. O primeiro é a pesquisa binária, optamos pela implementação recursiva pois essa é mais fácil de ser feita e mais intuitiva. O segundo é a pesquisa sequencial, que é terminada assim que o elemento fornecido é encontrado. Ambos recebem um inteiro e retornam a posição encontrada no vetor fornecido, se o elemento não estiver no vetor, o número -1 é retornado. Entre os algoritmos de ordenação, o primeiro é o SelectSort, que recebe um vetor e seu tamanho e o ordena usando o método de seleção. O segundo é o BubbleSort, que também recebe um vetor e seu tamanho, mas o ordena usando o método da bolha. O terceiro é o QuickSort Recursivo, que recebe um vetor, mas ao contrário dos outros dois, recebe a posição da esquerda e da direita, podendo assim executar a mesma função na chamada recursiva para outras partes do vetor. O quarto é o QuickSort Iterativo, cujo funcionamento é parecido com o QuickSort Recursivo, a única diferença é a pilha que nesse caso é explícita ao contrário do recursivo que é implícita, portanto não há nenhuma chamada recursiva.

A implementação da pilha está como alocação dinâmica, pois assim não foi necessário refazê-la, bastou usar a pilha já implementada no trabalho anterior. O nodo da pilha armazena dois inteiros, um indica a posição da esquerda e o outro a posição da direita, dessa forma é possível simular a recursão usada no QuickSort Recursivo. A implementação desse tipo abstrato de dados conta apenas com as operações vaziaPilha, iniciaPilha, Push e Pop, que são as funções necessárias para o QuickSort Iterativo. O algoritmo Iterativo repete o processo de ordenação até que a pilha esteja vazia.

O algoritmo de partição foi utilizado tanto no Quicksort Recursivo quando no Iterativo. Ele foi implementado em uma função que recebe um vetor, a posição da esquerda e da direita e retorna a posição do pivô que será utilizada nos Quicksorts. Para escolha do pivô foi calculada a mediana da esquerda, da direita e do meio usando a seguinte função:

mediana(a,b,c) = a XOR b XOR c XOR max(a,b,c) XOR min(a,b,c)

Logo depois o pivô é trocado com o elemento na direita e a partição é iniciada pela esquerda, percorrendo o vetor e inserindo os elementos menores que o pivô no começo, no final ele é colocado logo após o último "menor elemento inserido".

Para medir o tempo, usamos uma função que retorna o tempo do sistema em nanosegundos, com essa precisão foi possível medir a duração dos algoritmos de busca em vetores pequenos. Analisando os tempos de cada algoritmo de ordenação, concluimos que os dois QuickSorts são muito mais rápidos que os outros dois. Também observamos que o QuickSort Recursivo é um pouco mais eficiênte que o Iterativo, acreditamos que isso ocorre devido à implementação da pilha, que no caso do recursivo é implícita e o seu comportamento é feito em baixo nível pelo compilador, já o iterativo requer as operações da pilha em alto nível, que possui alocações dinâmicas. Nos testes que fizemos, obtivemos, para as ordenações, os seguites resultados:

Computador Pessoal (vetor de 1000 elementos):

SelectSort ordenou 10000 vetores em 16921758391ns (16.922s)
BubbleSort ordenou 10000 vetores em 17146174748ns (17.146s)
QuickSort Recursivo ordenou 10000 vetores em 586669352ns (0.587s)
QuickSort Iterativo ordenou 10000 vetores em 987042884ns (0.987s)

Servidores do Dinf (vetor de 1000 elementos):

SelectSort ordenou 10000 vetores em 34327237347ns (34.327s)
BubbleSort ordenou 10000 vetores em 46694420492ns (46.694s)
QuickSort Recursivo ordenou 10000 vetores em 1195200592ns (1.195s)
QuickSort Iterativo ordenou 10000 vetores em 1962472229ns (1.962s)

Computador Pessoal (vetor de 9999 elementos):

SelectSort ordenou 10000 vetores em 1718952929554ns (1718.953s)
BubbleSort ordenou 10000 vetores em 1767187863506ns (1767.188s)
QuickSort Recursivo ordenou 10000 vetores em 11593082036ns (11.593s)
QuickSort Iterativo ordenou 10000 vetores em 15668917989ns (15.669s)

Todo o programa é iniciado no arquivo main e para a compilação, em vez de usarmos um makefile, optamos por um shell script simples. No começo do programa o usuário insere o tamanho do vetor, e o valor máximo, depois aparece um menu com as opções de imprimir o vetor, jogar, redefinir o vetor e testar os tempos dos algoritmos de ordenação. Decidimos que o conteúdo do log seria diferente do que aparece para o usuário, tornando aquele um arquivo "interno" que só é disponível no final da execução do programa. O texto do log expressa com clareza as ações feitas pelo usuário durante a execução do programa. Os logs e os históricos do usuário correspondentes estão na página do trabalho na seção "logs".