Introdução
Este trabalho foi desenvolvido com o mesmo intuito do trabalho I, ou seja, seguimos a mesma idéia de modularização e também manter um código robusto, apesar de o intuito deste trabalho é somente estudarmos a eficiência de algoritmos de ordenação e busca. A dupla decidiu que é uma boa prática de programação sempre desenvolvermos códigos robustos. A interface com o usuário ficou divido: centralizado título e um menu a esquerda com 8 espaços de margem. Assim que o programa é iniciado um vetor com 512 elementos é gerado aleatóriamente, desordenado e podendo haver elementos repetidos. Há um segundo vetor que armazena o vetor ordenado, porém ao iniciar o programa contem lixo de memória, uma vez ordenado estará na memória o vetor original gerado aleatórimente e uma cópia ordenado. Por convenção da dupla, o índice zero do vetor foi reservado para a busca sequencial com sentinela, portanto elementos válidos estão entre 1 e 512 em ambos os vetores. A impressão do vetor tanto no terminal quanto no log foi feita na forma de matriz linha e coluna, elas estão numeradas, assim a intentificação de um elemento fica mais simples, compacta e limpa.
MODULARIZAÇÃO
OBS: Quick sort será implementado de forma eficiente ao retorno das aulas, apesar disso este já esta funcional, apenas com o pivô ineficiente. Passe para o make CFLAGS=INCLUDE_QUICK_SORT, assim o módulo com o quick sort será incluso. O programa deve ser linkado com curses, pois utilizamos algumas chamadas para cetralizar menu e greeting da interface com o usuário.
CÁCULO DO DESVIO PADRÃO
Devido o cálculo da variância necessitar da média das comparações (V = (somatório (Xi - MÉDIA)²) / N fórmula do cálculo da variância. N=nº de elementos) salvamos em um vetor todos os números de comparações e então de cada iésimo elemento do vetor subtraímos da média e elevamos ao quadrado. Os mil casos que foram analizados foram gerados aleatótiamente, tanto o vetor quanto elementos a serem pesquisados. Somente utilizamos a técnica do acumulador para cálculo da média dos mil casos. Não é possível acumular o quadrado da diferença entre Xi - MÉDIA, pois não temos de antemão MÉDIA, logo precisamos calcular a média dos 1000 casos e então podemos calcular a variância e consequentemente desvio padrão, DP = sqrt(V). Por isso cada número de comparações foi armazenado em um vetor.
LOG's
CONCLUSÃO
Concluímos deste trabalho que sem sobra de dúvida a busca binária é muito superior que a busca a sequencial, porém com o custo da ordenação, pois a busca binária demanda o vetor estar ordenado em ordem crescente ou decrescente. A conclusão matemática pode ser obeservada através do desvio padrão 99.999...% dos casos a busca binária se manteve mais regular, enquanto a busca sequencial é muito irregular. O algoritmo de ordenação selectsort é 100% regular, porém ineficiente (como podemos observar seu desvio padrão), pois não importa quanto próximo ordenado está o vetor no início da ordenação o selectsort sempre fará N(N-1) / 2 comparações, em nosso caso N = 512, portanto 512*(512-1) / 2 = 130816 comparações, sempre. O que o torna um método de ordenação nada eficiente. Aquardaremos a comparação com o quicksort, que é um método muito mais eficiente.
O quick sort foi implementado, porém estudamos (referência bibliogáfica Programer's Bible Jamsa's) que escolhendo o pivo no meio do vetor e com um pouco de sorte ele se torna um bom pivo, potencializando o desempenho. Pudemos observar que o quick sort e bem irregular segundo a métrica permutações. Ja o select sort após correção do bug ele se mostrou 100% regular, conforme prova matematica ele faz N-1 permutações, porém o quick sort com um bom pivo tem melhor desempenho.
