Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
Jorge Cruz
DI/FCT/UNL
Introdução aos Computadores e à Programação
1º Semestre 2006/2007
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
1
Ordenação de Vectores, Matrizes e Listas
• As estruturas de dados (vectores, matrizes ou listas) são
frequentemente armazenadas de uma forma ordenada.
• A ordenação facilita, a pesquisa de informação. Como veremos,
numa lista ordenada com n elementos a procura de um elemento
pode ser feito com log2(n) acessos em vez de n operações.
• Por exemplo, se uma lista tiver 107 = 10 000 000 elementos (por
exemplo, o número de portugueses na base de dados do BI), em
vez de 10 000 000 de acessos à lista (para encontrar um #BI), são
necessários apenas cerca de log2(107) ≈ 23.25, em média.
• Evidentemente a ordenação tem custos. Mas como é
frequentemente o caso, a ordenação é feita 1 vez, e os acessos
muitas vezes, compensa manter as estruturas de dados ordenadas.
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
2
Ordenação de Vectores
• Analisemos primeiro a ordenação de vectores, para o que existem
vários algoritmos (de ordenação) com vantagens e desvantagens
em diferentes contextos.
• Uma característica importante dos algoritmos é o espaço de
memória utilizado, que não consideraremos neste caso, já que
apenas se utiliza o espaço ocupado pelo vector.
• Outra característica importante é a sua complexidade, medida em
número de acessos ao vector. Este número depende naturalmente
do número n de elementos da estrutura de dados utilizada.
• Embora existam algoritmos (quicksort) mais rápidos (necessitam
de cerca de nlog2 n acessos), o que apresentamos (bubblesort) é
mais simples de descrever.
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
3
Ordenação de Vectores – Bubble Sort
• A ideia do algoritmo é comparar dois elementos consecutivos do
vector, e trocá-los se tiverem na ordem “errada”.
• Esta comparação é feita entre todos os n-1 pares do vector, por
uma determinada ordem, por exemplo (1,2), (2,3), ..., (n-1,n).
• Se não fôr feita nenhuma troca, o vector já está ordenado. Caso
contrário, repete-se o processo.
• No pior caso (em que V(n) era o elemento mais pequeno do
vector), é necessário executar n-1 vezes este “varrimento” do
vector (mais 1 vez para “ter a certeza”).
• No total, e para o pior caso, são feitas n(n-1) comparações, das
quais algumas serão trocas, pelo que a complexidade será
quadrática no número de elementos do vector (≈ n2).
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
4
Ordenação de Vectores – Bubble Sort
• Podemos observar o comportamento deste algoritmo nos dois
casos abaixo com um vector com 4 elementos, que se pretende
ordenar de forma crescente.
17 Novembro 2006
9
7
7
7
9
4
4
4
9
1
1
1
t
t
t
7
4
4
4
7
1
1
1
7
9
9
9
t
t
4
1
1
1
4
4
7
7
7
9
9
9
t
1
1
1
4
4
4
7
7
7
9
9
9
Pior caso
4*3 = 12 comparações
6 trocas
Caso “típico”
3*3 = 9 comparações
3 trocas
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
1
1
1
9
9
7
7
7
9
4
4
4
1
1
1
7
7
4
4
4
7
9
9
9
1
1
1
4
4
4
7
7
7
9
9
9
t
t
t
5
Ordenação de Vectores – Bubble Sort
• A função abaixo implementa o algoritmo de bubble sort. No início
de cada ciclo for a variável troca é falsa. Se se mantiver falsa no
fim do ciclo, o vector já se encontra ordenado e não é necessário
mais nenhum ciclo for.
function V = bubble_vec(V)
% bubble sort
n = length(V);
do
troca = false;
for i = 1:n-1
if V(i) > V(i+1)
troca = true;
x=V(i); V(i)=V(i+1); V(i+1)=x; %troca
endif;
endfor;
n = n-1;
% o n-ésimo já está ordenado!
until ! troca;
endfunction;
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
6
Ordenação de Listas de Registos
• Um problema importante é o da apresentação dos registos de
acordo com uma determinada ordem. Por exemplo:
– Apresentar uma listagem dos empregados por ordem alfabética;
– Apresentar uma listagem dos empregados ordenados por antiguidade;
• Complementarmente, podem-se adicionar restrições:
– Apresentar uma listagem, ordenada por ordem alfabética, dos empregados
que tenham um vencimento superior a 1000 €;
– Apresentar uma listagem, ordenada por antiguidade, dos empregados que
tenham um vencimento superior a 1000 €;
• O algoritmo de ordenação apresentado (bubble sort) pode ser usado
directamente para ordenar uma lista de registos de acordo com o
valor de um campo.
• Se L é uma lista de registos, nth(L,i) é o elemento de índice i
• No exemplo da lista de empregados, o código, nome, vencimento e
data do empregado de índice i são respectivamente:
nth(L,i).cod, nth(L,i).nome, nth(L,i).venc e nth(L,i).data
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
7
Ordenação de Listas de Registos
• A função abaixo ordena a lista L por ordem decrescente de
vencimentos dos empregados:
function L = bubble_list_venc_dec(L) % bubble sort
n = length(L);
do
troca = false;
for i = 1:n-1
reg1 = nth(L,i); reg2 = nth(L,i+1);
if reg1.venc < reg2.venc
troca = true;
L(i)
= reg2;
L(i+1) = reg1;
endif;
endfor;
n = n-1;
until ! troca;
endfunction;
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
8
Ordenação de Listas de Registos
• Se o campo de ordenação não for numérico terá que ser evocada uma
função adequada para verificar a ordem dos elementos.
• A função abaixo ordena a lista L por ordem alfabética dos nomes dos
empregados:
function L = bubble_list_nome_asc(L) % bubble sort
n = length(L);
do
troca = false;
for i = 1:n-1
reg1 = nth(L,i); reg2 = nth(L,i+1);
if my_str_norm_before(reg1.nome,reg2.nome)==-1
troca = true;
L(i)
= reg2;
L(i+1) = reg1;
endif;
endfor;
n = n-1;
until ! troca;
endfunction;
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
9
Ordenação de Listas de Registos
• Uma alternativa à ordenação directa de listas é a utilização (e
ordenação) de vectores de índices para representar as sequências
dos elementos de uma lista.
• Por exemplo:
– o vector [1, 2, 3, 4, 5] pode representar os cinco primeiros elementos de uma
lista na sequência: 1º, 2º, 3º, 4º e 5º.
– o vector [5, 4, 3, 2, 1] pode representar os mesmos cinco elementos mas por
ordem inversa.
– o vector [4, 1, 2] apenas representa 4º, 1º e 2º elementos (por essa ordem)
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
10
Algoritmos de Ordenação e Listas
• Deste modo, a função listagem_nome_venc apresenta o nome e
vencimento dos empregados de acordo com a ordenação dos
índices representada no vector V:
function listagem_nome_venc(L,V)
n=length(V);
for i=1:n
printf("Nome: %-25s Vencimento: %7.2f \n"
,nth(L,V(i)).nome, nth(L,V(i)).venc);
endfor;
endfunction;
• Assim, para obtermos uma listagem ordenada basta ordenar os
índices e chamar a função listagem_nome_venc.
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
11
Ordenação de Listas de Registos
• A função abaixo ordena o vector de índices V por ordem
decrescente de vencimentos dos empregados da lista L :
function V = bubble_ind_venc_dec(L,V) % bubble sort
n = length(V);
do
troca = false;
for i = 1:n-1
reg1 = nth(L,V(i)); reg2 = nth(L,V(i+1));
if reg1.venc < reg2.venc
troca = true;
x=V(i); V(i)=V(i+1); V(i+1)=x;
endif;
endfor;
n = n-1;
until ! troca;
endfunction;
• Para escrever os nomes e vencimentos dos empregados por essa
ordem:
V = bubble_ind_venc_dec(L,V);
listagem_nome_venc(L,V);
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
12
Ordenação de Listas de Registos
• A função abaixo ordena o vector de índices V por ordem alfabética
dos nomes dos empregados da lista L :
function V = bubble_ind_nome_asc(L,V) % bubble sort
n = length(V);
do
troca = false;
for i = 1:n-1
reg1 = nth(L,V(i)); reg2 = nth(L,V(i+1));
if my_str_norm_before(reg1.nome,reg2.nome)==-1
troca = true;
x=V(i); V(i)=V(i+1); V(i+1)=x;
endif;
endfor;
n = n-1;
until ! troca;
endfunction;
• Para escrever os nomes e vencimentos dos empregados por essa
ordem:
V = bubble_ind_nome_asc(L,V);
listagem_nome_venc(L,V);
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
13
Ordenação de Listas de Registos
• A vantagem de utilizar vectores de índices é poder manter
simultaneamente diferentes critérios de ordenação que não
necessitam de envolver todos os elementos da lista.
• Por exemplo, a função abaixo cria um vector apenas com os índices
dos empregados com um vencimento superior a 1000 €:
function
V=[];
for i
if
V = select_venc(L)
j=0; n=length(L);
= 1:n
nth(L,i).venc > 1000
j=j+1; V(j)=i;
endif;
endfor;
endfunction;
• Para mostrar todos os empregados por ordem alfabética e só os com
vencimentos acima de 1000 € por ordem decrescente de ordenado:
V1 = bubble_ind_nome_asc(L,1:length(L));
V2 = bubble_ind_venc_dec(L,select_venc(L));
listagem_nome_venc(L,V1);
listagem_nome_venc(L,V2);
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
14
Pesquisa em Vectores
• Consideremos um vector V, não ordenado, onde queremos
encontrar o número x. O algoritmo abaixo determina se o número
x está ou não incluído no vector, comparando x com todos os
valores da lista.
• A função retorna o índice i onde se encontra x (ou seja, V(i) = x),
ou retorna 0 se x não estiver incluído no vector
function i = procura_vec(x,V);
for i = 1:length(V);
if V(i) == x
return;
endif
endfor;
i = 0;
endfunction;
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
15
Pesquisa em Vectores
• A complexidade do algoritmo, em termos do número de acessos
ao vector, pode ser analisado da seguinte forma:
– Se x não pertence ao vector, então terão de ser feitas n leituras.
– Se x pertencer ao vector, o número de leituras é variável.
Assumindo que x pode estar em qualquer posição, deverão ser
lidos, em média, n/2 valores.
• Assumindo que x pode estar em V com uma probabilidade p (e
não estar com uma probabilidade q = 1-p), o número médio de
acessos será de aproximadamente
p  n/2 + q  n
• Se p = q = ½ teremos uma complexidade média de
½½n+½n =¾n
o que indica uma complexidade assintótica linear, O(n).
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
16
Pesquisa Linear em Vectores Ordenados
• A complexidade da pesquisa pode ser melhorada se o vector está
ordenado. Assumindo uma ordenação crescente, a pesquisa pode
terminar se o valor V(i) já exceder o valor de x, porque nesse
caso, os valores de V(j) com j > i serão ainda maiores!
function i = procura_vec_lin(x,V);
i = 1;
while i < length(L) & x > V(i);
i = i + 1;
endwhile
if x != V(i)
i = 0
endif;
endfunction;
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
17
Pesquisa Linear em Vectores Ordenados
• A complexidade, em termos do número de acessos ao vector, pode
ser analisada da seguinte forma:
– Como anteriormente, se x pertencer ao vector, o número de
leituras é variável, sendo em média lidos n/2 valores.
– Se x não pertencer ao vector, esse facto poderá ser descoberto
no início ou no fim, consoante o valor de x. Em média,
podemos assumir que apenas metade dos valores são testados
• Como x está em V com uma probabilidade p, e não está com
probabilidade 1-p, o número médio de acessos será de
p  n/2 + (1-p)  n/2 = n/2
• O número de acessos baixa assim de ¾ n para ½ n, mas mantém a
mesma complexidade assintótica linear, O(n).
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
18
Pesquisa Bipartida em Vectores Ordenados
• Se o vector está ordenado, podemos sempre determinar se x, a
existir no vector está à frente ou atrás de um elemento testado.
• Assim em vez de testar sequencialmente os valores de V,
podemos testá-los “em saltos”, delimitando em cada teste a
zona do vector onde valerá a pena pesquisar.
• Esquemáticamente, podemos considerar um esquema de
bipartição
x < V(i)
x > V(i)
i
• O algoritmo pode pois considerar um intervalo de pesquisa
cada vez menor, como exemplificado de seguida.
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
19
Pesquisa Bipartida em Vectores Ordenados
• Consideremos um vector V, ordenado por ordem crescente, com
31 números, onde queremos encontrar o número x. Inicialmente
os índices onde se faz a pesquisa estão no intervalo (1,31).
• Podemos comparar x com o número intermédio 16 (i.e. (1+31)/2).
– Se V(16) = x, este está encontrado.
– Se V(16) < x, este deverá ser procurado no intervalo (17,31).
– Se V(16) > x, este deverá ser procurado no intervalo (1,15).
• Neste último caso, podemos comparar x com o número
intermédio 8 (i.e. (1+15)/2).
– Se V(8) = x, este está encontrado.
– Se V(8) < x, este deverá ser procurado no intervalo (9,15).
– Se V(8) > x, este deverá ser procurado no intervalo (1,7).
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
20
Pesquisa Bipartida em Vectores Ordenados
• No segundo caso, podemos comparar x com o número intermédio
12 (i.e. (9+15)/2).
– Se V(12) = x, este está encontrado.
– Se V(12) < x, este deverá ser procurado no intervalo (13,15).
– Se V(12) > x, este deverá ser procurado no intervalo (9,11).
• No segundo caso, podemos comparar x com o número intermédio
14 (i.e. (13+15)/2).
– Se V(14) = x, este está encontrado.
– Se V(14) < x, este deverá ser procurado no intervalo (15,15).
– Se V(14) > x, este deverá ser procurado no intervalo (13,13).
• Nestes últimos casos, são feitas comparações com um só elemento
V(13) ou V(15), que indicam se x está ou não no vector V .
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
21
Pesquisa Bipartida em Vectores Ordenados
• No máximo, são feitas 5 comparações, com V(16), V(8), V(12),
V(14) e V(15), o que confirma que o número máximo de acessos
é da ordem de log2(n), já que log2(31) = 4.95 ≈ 5.
• Em geral, o intervalo inicial, de largura n, é reduzido para metade
em cada um de p passos, sendo feita uma comparação em cada
passo, e terminando o processo quando o intervalo tiver largura 1.
Assim, temos
n  ½  ½  ...  ½ = 1,
donde n / 2p = 1
e portanto n = 2p
ou
p = log2(n).
• Como p é o número de comparações, a pesquisa bipartida tem,
como visto atrás, complexidade assintótica logaritmica O( log2(n))
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
22
Pesquisa Bipartida em Vectores Ordenados
• O algoritmo descrito pode ser implementado através das funções
procura_vec_bip e p_vec_bip, que retornam o índice do elemento
do vector V onde se encontra o valor x, caso ele exista. Caso
contrário retornam o valor 0.
• A função procura_vec_bip apenas conta os elementos do vector e
chama a função p_vec_bip, que procura o elemento x no vector V
nos elementos com índices entre dois limites, inferior e superior
(no início estes limites são 1 e o número total de elementos):
function i = procura_vec_bip(x,V);
i = p_vec_bip(x,V,1,length(V));
endfunction.
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
23
Pesquisa Bipartida em Vectores Ordenados
• A função p_vec_bip verifica se x é o elemento “do meio” do
vector. Se não, procura nos índices ou inferiores ou superiores,
consoante x for menor ou maior que esse elemento.
• A pesquisa pára quando os limites superior e inferior forem os
mesmos, testando-se se x é o valor desse elemento.
function i = p_vec_bip(x,V,lo,up);
i = 0;
while up >= lo & i == 0
mid = floor((lo+up)/2);
if
x > V(mid)
lo = mid+1;
elseif x < V(mid)
up = mid-1
else
i = mid;
endif
endwhile
endfunction
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
24
Pesquisa Bipartida em Listas Ordenadas
• As funções procura_lista_bip e p_lista_bip, abaixo apresentadas,
são as correspondentes funções de acesso a uma lista L, ordenada
por um determinado campo (no exemplo, cod).
function i = procura_lista_bip(x,L);
i = p_lista_bip(x,L,1,length(L));
endfunction.
function i = p_lista_bip(x,L,lo,up);
i = 0;
while up >= lo & i == 0
mid = floor((lo+up)/2);
if
x > nth(L,mid).cod
lo = mid+1;
elseif x < nth(L,mid).cod
up = mid-1
else
i = mid;
endif
endwhile
endfunction
17 Novembro 2006
Algoritmos de Ordenação e Pesquisa
Aplicação a Listas de Registos
25