Atps classificação e pesquisa

ATPS de Classificação e Pesquisa

(Etapa 1 e Etapa 2)

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.

Busca Linear (ou Busca Sequencial)

1 Análise de Complexidade

No melhor caso, o elemento a ser buscado é encontrado logo na primeira tentativa da busca. No pior caso, o elemento a ser buscado encontra-se na última posição e são feitas N comparações, sendo N o número total de elementos. No caso médio, o elemento é encontrado após N/2 comparações. O algoritmo de busca linear é um algoritmo O(n).

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)

2 Análise de Complexidade

A complexidade desse algoritmo é da ordem de Θ(log2 n), em que n é o tamanho do vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é O(n).

1 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