Classificação e Pesquisa ATPS

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,

conhecida: O(nlog2n).

2 Código em C

void shellSort(int * vet, int size) {

int i , j , value;

int gap = 1;

do {

gap = 3*gap+1;

} while(gap < size);

do {

gap /= 3;

for(i = gap; i < size; i++) {

value =vet[i];

j = i - gap;

while (j >= 0 && value < vet[j]) {

vet [j + gap] =vet[j];

j -= gap;

}

vet [j + gap] = value;

}

} while ( gap > 1);

}

Selection Sort

O selection sort (do inglês, ordenação por seleção) é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.

Análise de Complexidade

O algoritmo possui complexidade O(n2) enquanto que, por exemplo, os algoritmos HeapSort e MergeSort possuem complexidades O(nlogn).

Código em C

void selection_sort(int num[], int tam) {

int i, j, min;

for (i = 0; i < (tam-1); i++) {

min = i;

for (j = (i+1); j < tam; j++) {

if(num[j] < num[min]) {

min = j;

}

}

if (i != min) {

int swap = num[i];

num[i] = num[min];

num[min] = swap;

}

}

}

Heapsort

O algoritmo heapsort é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por seleção.

Análise de Complexidade

Tem um desempenho em tempo de execução muito bom em conjuntos ordenados

conhecida: O(nlog2n).

2 Código em C

void shellSort(int * vet, int size) {

int i , j , value;

int gap = 1;

do {

gap = 3*gap+1;

} while(gap < size);

do {

gap /= 3;

for(i = gap; i < size; i++) {

value =vet[i];

j = i - gap;

while (j >= 0 && value < vet[j]) {

vet [j + gap] =vet[j];