Programação E Design Para Web

Sistema de informação

CLASSIFICAÇÃO E PESQUISA

Unidade: Facnet

Curso: Sistema de Informação

Semestre: 6

Disciplina: Classificação e pesquisa

 Aluno:

 Rafael Almeida de Oliveira RA: 1299887800

 Ramon de Andrade Silva RA: 2504124709

 Vinicius Vives Chalub RA: 7632736784

1.1.Introdução

Antes de mais nada, apresentarei o código-fonte dos algoritmos de pesquisa e ordenação utilizados, e um breve comentário sobre eles.

1.2.Busca linear ou sequencial

O método de pesquisa mais simples que existe. Funciona da seguinte forma: a partir do primeiro registro, pesquise sequencialmente até encontrar a chave procurada; então pare.

A função realizaBuscaLinear retorna o índice do registro que contém a chave x; caso não esteja presente o valor retornado é -1. Observe que esta implementação não suporta mais de um registro com uma mesma chave. Para aplicações com esta característica é necessário incluir um argumento a mais na função de pesquisa para conter o índice a partir do qual se quer pesquisar, e alterar a implementação de acordo.

2.1.1. Análise

A grande vantagem desse método de busca é que, além de se tratar de um algoritmo simples, os dados que serão analisados não precisam passar por nenhum tipo de preparo (como a ordenação, por exemplo) antes de execução do algorítimo, tornando seu uso extremamente simples e confiável. É mais eficiente quando a estrutura possui poucos elementos.

1 Código em C

/**

* Retorna -1 caso não encontre ou a posição

* caso encontre.

*/

int procura(char vetor[], int tamanho, char elementoProcurado) {

int i;

for (i = 0; i < tamanho; i++) {

if (vetor[i] == elementoProcurado) {

return i;

}

}

return -1;

}

Busca Binária (ou Pesquisa Binária)

Se não sabemos nada a respeito da ordem em que os itens aparecem no vetor, o melhor que podemos fazer é uma busca linear. Entretanto, se os itens aparecem ordenados5, podemos usar um método de busca muito mais eficiente. Esse método é semelhante aquele que usamos quando procuramos uma palavra num dicionário: primeiro abrimos o dicionário numa página aproximadamente no meio; se tivermos sorte de encontrar a palavra nessa página, ótimo; senão, verificamos se a palavra procurada ocorre antes ou depois da página em que abrimos e então continuamos, mais ou menos do mesmo jeito, procurando a palavra na primeira ou na segunda metade do dicionário.

Como a cada comparação realizada, o espaço de busca reduz-se aproximadamente

à metade:

Código em C

//em C para se passa um vetor como parâmetro para uma função, tem que se passar o ponteiro do vetor

int PesquisaBinaria ( int *array, int chave , int N)

{

int inf = 0; //Limite inferior (o primeiro elemento do vetor em C é zero )

int sup = N-1; //Limite superior (termina em um número a menos 0 à 9 são 10 numeros )

int meio;

while (inf v[i + 1])

{

swapbubble(v, i);

trocou = 1;

}

}while(trocou);

}

Insertion Sort

Insertion sort, ou ordenação por inserção, é um simples algoritmo, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer

Análise de Complexidade

Menor número de trocas e comparações entre os algoritmos de ordenação O(n) quando o vetor está ordenado. Pior caso O(n²).

Código em C

void insertionSort(int v[], int n)

{

int i, j, chave;

for(j=1; j= 0 && v[i] > chave)

{

v[i+1] = v[i];

i--;

}

v[i+1] = chave;

}

}

Shell Sort

Criado por Donald Shell em 1959, publicado pela Universidade de Cincinnati, Shell sort é o mais eficiente algoritmo de ordenação dentre os de complexidade quadrática. É um refinamento do método de inserção direta. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos