Relatório do trabalho de Algoritmos II.
Disciplina do 2o Período dos Bacharelados: BCC, IBM e MI
Prof. Elias P. Duarte Jr. Departamento de Informática UFPR
Alunos: Bruno Henrique Meyer e Gustavo Shoiti Shiomi.



Inicialmente foi decidido quais variáveis principais usaríamos no main. Após isso, foi implementada as funções de preencher aleatoriamente o vetor e de imprimi-lo.

Após isso, achamos mais simples implementar primeiramente a pesquisa sequencial já que é um tipo de pesquisa mais simples de se fazer.

Nesse ponto houve uma pequena confusão dado que começamos a montar a função de pesquisa binária, porém pouco tempo depois percebemos que seria necessário um vetor ordenado para testa-lo, então criamos a função do Select Sort e após isso terminamos a função da pesquisa binária.

Pela sua semelhança com o Select Sort, preferimos depois disso implementar o Bubble Sort.

Chegamos em um momento que decidimos comparar a eficiência dos dois algoritmos de ordenação já implementados, então pesquisamos como descobrir o tempo de execução de cada um. Escolhemos usar a biblioteca time.h e sua variável de ambiente "clock()" que representa o "valor" atual do relógio do computador , sendo que essa variável tem valores diferentes em trechos do código, é possível descobrir quantos segundos demoraram entre uma atividade e outra.

Então, começamos a implementar o Quick Sort Recursivo, porém, antes da sua implementação criamos duas funções que seriam útil tanto na implementação recursiva quanto na iterativa: medianaNoVetor que nos dizia a mediana entre três elemento de um vetor(usada para calcular o pivô) e a função particao, que são usadas tanto na implementação recursiva quanto na iterativa do QuickSort.

Após terminar o Quick Sort Recursivo, fizemos a consistência dos números do "bilhete" para conferir se estavam na faixa adequada, e depois implementamos o Quick Sort Iterativo. O Quick Sort Iterativo foi implementado usando duas pilhas que tinham em cada índice em comum, um par de elementos que representava um sub-vetor que deveria ser "particionado" e após isso, gerava 2, 1 ou nenhum sub-vetor adicionais nas pilhas, num ciclo que duraria até a pilha acabar.

Por fim, modularizamos o programa em arquivos diferentes e modificamos o código para que fosse possível jogar quantas vezes o usuário desejasse.

No final, também, modificamos o método de temporização que estava sendo feito usando segundos em forma de inteiro, e usamos um float para representar melhor o tempo de execução dado a pequena diferença entre alguns tipos de ordenação em alguns casos.

Como conclusão, observamos que há uma grande diferença entre o Bubble Sort, Select Sort e Quick Sort, sendo respectivamente nessa ordem do mais "lento" ao mais "rápido" na grande maioria dos casos. Também verificamos que há uma diferença entre o Quick Sort Iterativo e o Recursivo, já que o Iterativo é mais rápido. Outro detalhe que ficou bem visível durante a montagem do código, foi a necessidade do vetor estar ordenado antes de usar a pesquisa binária, o que não acontece na pesquisa sequencial.

Obs: Durante alguns testes, verificamos que o Quick Sort Iterativo era em alguns casos, mais "lento" que sua versão Recursiva, porém foi achado um "bug" na função da versão Iterativa que fazia uma comparação a mais em alguns casos, o que deixou muito implícito o quanto pode custar um comando a mais dentro de um laço que é percorrido muitas vezes.