Busca (Search)
Busca seqüencial
dados n elementos num array
Técnica mais simples para determinar
se o array contém um dado elemento x.
for ( i = 1, n) do
{
if ( A [ i ] == x ) return i;
}
return 0;
CAP-223
Busca (Search) - cont.
Busca binária
Se os dados num array seguem uma ordem
(por exemplo ), i.e.,  k, 1 k<n: A[k]  A[k+1]
A busca por um elemento x se torna mais
rápida
Comparação do x com A[i] fornece maiores
informações
xA[i] exclui não só A[i] mas também todos
os elementos de um dos lados do A[i]
CAP-223
Busca (Search) - cont.
u = 1; v = n
while u  v do
{
m = qualquer valor u  m  v
if
x < A[m] then v = m - 1
elseif x > A[m] then u = m + 1
else return m
}
return notfound
CAP-223
Busca (Search) - cont.
Hashing
faz uma referência direta aos registros numa
tabela realizando transformações aritméticas
em endereços na tabela
se as chaves forem inteiros distintos de 1 a N,
então pode-se armazenar o registro com chave
i na posição i dentro da tabela
Hashing é uma generalização desta metodologia
quando não há conhecimento dos valores das
chaves
CAP-223
Busca (Search) - cont.
Hashing é um bom exemplo de compromisso
entre tempo e memória
Se não houvesse limitação de memória, pode-se
fazer qualquer busca com somente um único
acesso.
Se não houvesse limitação de tempo, pode-se
realizar a busca seqüencial
Uso eficiente de memória disponível e acesso
rápido são principais fatores dos métodos hash
CAP-223
Busca (Search) - cont.
Endereçamento direto - elemento k é
armazenado na posição k
Com o hashing, o elemento k é
armazenado na posição h(k), onde h é
uma função hash para determinar a
posição a partir da chave k.
CAP-223
Busca (Search) - cont.
Primeiro passo numa busca utilizando hashing
é calcular uma função de hash que transforma
a chave de busca num endereço da tabela
Ideal seria chaves diferentes mapeando para
endereços diferentes - MAS NENHUMA
FUNÇÃO HASH é perfeita
Processo de collision-resolution (resolução de
colisão)
CAP-223
Busca (Search) - cont.
O ideal é que uma boa função hash satisfaça
hashing uniforme: cada chave tem a mesma
probabilidade de ser alocada a qualquer uma
das m posições
Infelizmente isto nem sempre é possível. Nem
sempre a distribuição é conhecida. Em muitos
casos as chaves podem NÃO ser geradas
de uma forma independente.
CAP-223
Busca (Search) - cont.
Informação qualitativa sobre a distribuição das
chaves pode ser muito útil para criar uma
função hash
Como exemplo, considere tabela de símbolos
de um compilador onde as chaves são “strings”
que representam identificadores num programa.
Símbolos próximos como pt e pts ocorrem num
mesmo programa. Uma boa função hash seria
minimizar a chance de que tais variações sejam
alocadas para a mesma posição
CAP-223
Busca (Search) - cont.
Uma boa política é derivar umo valor hash tal
que este valor é independente de quaisquer
padrões que possam existir nos dados
Um bom exemplo é o “método de divisão”
O valor de hash é o resto quando a chave é
dividida por um número primo.
Algumas aplicações podem precisar de certas
propriedades específicas. Por exemplo,
chaves “próximas” deveriam gerar valores
hash distantes.
CAP-223
Busca (Search) - cont.
Maioria das funções hash supõe que o universo
das chaves é um conjunto de números Naturais.
Quando não é, teria que achar uma forma de
interpretar as chaves como números Naturais.
Método da divisão - h(k) = k mod m,
mapear a chave k em umas das m posições
Exemplo: k = 100 e m = 12  h(k) = 4
Evitar certos valores para m. m NÃO deveria ser
potência de 2. Se m = 2p, então h(k) é apenas
os p bits menos significativos de k. É melhor
uma função que dependa de todos os bits de k.
CAP-223
Busca (Search) - cont.
Um número primo que não seja muito próximo
a uma potência exata de 2 é, em geral, uma boa
opção para m.
Exemplo: n = 2000 e quando há insucesso, não
teria importância de examinar uma média de
3 elementos.
m deveria ser 701, pois é um
primo próximo a 2000/3 e não é próximo a
nenhuma potência de 2.
h(k) = k mod 701
CAP-223
Busca (Search) - cont.
Função Hash - mod M, onde M é tamanho
da tabela
chave AKEY - 44217  80
chave BARH  80
Uso da lista ligada para cada endereço onde
a lista contém registros com aquele endereço
M listas
CAP-223
Busca (Search) - cont.
M:
11
chave: A-S-E-A-R-C-H-I-N-G-E-X-A-M-P-L-E
hash: 1 8 5 1 7 3 8 9 3 7 5 2 1 2 5 1 5
0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10
A X C
E
G S I
A M N
E
R H
A
E
L
P
Separate chaining (encadeamento separado)
registros em colisão são “encadeados” em
listas ligadas
CAP-223
Busca (Search) - cont.
Linear Probing
M (tamanho da tabela) > N registros
Examinar posição imediatamente após
a posição em colisão
comparar a chave com o registro
se chaves forem iguais sucesso
se não há registro insucesso
senão procure na posição seguinte
CAP-223
Busca (Search) - cont.
M:
19
chave: A-S-E-A-R-C-H-I-N-G-E-X-A-M-P-L-E
hash: 1 0 5 1 18 3 8 9 14 7 5 5 1 13 16 12 5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
A
S
E
A
R
C
H
E
I
N
G
X
CAP-223
Busca (Search) - cont.
Double Hashing
Sempre que houver um conflito (colisão),
em vez de procurar a próxima posição
vazia, é usada uma outra função hash cujo
valor é somado ao valor da chave.
O processo trabalha com duas funções hash
CAP-223
Busca (Search) - cont.
M:
19
chave: A-S-E-A-R-C-H-I-N-G-E-X-A-M-P-L-E
hash1: 1 0 5 1 18 3 8 9 14 7 5 5 1 13 16 12 5
hash2: 7 3 3 7 6 5 8 7 2 1 3 8 7 3 8 4 3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
A
S
E
A
H
C
I
G
R
N
E
X
CAP-223
Busca (Search) - cont.
•Radix Searching
»Radix Search Tries
»Multiway Radix Searching
»Patricia (Practical Algorithm To Retrieve
Information Coded in
Alphanumeric)
•External Searching
»Indexed Sequential Access
»B-Trees
»Extendible Hashing
CAP-223
Classificação (Sorting)
Ordenar (classificar) arquivos de registros
contendo chaves
Ordenação interna - arquivo a ser ordenado
cabe na memória

registros são fáceis de acessar
Ordenação externa - arquivos em disco

acesso seqüencial ou em blocos grandes
CAP-223
Classificação (Sorting) - cont.
Selection sort
• ache o menor elemento e troca-o com o elemento
que está na primeira posição
• ache o segundo menor elemento e troca-o com o
que está na segunda posição
• continue com este processo até que a lista está
totalmente classificada
“seleciona” o menor elemento que restou
CAP-223
Classificação (Sorting) - cont.
for i := 1 to N - 1 do {
min := i;
for j := i + 1 to N do {
if a [ j ] < a [ min ] then min := j;
}
t := a [ min ];
a [ min ] := a [ i ];
a [ i ] := t;
}
CAP-223
Classificação (Sorting) - cont.
Insertion sort
Mais flexível do que Selection Sort
Elemento sendo considerado é inserido movendo
elementos maiores uma posição a direita
for i := 2 to N do {
v := a [ i ]; j := i;
while a [ j - 1 ] > v do {
a [ j ] := a [ j - 1 ];
j--;
}
a [ j ] := v;
}
CAP-223
Classificação (Sorting) - cont.
Bubble sort
Passe pelos elementos trocando elementos
adjacentes. Em algum momento quando não
foi efetuada nenhuma troca, a lista está classificada
for i := N to 1 do {
for j := 2 to i do {
if a [ j - 1 ] > a [ j ] then {
t := a [ j - 1 ];
a [ j - 1 ] := a [ j ];
a [ j ] := t;
}
}
{
CAP-223
Classificação (Sorting) - cont.
Shell sort
•h é um número escolhido
•os elementos com distância-h são classificados
•h vai sendo decrementado até 1 (seqüências ...)
•nesta fase não há necessidade mover elementos
a uma distância grande
h = ..., 1093, 364, 121, 40, 13, 4, 1
CAP-223
Classificação (Sorting) - cont.
h := 1; repeat h := 3*h + 1 until h > N;
repeat
h := h div 3;
for i := h + 1 to N do {
v := a [ i ]; j := i;
while a [ j - h ] > v do {
a [ j ] := a [ j - h ];
j := j - h;
if j <= h then {
a [ j ] := v;
break;
}
}
}
until h = 1;
CAP-223
Classificação (Sorting) - cont.
25 - 57 - 48 - 37 - 12 - 92 - 86 - 33
seqüência (h) é (5, 3, 1)
25 - 57 - 48 - 37 - 12 - 92 - 86 - 33
h=5
25 - 57 - 33 - 37 - 12 - 92 - 86 - 48
h=3
25 - 12 - 33 - 37 - 48 - 92 - 86 - 57
...
CAP-223
Classificação (Sorting) - cont.
Radix sort
• propriedades “digitais”
• comparam e processam pedaços de chaves
• sistema base M
Exemplo: radix 4 (cada dígito entre 0 e 3)
e no máximo 3 dígitos
301 - 023 - 230 - 322 - 100 - 321 - 213
Dígito mais à direita
- classifica
Dígito central
- classifica
Dígito mais à esquerda - classifica
CAP-223
Classificação (Sorting) - cont.
Mergesort
•Arquivos grandes com inserções regulares de
novos elementos
•Organizar novos registros em lote e inserir este
lote no “arquivão”
i := j := 1;
for k := 1 to M + N do {
if a [ i ] < b [ j ] then {
c [ k ] := a [ i ]; i++;
}
else {
c [ k ] := b [ j ]; j++;
}
}
CAP-223
Classificação (Sorting) - cont.
Variações de Mergesort
•List Merge sort
•Bottom-up Merge sort
CAP-223
Classificação (Sorting) - cont.
Quicksort
C. A. R. Hoare (1960)
Muito usado e muito popular
Fácil de implementar
Funciona em uma variedade de situações
Consumo de poucos recursos
Operações cerca de N log N
Problemas: implementação recursiva
pior caso N2 operações
frágil: pequeno erro na implementação
pode afetar no desempenho
CAP-223
Classificação (Sorting) - cont.
Algoritmo utiliza princípio de divide-and-conquer
 divide - particiona em:
elementos menores à esquerda
elementos maiores à direita
 conquer - classifica as duas partes em separado
Problema de Partição
 achar um limite m tal que elementos menores
à esquerda são  m e elementos maiores
à direita
são  m
CAP-223
Classificação (Sorting) - cont.
Particiona um subarray a [ left .. right ]
e ordena de esquerda para direita
incrementando i e “ao mesmo tempo”
ordena da direita para esquerda
decrementando j
CAP-223
Classificação (Sorting) - cont.
Sugestões para partição
 a [ ( left+right )div 2 ]
 elemento escolhido aleatoriamente
 mediana de três ou cinco elementos do
array a partir de posições fixas ou
aleatórias
 média entre menor e maior elemento (?)
CAP-223
Classificação (Sorting) - cont.
quicksort ( left, right ) {
partition ( i, j, left, right );
if left < j then quicksort ( left, j );
if i < right then quicksort ( i, right );
}
partition ( i, j, left, right ) {
m := guessmedian ( left, right );
i := left; j := right;
repeat
while a [ i ] < m do i++;
while m < a [ j ] do j--;
if i  j then { a [ i ] := a [ j ]; i++; j--; }
until i > j;
}
CAP-223