Aula 10
Algoritmos de Busca
Aquiles Burlamaqui
UERN
Roteiro

Algoritmos de Busca




Motivação
Definição
Tipos de Algoritmos
Algoritmos de Ordenação


Bubble Sort
Quick Sort
Motivação


A maioria dos algoritmos estudados
por cientistas da computação que
resolvem problemas são algortimos
de busca.
Uma vez que armazenada uma
informação, em um dado momento
você precisará recuperá-la.
Definição


“Algoritmo que toma um problema como entrada e retorna a
solução para o problema, geralmente após resolver um número
possível de soluções.”
“Um algoritmo de busca é um algoritmo que recebe um
parâmetro C e tenta achar um registro no arquivo (ou tabela)
cuja chave é C. O algoritmo retorna um ponteiro para o
registro, ou NULL (ou índice inválido) caso não ache o
registro.”
Tipos de Algoritmos de Busca

Busca em vetor ordenado


Busca seqüencial
Busca Binária
Busca Seqüencial

Problema:

determinar se um dado número está ou não está em um dado vetor
ordenado. Mais precisamente, dado um número x e um vetor
crescente v[0..n-1], encontrar um índice m tal que v[m] == x .
Busca Seqüencial
// A função abaixo recebe um número x e um vetor
// crescente v[0..n-1]. Ela devolve um índice m
// em 0..n-1 tal que v[m] == x. Se tal m não existe,
// a função devolve -1.
int buscaSequencial (int x, int n, int v[]) {
int m = 0;
while (m < n && v[m] < x) ++m;
if (m < n && v[m] == x)
return m;
else
return -1;
}
Busca Binária

A chave é comparada com o elemento no meio da
tabela. Se for igual, a busca terminou. Caso
contrário, ela deve continuar ou na metade inferior
(se a chave for menor que o elemento do meio) ou
na metade superior da tabela (se a chave for maior
que o elemento do meio).
Busca Binária
//
//
//
//
A função abaixo recebe um número x e um vetor
crescente v[0..n-1]. Ela devolve um índice m
tal que v[m] == x ou devolve -1 se tal m não
existe.
int buscaBinaria (int x, int n, int v[]) {
int e, m, d;
e = 0; d = n-1;
while (e <= d) {
m = (e + d)/2;
if (v[m] == x) return m;
if (v[m] < x) e = m + 1;
else d = m - 1;
}
return -1;
}
Busca Binária

Sempre teremos


v[e-1]
<
x
<
v[d+1] .
É a base de muitos algoritmos
eficientes para diversos problemas.
Algoritmos de Ordenação
Bubble Sort

A idéia básica do Buble Sort é percorrer
os dados do vetor (arquivo)
sequencialmente várias vezes. Em cada
passagem pelos dados devemos
comparar cada elemento com o seu
sucessor (x[k] com x[k+1]). Se os
elementos não estiverem ordenados
devemos trocá-los de posição.
Quick Sort
BubbleSort
Quick Sort





O Quicksort adota a estratégia de divisão e conquista. Os passos são:
1. Escolha um elemento da lista, denominado pivô;
2. Rearranje a lista de forma que todos os elementos anteriores ao
pivô sejam menores ou iguais a ele, e todos os elementos posteriores ao
pivô sejam maiores ou iguais a ele. Ao fim do processo o pivô estará em
sua posição final. Essa operação é denominada partição;
3. Recursivamente ordene a sublista dos elementos menores e a
sublista dos elementos maiores;
A base da recursão são as listas de tamanho zero ou um, que estão
sempre ordenadas. O processo é finito pois a cada iteração pelo menos
um elemento é posto em sua posição final e não será mais manipulado
na iteração seguinte.
Quick Sort
Quick Sort