Buscar

Aula 08 - Ordenação Externa (Algoritmos de pesquisa

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

OBS: Aula 07 foi exercício para entrega em sala de aula
A função da ordenação é otimizar a busca.
Define-se pesquisa como a operação que permite encontrar ou concluir que não existe, um dado 
elemento num conjunto. Existe uma variedade enorme de métodos de pesquisa.
Quantidade de dados envolvidos○
Arquivo estar sujeito a inserções e retiradas frequentes.○
A escolha do método de pesquisa mais adequado a determinada aplicação depende principalmente:
Busca Sequencial
A forma mais simples de encontrar um elemento em uma estrutura de dados é procurar cada 
elemento do vetor, um a um (busca sequencial). A pesquisa de um elemento pode ser feita um 
conjunto ordenado ou não.
Quando o conjunto não está ordenado, normalmente faz-se uso da busca sequencial até se 
encontrar o elemento desejado ou concluir que não existe.
Função buscaSequencial (n, chave: inteiro; var vet: interio) : inteiro
Var
i : inteiro
i <- 0
se vet[i] = chave) então
retorne i;
i <- i =1
enquanto (i<n) faça
fim enquanto
retorne -1
inicio 
fimfunção
Busca binária 
Encontra o meio do vetor
Se for igual, então para○
Se for menor, despreza os elementos à direita do meio○
Se for maior, despreza os elementos à esquerda do meio○
Compara o meio do vetor com o elemento buscado
Repete até que o elemento seja encontrado
Quando o conjunto está ordenado a busca binária é mais eficiente que a busca sequencial. Pela 
busca binária, a ideia é reduzir o espaço de busca já que a estrutura está ordenada.
função buscaBinária (n, chave: inteiro; ver vet: inteiro) : inteiro
esquerda,direita, meio : inteiro
var
Semana 06 - Aula 08 - Ordenação Externa (Algoritmos de 
pesquisa
sexta-feira, 4 de abril de 2014 19:14
 Página 1 de COM112 - Algoritmo e Estrutura de Dados II 
esquerda,direita, meio : inteiro
esquerda <- 0
direita <- n-1
meio = (esquerda + direita) / 2
retorne meio
se (vet[meio = chave)
esquerda = meio +1
Se (vet[meio] < chave)
direita = meio - 1
senao 
fimse
senao
fimsenão
enquanto (esquerda <= direita)
fimequanto
inicio
fimfunção
Para estruturas com variáveis diferentes criam-se índices para cada campo para facilitar a busca de 
acordo com o campo utilizado. Se estiver ordenada pela informação chave, a busca binária pode 
funcionar, mas para outros atributos como dados satélites, talvez não esteja ordenado.
 Página 2 de COM112 - Algoritmo e Estrutura de Dados II

Outros materiais