ATPS Classificação E Pesquisa

Faculdade Santa Terezinha – Anhanguera

ATPS Classificação e Pesquisa Etapa 1 e 2

Professor: Marcelo Aguiar

Componentes:

Ariel Pereira Souza – RA 2505004039

Alex Francisco Soares – RA 2547453866

Rafael Bomfim – RA 2504071494

Israel Dillas Soares – RA 11553598887

Francisco Wanderson – RA 1191425998

- Método de busca com o melhor desempenho.

O melhor método de busca sem ordenação de dados será o linear com sentinela, mas se o valor procurado não se encontrar no vetor, a quantidade de testes será igual ao da busca linear.

O testes realizados pode variar de equipamento para equipamento, pois o cálculo o tempo é realizado através do “clock” do processador.

- Desempenho da busca binária x busca linear x busca linear com sentinela

Caso os dados sejam ordenados, o melhor método de busca será a busca binaria, veja na figura 1, neste caso o tempo e o processamento será menor que as demais.

É preciso analisar se é possível a ordenação da base de dados, pois se a base de ordenação for muito grande a ordenação se tornará lenta e pesada.

A bubblesort e seleção apresentaram resultados satisfatórios, mas exigem mais processamento do que a busca em bases não ordenadas.

Tip. de Teste Tam. do Vetor Quant. de Testes

Busca linear 1.000 1.000

Busca Linear com Sentinela 1.000 1.000

Busca Binária 1.000 9

Bubblesort 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

Conclusão

Depois de realizados vários testes, podemos concluir que existem diversos métodos eficientes de classificação e pesquisa, sendo que para cada ocasião um se sobressai sobre os outros.

Algoritmos removido do ATPS – Classificação e Pesquisa – Etapa 1

Anexo I

Código completo para realizar a bateria de testes descritas abaixo.

/*

Name: 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

*/

#include

#include

#include

#include

#define tempo 2000

#define search_p 87

#define search_s 100001

//prototipos das funções

void bateria_testes(int tam, int t);

void linear(int n, int t, int *p_int, double *p);

void linear_sentinela(int n, int t, int *p_int, double *p);

void binaria(int n, int t, int *p_int, double *p);

void bubblesort(int n, int t, int *p_int, double *p);

void selecao(int n, int t, int *p_int, double *p);

double unif(long int *seed, double low, double high);

int inteiros_unif(long int *seed, int low, int high);

main(){

//declaração de variaveis

int op=0, tipo;

while (op!=5){

system("cls");

//cabeçalho com os parametros de teste

printf("\n ATPS - Classifica%c%co e Pesquisa \n",135,198);

printf(" \n +------+--------+-----+--------+------------+----------+-------------+");

printf(" \n | OP | N | low | high | seed | N. Proc. | S. N. Proc. |");

printf(" \n +------+--------+-----+--------+------------+----------+-------------+");

printf(" \n | 01 | 100 | 0 | 100000 | 1234554321 | 87 | 100001 |");

printf(" \n +------+--------+-----+--------+------------+----------+-------------+");

printf(" \n | 02 | 1000 | 0 | 100000 | 1234554321 | 87 | 100001 |");

printf(" \n +------+--------+-----+--------+------------+----------+-------------+");

printf(" \n | 03 | 10000 | 0 | 100000 | 1234554321 | 87 | 100001 |");

printf(" \n +------+--------+-----+--------+------------+----------+-------------+");

printf(" \n | 04 | 100000 | 0 | 100000 | 1234554321 | 87 | 100001 |");

printf(" \n +------+--------+-----+--------+------------+----------+-------------+");

printf("\n\n Selecione os par%cmetros de teste [ 1 - 4 ]: ",131);

scanf("%d",&op);

if(op5){

printf("\n Opcao invalida !");

getch();

}

break;

}

}

}

/*------------------------------------------------------------------------------

Algoritmo 1 – Gerador de números reais aleatórios

Gerador de distribuicao uniforme retorna um numero

double (real com longa precisão) na faixa low – high,ou seja, [low,high].

------------------------------------------------------------------------------*/

double unif(long int *seed, double low, double high){

double unif_ret;

long int m,a,b,c, k;

double value_0_1;

m = 2147483647;

a = 16807;

b = 127773;

c = 2836;

k = *seed/b;

*seed = a * (*seed % b) - k*c;

if (*seed

Etapa 2 –

Instancia Low High Seed

1 408 96807 640993899

2 490 709992 383429253

3 218 67508 416520389

TIPO Dados Aleatórios

Instância Média entre instâncias 1, 2, e 3 Média entre instâncias 1, 2, e 3 Média entre instâncias 1, 2, e 3

Dados 500 5.000 50.000

Algoritmo N. Comp. N. Trocas Tempo N. Comp N. Trocas Tempo N. Comp. N. Trocas Tempo

QuickSort 6861 754 0,0010004 104532 11035 0,0156142 1212545 150884 0,0156261

Binária 3801 65708 0,0009967 54538 6288012 0,0312514 711283 623952428 4,0485333

MergeSort 4844 4214 0,0039895 65319 59066 0,0312514 817897 756515 1,2656510

Passo 4

Relatório 2 – Métodos de Ordenação

Os resultados com o Quick Sort em casos melhores escolhem um elemento mediano da lista para ser o seu pivô, quando não é porque a escolha do pivô não foi adequada.

O Quick Sort no melhor caso sempre escolhe o elemento mediano da sua lista de entrada.

1 melhor caso: O(n log n), * pior caso: O(n2), 2 caso médio: O(n log n), 3 Não é estável

Outro que em sua melhor utilização é similar ao quicksort é o Mergesort.

Seja qual for o caso a ordem será n log n. Isso acontece porque em todas as situações onde se encontra o vetor, ele irá realizar a divisão e o intercalação.

1 melhor caso: O(n log n)

2 pior caso: O(n log n)

3 caso médio: O(n log n)

4 Estável (Implementado corretamente)

O algoritmo de inserção linear faz uma busca linear para encontrar a posição para fazer a inserção. No entanto, uma vez que o elemento é inserido numa sequência que já está ordenada, o ideal é usar uma pesquisa binária, em vez de uma busca linear. Considerando que uma busca linear requer O(n) comparações no pior caso, uma busca binária requer apenas O(log n) comparações.

1 melhor caso: O(n log n)

2 pior caso: O(n2)

3 caso médio: O(n2)

4 Estável