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 nlog2 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