Classificação E Pesquisa

Relatório 1 – Pesquisa de Dados.

Conforme descrito no ATPS realizamos os testes, buscando 2 números de um conjunto de dados entre 100 a 100000. As tabelas a seguir mostraram os resultados dos testes feitos com busca linear, busca linear com sentinela e busca binária. A tabela 1 mostra o resultado da busca linear.

Tabela 1: Busca linear.

N 1º número Tempo Teste 2º número Tempo Teste

100 52 0.0048 101 100001 0.0048 101

1000 52 0.4138 1001 100001 0.4138 1001

10000 52 Estourou Estourou 100001 Estourou Estourou

100000 52 Estourou Estourou 100001 Estourou Estourou

Código de busca linear Imagem 1.

Funciona da seguinte forma: a partir do primeiro registro, pesquise sequencialmente até encontrar o número procurado, quando achar, pare. A função retorna o índice do registro que contém o número que procurávamos. Caso não encontre o valor retornado é 0. Os dados que serão analisados não precisam passar por nenhum tipo de preparo antes da execução do algoritmo, tornando seu uso extremamente simples e confiável.

Na tabela 2 mostra os resultados da busca linear com sentinela.

Tabela 2: Busca linear com sentinela.

N 1º número Tempo Teste 2º número Tempo Teste

100 52 0.0008 101 100001 0.0008 101

1000 52 0.0011 49950 100001 0.0001 1001

10000 52 0.3680 Estourou 100001 0.0336 Estourou

100000 52 Estouro Estourou 100001 Estourou Estourou

Código de busca linear com sentinela imagem 2.

Funciona da seguinte forma: introduz-se o número procurado no final da estrutura de dados, os outros números continuam aleatórios. Isso garante que a pesquisa termine. Após a chamada função se o índice for 0 significa que não foi encontrado o valor. O uso da sentinela tem como objetivo acelerar a busca, através da simplificação da expressão booleana, ou seja, a sentinela proporciona à oportunidade de polpa a execução de um condicional.

A tabela 3 mostra o resultado da busca linear com ordenação de seleção.

Tabela 3: Busca linear e ordenação de seleção.

N 1º número Tempo Teste 2º número Tempo Teste

100 52 0.0023 4950 100001 0.0032 2469

1000 52 0.0111 4995 100001 0.0632 1001

10000 52 Estourou Estourou 100001 Estourou Estourou

100000 52 Estourou Estourou 100001 Estourou Estourou

Funciona da seguinte forma: Em cada fase, selecionar um menor item ainda não ordenado e permutá-lo com aquele que ocupa a sua posição na sequência ordenada. Após a ordenação inicia a busca.

A tabela 4 mostra o resultado da busca linear com ordenação de seleção.

Tabela 4: Busca linear com sentinela e ordenação de seleção.

N 1º número Tempo Teste 2º número Tempo Teste

100 52 0.0023 4950 100001 0.0023 101

1000 52 0.0042 4995 100001 0.0042 1001

10000 52 Estourou Estourou 100001 Estourou Estourou

100000 52 Estourou Estourou 100001 Estourou Estourou