11 Maio 2007Listas e Vectores: Pesquisa e Ordenação1 Pedro Barahona DI/FCT/UNL Introdução aos Computadores e à Programação 2º Semestre 2006/2007

11 Maio 2007 Listas e Vectores: Pesquisa e Ordenação 1

Listas e Vectores: Pesquisa e Ordenação

Pedro BarahonaDI/FCT/UNL

Introdução aos Computadores e à Programação2º Semestre 2006/2007


Listas - Criação

• Uma lista é uma sequência de dados do mesmo tipo, simples ou complexo, para

as quais estão definidas (em Octave) as operações básicas ed criação, adição,

acesso e alteração.• Criação: list(elem_1, elem_2, ..., elem_k)

Cria uma lista, com os elementos de 1 a k.

• Nota 1: A lista pode ser vazia !

• Nota 2: Geralmente, pretende-se que todos os elementos tenham o mesmo tipo.

No entanto, uma lista pode conter elementos de qualquer tipo, ou mesmo ser

heterogénea, como indicado

>> emps = list()emps = ()

emp.cod = 25, emp.venc = 1025.7;emps = list(1, ‘estaranha’, emp)


Listas – Adição e Acesso

• A uma lista podem ser adicionados, no seu final, mais elementos, com a instrução

• Adição: append(nome_lista, elem_1, elem_2, ..., elem_k)

Exemplo: A lista nums é inicialmente criada com os números 1, 2 e 3, sendo

posteriormente acrescentados os números 4 e 5.

• O acesso ao k-ésimo elemento de uma lista pode ser feito através da instrução

• Acesso: nth(nome_lista, k)

Exemplo: Obter a diferença entre o 3º e o 5º elemento da lista nums, criada

anteriormente.

dif = nth(nums,3) – nth(nums,5)

nums = list(1,2,3);nums = append(nums, 4, 5)


Listas – Alteração

• A alteração de elementos de uma lista pode ser feita por alteração directa dos

seus elementos identificados pelos seus índices.

• Exemplo 1: Substituir na lista nums, com os números de 0 a 6, os seu 6º

elemento (inicialmente com o valor 5) pelo valor 7 .

Neste caso, a lista nums que se obtem, contem os números

(0,1,2,3,4,7,6).

• Exemplo 2: Substituir na lista nums, anterior, os seus primeiros 2 elementos

pelos números 9 e 8 .

passando, a lista nums, a conter os números

(9,8,2,3,4,7,6).

nums(6) = 7

nums(1:2) = list(9,8)


Listas – Substituição

• Em alguns casos, nomeadamente em operações de ordenação, interessa trocar a

posição de dois elementos de uma lista.

• Esta operação pode ser implementada por uma função, troca, que inclui

operações de acesso e alteração de uma lista. Mais especificamente,

• Função troca:

A troca dos i-ésimo e j-ésimo elementos de uma lista pode ser feita com a função

abaixo.

.

function lista = troca(lista, i, j);

x = nth(lista_in,i); % guarda o elemento 1

lista(i) = nth(lista,j); % substitui i por j

lista(j) = x; % repõe o elemento j em i

endfunction


Leitura de Listas

• Para ilustrar o conceito de lista, vamos considerar o anterior ficheiro com

informação sobre empregados e criar uma lista com essa informação.

• Nota: Assume-se que no ficheiro (‘empresa_aux.txt’) os campos são separados

por tabs horizontais e que os espaçoes dentro dos nomes já forma fobstituidos por

espaços especiais (non-break spaces).

• Como anteriormente, a cada linha do ficheiro corresponde uma estrutura, emp,

com os campos cod, nome, venc e data. Por exemplo,

cod nome venc data610 Paulo Fernandes Lopes 2341.36 15/04/1996

cod nome vencimento data

610 Paul o Fer nandes Lopes 2341. 36 15/ 04/ 1996825 Pedr o Vi ei r a 989. 24 25/ 06/ 1999316 Mar t a Cost a Mar t i ns 1389. 17 05/ 01/ 199234 Rui Vasco Per ei r a 5310. 32 15/ 04/ 1996723 J or ge Bar at a 767. 26 03/ 09/ 2002


Listas – Substituição

• A leitura dos vários campos de uma estrutura pode ser feita como anteriormente.

Um programa, que cria uma lista, lista_emps, com a informação sobre os

empregados do ficheiro “empresa_aux.txt”, é o seguinte:

[f_aux, msg] = fopen("empresa_aux.txt", "r");

lista_emps = list(); n = 0;

[emp.cod,emp.nome,emp.venc,emp.data, count] =

fscanf(f_aux,"%i%s%f%s","C");

while !feof(f_aux)

n = n+1;

lista_emps = append(lista_emps , emp);

[emp.cod,emp.nome,emp.venc,emp.data, count] =

fscanf(f_aux,"%i%s%f%s","C");

endwhile;

fclose(f_aux);


Estruturas e Listas em Funções

• Estruturas e listas podem ser retornadas como resultado de uma função. Por

exemplo, a função abaixo retorna a lista anterior e o número dos seus elementos,

(se chamada com o ficheiro de nome “empresa_aux.txt”)

function [lista_emps, n] = ler_lista_emps(fname); [f_aux, msg] = fopen(fname, "r"); lista_emps = list(); n = 0; [emp.cod,emp.nome,emp.venc,emp.data, count] = fscanf(f_aux,"%i%s%f%s","C"); while !feof(f_aux) n = n+1; lista_emps = append(lista_emps, emp); [emp.cod,emp.nome,emp.venc,emp.data, count] = fscanf(f_aux,"%i%s%f%s","C"); endwhile; fclose(f_aux);endfunction;


Processamento de Listas

• A partir deste momento, todo o processamento da informação sobre os empregados

pode ser feito sem leitura do ficheiro, mas apenas por acesso à lista lista_emps.

• Vamos ilustrar esta situação em 3 problemas:

– Cálculo da média dos vencimentos dos empregados.

– Selecção dos empregados com o nome Paulo

– Ordenação dos empregados por ordem crescente de antiguidade


Cálculo de Médias em Listas

• Uma vez lida a informação dos empregados para a lista lista_emps, ela pode ser

acedida directamente e passada como parâmetros de entrada em funções.

• Assim o cálculo do total e da média dos vencimentos é feito pela chamada da função

vencimentos, definida abaixo e chamada com o parâmetro lista_emps. Por exemplo,

na instrução

[m,t] = vencimentos(lista_emps)

function [media, total] = vencimentos(lista); total = 0; n = length(lista) for i = 1:n total = total + nth(lista,i).venc; endfor; media = total / n; % printf("o total de vencimentos é %7.2f \n“, total); % printf(“ e a sua média é %7.2f \n", total/n);endfunction;


Selecção de Elementos em Listas

• Igualmente se podem seleccionar os elementos de uma lista que satisfazem um

certo critério.

• No exemplo abaixo os empregados cujo vencimento é superior a um dado valor

são seleccionados e organizados numa lista, emps, que é o resultado da função

vencimento_maior.

• Estes empregados podem ser obtidos pela chamada da função

emps_mais_de_1000 = vencimento_maior(lista_emps, 1000)

function emps = vencimento_maior(lista, valor); emps = list(); for i = 1:length(lista) emp = nth(lista,i); if emp.venc > valor emps = append(emps, emp); endif; endfor;endfunction;


Selecção de Elementos em Listas

• O critério utilizado para seleccionar os elementos de uma lista é arbitrário, podendo

ser naturalmente outro.

• No exemplo abaixo são seleccionados, e retornados como resultado da função

emps_com_nome, os empregados que têm uma dada palavra no seu nome. Por

exemplo, os empregados cujo nome inclui a palavra “Paulo” são retornados pela

chamada da função

paulos = emps_com_nome(lista_emps, ‘Paulo’)

function emps = emps_com_nome(lista, nome); emps = list(); for i = 1:length(lista) emp = nth(lista,i); if index(toupper(emp.nome),toupper(nome))> 0 emps = append(emps, emp); endif; endfor;endfunction;


Ordenação de Listas e Vectores

• As estruturas de dados lineares (nomeadamente listas e vectores) 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.


Ordenação de Listas e Vectores

• Analisemos primeiro a ordenação de vectores (ou listas), 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

nlog2n acessos), o que apresentamos (bubblesort) é mais simples de descrever

(e implementar?).


Ordenação por Bubble Sort

• A ideia do algoritmo é comparar dois elementos consecutivos do vector, e trocá-

los se tiverem na ordem “errada”. A comparação é feita entre os n-1 pares do

vector, por uma determinada ordem, por exemplo (1,2), (2,3), ..., (n-1,n).

• No final deste processo, o último elemento já está bem posicionado. Sem qualquer

optimização, pode fazer-se outro varrimento, em que ficará bem colocado o

penúltimo elemento.

• Desta forma, e no pior caso, bastará fazer n-1 varrimentos para garantir que o

vector ficou ordenado.

• No total, e para o pior caso, são feitas (n-1)comparações em cada um dos (n-1)

varrimentos, em que algumas comparações resultam em trocas.

• Desta forma serão feitas (n-1)2 comparações, pelo que a complexidade será

quadrática no número de elementos do vector, isto é lim (n-1)2 n2 (para valores

de n “grandes”).


Ordenação por Bubble Sort

• Podemos observar o comportamento deste algoritmo no (pior) caso abaixo, com

um vector de 4 elementos, em ordem decrescente que se pretende ordenar de

forma crescente!

9 7 4 1 compara 9 com 7 troca



7 4 1 9

1ª iteração

o 4º valor está arrumado!


4 7 1 9 compara 7 com 1 troca4 1 7 9 compara 7 com 94 1 7 9

2ª iteração


=

4 1 7 9 compara 4 com 1 troca1 4 7 9 compara 4 com 74 1 7 9 compara 7 com 94 1 7 9

3ª iteração


=


Bubble Sort (Não Optimizado)

• A função abaixo implementa o algoritmo de bubble sort com dois ciclos para

encadeados. No final destes ciclos o vector está ordenado.

function V = bubble_1(V); % bubble sort n = length(V); for k = 1:n-1 % n-1 varrimentos for i = 1:n-1 if V(i) > V(i+1) x=V(i); V(i)=V(i+1); %troca V(i) com V(i+1) V(i+1)=x; endif; endfor; endfor;endfunction;


Optimização do Bubble Sort

• O algoritmo pode ser optimizado de duas formas complementares.

Diminuição dos ciclos

• Por um lado, em cada iteração o último valor a ser considerado vai decrescendo de

n para n-1, para n-2, ....

• Desta forma o ciclo interno pode ser parametrizado por um valor k que vai

decrescendo em cada ciclo externo.

Interrupção dos varrimentos

• Se um varrimento termina sem trocas, o vector já está ordenado, e não é necessário

fazer mais varrimentos.

• Assim há que identificar numa variável, troca, se houve trocas durante um

varrimento. Caso contrário, terminar imediatamente a ordenação.


Bubble Sort (Optimizado)

• As duas optimizações descritas estão implementadas no algoritmo abaixo. Se ao

fim de um varrimento não tiver havido trocas, o vector já está ordenado e a

função termina sem iniciar mais varrimentos!.

function V = bubble_2(V); % bubble sort n = length(V); for k = n-1:-1:1 % k = n-1, n-2, n-3, ... troca = 0; for i = 1:k if V(i) > V(i+1) troca = 1; x=V(i); V(i)=V(i+1); %troca V(i) com V(i+1) V(i+1)=x; endif; endfor; if troca == 0 return endif; endfor;endfunction;


Bubble Sort (Optimizado)

• Como a unica operação a fazer sobre vectores é trocar dois elementos, o mesmo

algoritmos pode servir para ordenar listas de estruturas. Por exemplo, a função

abaixo ordena a lista por ordem crescente do campo venc.

function Lista = bubble_3(Lista); % bubble sort n = length(Lista)-1; for k = n-1:-1:1 troca = FALSE; for i = 1:k if nth(lista,i).venc > nth(lista,i+1).venc troca = TRUE; %troca Lista(i) com Lista(i+1) troca(Lista,i, i+1); endif; endfor; if !troca then return; endfor:; endfunction;


Pesquisa Linear em Vectores

• Consideremos um vector V, numérico e 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 (primeiro) índice i onde se encontra x (ou seja, V(i) = x), ou

retorna 0 se x não estiver incluído no vector

• A função pode ser facilmente adaptada para uma lista e um campo substituindo-se

a comparação para

if nth(Lista,i).campo == x

function i = procura_linear_1(x,V); for i = 1:length(V); if V(i) == x return; endif endfor; i = 0;endfunction;


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, portanto, não

estar no vector 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).


Pesquisa Linear em Vectores (Optimizada)

• A pesquisa pode ser mais rápida se o vector estiver 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_linear_2(x,V); for i = 1:length(V); if V(i) == x return; elseif V(i) > x i = 0; return; endif endfor;endfunction;


Pesquisa Linear em Vectores (Optimizada)

• A complexidade, em termos do número de acessos ao vector, pode ser analisado

de uma forma semelhante à anterior :

– Se x pertencer ao vector V, o número de leituras é variável, sendo em média

lidos n/2 valores.

– Se x não pertencer ao vector V, esse facto será descoberto mais cedo ou

mais tarde consoante o valor de x (e os valores em V). Em média, podemos

assumir igualmente 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).


Pesquisa Bipartida

• Se o vector V estiver ordenado, podemos sempre determinar se x, a existir no

vector V, 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

• O algoritmo pode pois considerar um intervalo de pesquisa cada vez menor, como

exemplificado de seguida.

x > V(i)x < V(i)

i


Pesquisa Bipartida

• 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 entre 1 e 31 = 16 = (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 = (1+15)/2





Pesquisa Bipartida

• No segundo caso, podemos comparar x com o número intermédio 12 = 9+15/2.




• No segundo caso, podemos comparar x com o número intermédio 14 = (13+15)/2.




• Nestes últimos casos, são feitas comparações com um só elemento, V(13) ou

V(15), que garantem a verificação sobre se x está ou não no vector V .


Pesquisa Bipartida• 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)).

• Assim para vectores (ou listas) com 109 valores, uma pesquisa requer em média

log2(109) ≈ 29.9, e não 500*106 acessos.

• Se cada acesso demorar 1 s, a pesquisa bipartida demora cerac de 30 s, em

comparação com 500 seg = 10 min!


Pesquisa Bipartida• Dadas as vantagens, vale a pena utilizar a pesquisa bipartida. Eis uma possível

implementação, recursiva, em que se pretende determinar se o número x está no

vector V, entre as posições i e j.

• Naturalmente, a função será chamada como

k = procura_bipartida(x,V,1,length(V)).

function k = procura_bipartida(x,V,i,j); if i > j k = 0 % x não pertence a V else m = round((i+j)/2) if V(m) == x k = m; return; elseif V(m) < x i = m+1; % o j mantem-se else j = m-1; % o i mantem-se endif; k = procura_bipartida(x,V,i,j); endifendfunction;

Documents

11 Maio 2007Listas e Vectores: Pesquisa e Ordenação1 Pedro Barahona DI/FCT/UNL Introdução aos Computadores e à Programação 2º Semestre 2006/2007