Atps
Ensaios: Atps. Pesquise 862.000+ trabalhos acadêmicosPor: miguel.elias • 2/12/2012 • 3.114 Palavras (13 Páginas) • 760 Visualizações
ATPS Classificação e Pesquisa
Etapa 1
Passo 1
Considerando os parâmetros de testes definidos no ATPS, foi possível identificar que o melhor método de busca sem a ordenação dos dados é o linear com sentinela, porém se o valor procurado não estiver no vetor, o tempo e a quantidade de testes realizados serão exatamente iguais ao da busca linear, pois a chave será localizada apenas no final da base de dados.
O calculo de tempo foi realizado através da quantidade de ciclos do processador (clock), mas como a base utilizada nos testes é pequena o processo é muito rápido para realizar uma comparação precisa entre os algoritmos, além disso, foi possível notar que os valores definidos para busca no ATPS não estão disponíveis após a geração dos números aleatórios e dessa forma os algoritmos de busca não localizarão os valores o que forçara percorrer o vetor até o final.
Passo 2
Desempenhos da busca binária x busca linear x busca linear com sentinela.
Após a ordenação dos dados fica claro que o melhor método de busca é a binária como mostra a Figura 1, pois tanto o tempo quanto a quantidade de processamento é muito menor do que as outras técnicas de busca.
O principal ponto é se a ordenação da base de dados é viável para aplicar esse tipo de técnica, pois dependendo do tamanho da base a ordenação pode se tornar muito lenta e exigir muito processamento.
A ordenação através de algoritmos como bubblesort e seleção demonstraram bons resultados, mas ainda assim exigem mais processamento do que as buscas em bases que não foram ordenadas, porem se a ordenação for realizada periodicamente ou no momento em que os dados são inseridos a busca binária torna-se viável, pois a localização e o tempo de processamento são muito mais rápidos do que as demais técnicas.
|Tipo de teste |Tamanho Vetor |Quantidade de testes |
|Busca Linear |1.000 |1.000 |
|Busca Linear com Sentinela |1.000 |1.000 |
|Busca Binária |1.000 |9 |
|Bubble Sort |1.000 |244.968 |
|Seleção |1.000 |56.738 |
Figura 1 – Resultados dos testes realizados com os algoritmos de busca após a ordenação da base
Passo 3
Após a realização das baterias de testes foi possível concluir que existem algoritmos de localização e ordenação mais eficientes do que outros, porém a aplicação e a utilização de cada um depende da situação e principalmente do tamanho da base de dados que será manipulada.
Considerando os parâmetros utilizados nesses testes observamos que o melhor comportamento dos algoritmos de ordenação e seleção foram obtidos pelo método seleção e a busca binária, mas isso não significa que são os melhores para todas as situações, pois todos possuem suas particularidades e deficiências.
Anexo I
Código completo para realizar a bateria de testes descritas abaixo.
/* ATPS - Classificação e Pesquisa
Description: Bateria de testes de busca linear, linear com sentinela e binária
ordenação bubble sort e seleção
*/
main()
{
long int seed;
int low, high, retorno1, tabela1[N], numero_procurado1, op;
double low2, high2, retorno2, tabela2[N], numero_procurado2;
seed = 1234554321;
while(op != 3){
system("cls");
printf("Desafio - Busca Sequencial\n");
printf("Digite 1 para manipular inteiros\n");
printf("Digite 2 para manupular double\n");
printf("Digite 3 para sair\n");
printf("Entre com a opcao desejada: ");
scanf("%i",&op);
switch(op)
{
case 1:
for(int i=0; i<= N; i++)
{
retorno1 = inteiros_unif(&seed, 0, 100000);
tabela1[N] = retorno1;
printf("\nRetorno: %i",tabela1[N]);
}
printf("\nDigite o inteiro a ser procurado: ");
scanf("%i",&numero_procurado1);
if(buscaSequencialInt(numero_procurado1, tabela1))
{
printf("\nO argumento %i existe\n", numero_procurado1);
}
else
{
printf("\nO argumento %i NAO existe\n", numero_procurado1);
}
system("pause");
break;
case 2:
for(int i=0; i<= N; i++)
{
...