» Algoritmos: Pesquisa de Informação
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
• A procura/pesquisa de informação é uma das actividades
quotidianas mais frequentes;
• E consequentemente, uma das actividades preponderantes
num sistema informático;
• Embora a pesquisa de informação (procurar um elemento
entre um conjunto deles) pareça uma operação simples, criar
programas eficientes em termos de procura levanta vários
problemas;
• A pesquisa de informação é muitas vezes efectuada
recorrendo a tabelas. Assim, vamos analisar dois métodos de
pesquisa de informação em tabelas:
1. Procura sequencial ou linear
2. Procura binária
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Pesquisa Sequencial de Informação
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
1. Procura sequencial ou linear – é uma das formas mais
simples de procurar dados numa tabela. O que se faz é
percorrer a tabela: começa-se no 1º elemento e comparase esse elemento com o valor dado, depois passa-se para
o 2º elemento e compara-se com o valor dado, e assim
sucessivamente até que o valor seja encontrado ou
cheguemos ao fim da tabela.
Podemos fazer este tipo de procura de 2 formas:
Ordenação
“Shell Sort”
a) sem a utilização de sentinelas
Ordenação
“Selection Sort”
b) com a utilização de sentinelas
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Pesquisa Sequencial de Informação
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Procura Binária
Considere para os exemplos que se vão seguir, que as
variáveis e tipos foram definidos da seguinte forma:
Program procuratel (input, output);
Ordenação de
Informação:
Const
maxpessoas = 1000;
Ordenação
“Bubble Sort”
Type
repnome = array [1..25] of char;
tabnomes = array [1..maxpessoas] of repnome;
tabtelefones = array [1..maxpessoas] of integer;
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
Var
nomes : tabnomes;
telefones : tabtelefones;
nomedes : repnome;
i, telefone : integer;
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Pesquisa Sequencial de Informação
a) sem a utilização de sentinelas
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
Function procura (chave:repnome;
var nomes:tabnomes;
var telefones:tabtelefones):integer;
var
i : integer;
begin
i:=1;
while (nomes[i]<>chave) and (i<maxpessoas) do
i:=i+1
if nomes[i]=chave then
Esta função efectua
procura:=telefones[i];
uma procura
else
Sequencial na tabela
procura:=-1
Nomes tentando
end;
Encontrar a palavra
Correspondente à
Variável chave !
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Pesquisa Sequencial de Informação
•
Pesquisa de
Informação:
O problema da solução anterior é que a parte do programa
que diz respeito à procura propriamente dita, ou seja, a
instrução:
Procura Sequencial
ou Linear
while (nomes[i]<>chave) and (i<maxpessoas) do
i:=i+1;
Procura Binária
Ordenação de
Informação:
Tem de efectuar continuamente 2 testes, o que torna a
operação de pesquisa menos eficiente:
Ordenação
“Bubble Sort”
- ver se o nome que se procura foi encontrado:
Ordenação
“Shell Sort”
(nomes[i]<>chave)
Ordenação
“Selection Sort”
- ver se já se chegou ao fim da tabela:
(i<maxpessoas)
•
Note-se que o 1º teste é necessário mas o 2º só faz falta
porque não podemos garantir que o nome que
procuramos existe de facto na tabela.
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Pesquisa Sequencial de Informação
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Procura Binária
b) Uma forma de prescindir do 2º teste é através da utilização
do que se designa por valor sentinela, ou seja, um valor
que é inserido na tabela para garantir que a procura tem
sucesso:
Ordenação de
Informação:
Function procura (chave:repnome;
var nomes:tabnomes;
var telefones:tabtelefones):integer;
Ordenação
“Bubble Sort”
var
i : integer;
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
Begin
nomes[maxpessoascsent] := chave;
i:=1;
while (nomes[i]<>chave)do
i:=i+1
if i<>maxpessoascsent then
procura:=telefones[i];
else
procura:=-1
end;
Colocação do valor
Sentinela.
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Pesquisa Sequencial de Informação
• Para se poder utilizar um valor sentinela é preciso que existe uma
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Posição adicional na tabela, ou seja, se a tabela tem n elementos terá
de ter n+1 posições;
• Nessa posição adicional da tabela (n+1) coloca-se o valor sentinela;
• A seguir efectua-se a pesquisa normalmente;
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
• A última operação tem de ser verificar se o valor encontrado
corresponde ao valor sentinela.
• O exemplo do slide anterior pressupõe que a definição inicial do
programa principal passe a ser:
Ordenação
“Shell Sort”
Program procuratel (input, output);
Ordenação
“Selection Sort”
Const
maxpessoas = 1000;
maxpessoascsent = 1001;
Type
repnome = array [1..25] of char;
tabnomes = array [1..maxpessoascsent] of repnome;
tabtelefones = array [1..maxpessoas] of integer;
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Pesquisa Binária de Informação
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
2. Procura binária – é uma alternativa à procura sequencial e
é mais eficiente só que exige que os elementos que estão
a ser pesquisados se encontrem ordenados. Este tipo de
procura reduz o nrº de elementos a pesquisar para metade
pois processa-se da seguinte forma:
a) começa-se por se considerar o elemento que está no
meio da tabela;
b) se esse valor for maior (ou seja, aparecer depois) que o
elemento que estamos a procurar então a procura será
feita apenas na primeira metade da tabela;
c) se esse valor for menor (ou seja, aparecer antes) que o
elemento que estamos a procurar então a procura será
feita apenas na segunda metade da tabela;
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Pesquisa Binária de Informação
Function procura
Pesquisa de
Informação:
(chave:repnome;
var nomes:tabnomes;
var telefones:tabtelefones):integer;
Procura Sequencial
ou Linear
var
LimInf, LimSup, Meio : integer;
Procura Binária
begin
LimInf:=1;
LimSup:=Maxpessoas;
Ordenação de
Informação:
Ordenação
“Bubble Sort”
repeat
meio:=(LimInf+LimSup) div 2;
if chave<Nomes[Meio]then
LimSup:=Meio-1;
else
LimInf:=Meio+1;
until (chave=Nomes[Meio]) or (LimInf>LimSup);
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
if chave=Nomes[Meio] then
procura:=telefones[Meio];
else
procura:=-1
end;
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Ordenação Bolha (Bubble Sort)
Pesquisa de
Informação:
Procura Sequencial
ou Linear
•
Já vimos que a ordenação da informação facilita as
operações de busca tornando-as mais eficientes;
•
Os algoritmos de ordenação dividem-se em 2 grandes
grupos:
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
•
a)
os de ordenação interna – que ordenam os elementos
que estão simultaneamente armazenados em
memória, ex: tabela;
b)
os de ordenação externa – que ordenam elementos
que por serem muitos não podem estar
simultaneamente em memória, estando parte desses
elementos armazenada no computador em ficheiros;
Os algoritmos que vamos ver são apenas de ordenação
interna, ou seja, algoritmos para a ordenação de dados
armazenados em tabelas .
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Ordenação por Borbulhamento (“Bubble Sort”)
• É o mais simples e básico algoritmo de ordenação.
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Procura Binária
Ordenação de
Informação:
• A ideia básica é:
- percorrer todos os elementos a ordenar;
- comparar elementos adjacentes;
- trocar os pares de elementos que estejam fora de
ordem;
-De um modo geral uma única passagem por todos os
elementos não é suficiente para ordenar a tabela, sendo
normal várias passagens pelos elementos. A tabela só
estará ordenada quando for efectuada uma passagem
por todos os elementos sem que seja efectuada
qualquer troca.
Ordenação
“Bubble Sort”
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
• O único problema deste tipo de ordenação é que não se
torna muito eficiente dado que apenas são trocados os
valores adjacentes. Assim, se um elemento estiver muito
longe da sua posição final ordenada é preciso efectuar
muitas passagens até que seja colocado no seu devido lugar.
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Ordenação por Borbulhamento (“Bubble Sort”)
Exemplo 1:
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
Program BSort(input,output);
const
n=10;
var
i, j : integer;
temp : integer;
a
: array[1..n] of integer;
begin
for i:=1 to (n-1) do
for j:=i+1 to n do
if a[i]>a[j] then begin
temp:=a[i];
a[i]:=a[j];
a[j]:=temp;
end;
end.
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Ordenação por Borbulhamento (“Bubble Sort”)
Exemplo 2:
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
Procedure ordena(.....);
Const
tamanho=10;
var
i : integer;
nenhumatroca : boolean;
numeros:array[1..tamanho];
Procedure troca (var x,y:integer);
var temp :integer;
begin
temp:=x;
x:=y;
end
begin
repeat
nenhumatroca:=true;
for i:=1 to tamanho-1 do
if numeros[i]>numeros[i+1] then
begin
troca(numeros[i],numeros[i+1]);
nenhumatroca:=false;
end
until nenhumatroca:=true
End;
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Ordenação “Shell Sort”
Pesquisa de
Informação:
• É uma variante da ordenação por borbulhamento;
Procura Sequencial
ou Linear
• A ideia básica:
- comparar e trocar por borbulhamento, não os
elementos adjacentes mas os elementos separados por
um certo intervalo (que é metade do número de
elementos a ordenar);
-depois esse intervalo é dividido ao meio e o processo
repete-se até que o intervalo seja 1.
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
• Esta ordenação é mais eficiente que a ordenação por
borbulhamento dado que as primeiras passagens apenas
consideram um subconjunto do total de elementos a ordenar
e as últimas passagens, que são as que vão incidir sobre
todos os elementos já os vão encontrar parcialmente
ordenados.
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Ordenação
“Shell Sort”
Procedure ordena(.....);
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
Estrutura e Organização de Dados
Const
tamanho=10;
var
intervalo, i : integer;
nenhumatroca : boolean;
numeros:array[1..tamanho];
Procedure troca (var x,y:integer);
var temp :integer;
begin
temp:=x;
x:=y;
end
Begin
intervalo:=tamanho div 2;
repeat
repeat nenhumatroca:=true;
for i:=1 to tamanho-intervalo do
if numeros[i]>numeros[i+intervalo] then
begin
troca(numeros[i],numeros[i+intervalo]);
nenhumatroca:=false;
end
until nenhumatroca:=true
intervalo := intervalo div 2
until intervalo:=0
End;
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Ordenação por Selecção (“Selection Sort”)
Pesquisa de
Informação:
Procura Sequencial
ou Linear
• Consiste em percorrer todos os elementos a ordenar e a
cada passagem coloca um elemento na posição correcta, ou
seja:
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
Ordenação
“Shell Sort”
- na primeira passagem o valor mais pequeno é
colocado na posição correcta;
-na segunda passagem o segundo valor mais pequeno é
colocado na posição correcta;
- e assim sucessivamente...
Ordenação
“Selection Sort”
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007
» Algoritmos: Ordenação por Selecção (“Selection Sort”)
Pesquisa de
Informação:
Procura Sequencial
ou Linear
Procura Binária
Ordenação de
Informação:
Ordenação
“Bubble Sort”
Ordenação
“Shell Sort”
Ordenação
“Selection Sort”
Procedure ordena(.....);
Const
tamanho=10;
var
posmenor, i, j : integer;
nenhumatroca : boolean;
numeros:array[1..tamanho];
Procedure troca (var x,y:integer);
var temp :integer;
begin
temp:=x;
x:=y;
end
Begin
for i:=1 to tamanho-1 do
begin
posmenor:=i;
for j:=i+1 to tamanho do
if numeros[j]<numeros[posmenor] then
posmenor:=j;
troca(numeros[i], numeros[posmenor])
end
End;
Estrutura e Organização de Dados
Gestão de Sistemas de Informação – 1ºAno
(c) Alcina Prata & Luís Coelho, 2007