Algoritmos de Ordenação
Aplicação a Listas de Registos
Jorge Cruz
DI/FCT/UNL
Programação para as Ciências Experimentais
1º Semestre 2005/2006
25 Novembro 2005
Algoritmos de Ordenação
Aplicação a Listas de Registos
1
Ordenação 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 €;
• Em qualquer dos casos é importante saber ordenar os registos de
acordo com um determinado critério.
• Vamos então descrever dois algoritmos simples de ordenação
(insert sort e bubble sort) e depois mostrar como podem ser
aplicados na ordenação de registos (guardados em listas).
25 Novembro 2005
Algoritmos de Ordenação
Aplicação a Listas de Registos
2
Algoritmos de Ordenação: insert sort
• Suponhamos que queríamos ordenar o seguinte vector:
v0 = [12, 2, 9, 15, 10]
• Talvez a maneira mais intuitiva de o fazer seja através do algoritmo
insert sort:
– Começa-se por criar um vector v1 apenas com o primeiro elemento de v0:
•
v1 = [12]
– Acrescentam-se o restantes elementos, um a um, de modo a manter v1
sempre ordenado:
•
•
•
•
v1 = [2, 12]
v1 = [2, 9, 12]
v1 = [2, 9, 12, 15]
v1 = [2, 9, 10, 12, 15]
• O problema fundamental deste algoritmo é como é que se faz para
inserir um elemento numa lista ordenada.
25 Novembro 2005
Algoritmos de Ordenação
Aplicação a Listas de Registos
3
Algoritmos de Ordenação: insert sort
• Para inserir um elemento numa lista ordenada podemos percorrer a lista
do fim para o principio até se descobrir a posição que o elemento deve
ocupar na ordenação.
• Ao percorrer a lista podemos ir chegando uma posição à direita todos os
elementos maiores do que o novo elemento de modo a arranjar espaço
para ele:
function L = insert(L0,x)
L=L0; n=length(L);
for i=n:-1:1
if (L(i)<x) L(i+1)=x; return;
else
L(i+1)=L(i);
if (i==1) L(i)=x; return; endif
endif
endfor
endfunction
25 Novembro 2005
Algoritmos de Ordenação
Aplicação a Listas de Registos
4
Algoritmos de Ordenação: insert sort
• A seguinte função insert_sort começa por criar um vector inicial apenas
com o primeiro elemento da lista para ordenar e vai acrescentando todos
os outros elementos, um a um, recorrendo à função insert:
function L = insert_sort(L0)
n=length(L0);
L=[L0(1)];
for i=2:n
L=insert(L,L0(i));
endfor
endfunction
25 Novembro 2005
Algoritmos de Ordenação
Aplicação a Listas de Registos
5
Algoritmos de Ordenação: bubble sort
• Um outro algoritmo de ordenação, um pouco mais sofisticado, é o
bubble sort.
– Suponhamos que queremos ordenar o vector:
•
v0 = [12, 2, 9, 15, 10]
– Começa-se por percorrer o vector inicial (até ao penúltimo elemento) e trocar
dois elementos sempre estiverem na ordem errada:
•
v1 = [2, 12, 9, 15, 10]
[2, 9, 12, 15, 10]
[2, 9, 12, 15, 10]
[2, 9, 12, 10, 15]
– Agora, que garantidamente o último elemento do vector é o maior, repete-se
o processo (para os elementos ainda não garantidamente ordenados) :
•
25 Novembro 2005
v1 = [2, 9, 12, 10, 15]
[2, 9, 12, 10, 15]
[2, 9, 10, 12, 15]
• v1 = [2, 9, 10, 12, 15]
• v1 = [2, 9, 10, 12, 1
[2, 9, 10, 12, 15]
Algoritmos de Ordenação
Aplicação a Listas de Registos
6
Algoritmos de Ordenação: bubble sort
• O código Octave do algoritmo de ordenação bubble sort será então:
function L = bubble_sort(L0)
n=length(L0);
L=L0;
for k=n-1:-1:1
for i=1:k
if L(i+1)<L(i)
temp=L(i);
L(i)=L(i+1);
L(i+1)=temp;
endif;
endfor;
endfor;
endfunction
25 Novembro 2005
Algoritmos de Ordenação
Aplicação a Listas de Registos
7
Algoritmos de Ordenação e Listas
• Os algoritmos de ordenação como o bubble sort e o insert sort
podem ser utilizados para ordenar uma lista de registos se
considerarmos vectores de índices.
• 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.
• Se t é uma lista de registos, nth(t,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(t,i).cod
nth(t,i).nome
nth(t,i).venc
nth(t,i).data
25 Novembro 2005
Algoritmos de Ordenação
Aplicação a Listas de Registos
8
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 L:
function listagem_nome_venc(t,L)
n=length(L);
for i=1:n
printf("Nome: %-25s Vencimento: %7.2f \n“
,nth(t,L(i)).nome, nth(t,L(i)).venc);
endfor;
endfunction
• Assim, para obtermos uma listagem ordenada basta ordenar os
índices e chamar a função listagem_nome_venc.
25 Novembro 2005
Algoritmos de Ordenação
Aplicação a Listas de Registos
9
Algoritmos de Ordenação e Listas
• Para ordenar os índices pode-se usar um algoritmo de ordenação
tendo o cuidado de “redefinir” a comparação entre dois elementos
de acordo com o critério de ordenação que se pretende.
• Por exemplo, a função bubble_sort_list_cod usa o bubble sort para
ordenar os índices existentes no vector L0 por ordem crescente do
código do empregado:
25 Novembro 2005
function L = bubble_sort_list_cod(t,L0)
L=L0; n=length(L0);
for k=n-1:-1:1
for i=1:k
if nth(t,L(i+1)).cod < nth(t,L(i)).cod
temp=L(i);
L(i)=L(i+1);
L(i+1)=temp;
endif;
endfor;
endfor;
endfunction
Algoritmos de Ordenação
Aplicação a Listas de Registos
10
Algoritmos de Ordenação e Listas
• Para ordenar os índices pode-se usar um algoritmo de ordenação
tendo o cuidado de “redefinir” a comparação entre dois elementos
de acordo com o critério de ordenação que se pretende.
• A função bubble_sort_list_venc é idêntica à anterior mas ordena os
índices existentes no vector L0 por ordem crescente do vencimento
do empregado:
25 Novembro 2005
function L = bubble_sort_list_venc(t,L0)
L=L0; n=length(L0);
for k=n-1:-1:1
for i=1:k
if nth(t,L(i+1)).venc < nth(t,L(i)).venc
temp=L(i);
L(i)=L(i+1);
L(i+1)=temp;
endif;
endfor;
endfor;
endfunction
Algoritmos de Ordenação
Aplicação a Listas de Registos
11
Algoritmos de Ordenação e Listas
• Para ordenar os índices pode-se usar um algoritmo de ordenação
tendo o cuidado de “redefinir” a comparação entre dois elementos
de acordo com o critério de ordenação que se pretende.
• A função bubble_sort_list_data ordena os índices existentes no
vector L0 por ordem crescente de antiguidade do empregado, e usa
a função anterior para comparar duas datas:
25 Novembro 2005
function L = bubble_sort_list_data(t,L0)
L=L0; n=length(L0);
for k=n-1:-1:1
for i=1:k
if anterior(nth(t,L(i+1)).data,nth(t,L(i)).data)==1
temp=L(i);
L(i)=L(i+1);
L(i+1)=temp;
endif;
endfor;
endfor;
endfunction
Algoritmos de Ordenação
Aplicação a Listas de Registos
12
Algoritmos de Ordenação e Listas
• Para ordenar os índices pode-se usar um algoritmo de ordenação
tendo o cuidado de “redefinir” a comparação entre dois elementos
de acordo com o critério de ordenação que se pretende.
• A função bubble_sort_list_nome ordena os índices existentes no
vector L0 por ordem alfabética dos nomes dos empregados, e usa a
função my_str_norm_before para comparar dois nomes:
function L = bubble_sort_list_nome(t,L0)
L=L0; n=length(L0);
for k=n-1:-1:1
for i=1:k
if my_str_norm_before (nth(t,L(i+1)).nome,nth(t,L(i)).nome)==1
temp=L(i);
L(i)=L(i+1);
L(i+1)=temp;
endif;
endfor;
endfor;
endfunction
25 Novembro 2005
Algoritmos de Ordenação
Aplicação a Listas de Registos
13
Algoritmos de Ordenação e Listas
• Se além da ordenação estivermos também interessados em seleccionar
apenas alguns registos, podemos previamente construir um vector apenas
com os índices dos registos seleccionados.
• Por exemplo, a função select_venc cria um vector apenas com os índices
de L0 cujos empregados tenham um vencimento superior a 1000 €:
function L = select_venc(t,L0)
L=[]; j=0; n=length(L0);
for i = 1:n
if nth(t,L0(i)).venc > 1000
j=j+1;
L(j)=L0(i);
endif;
endfor;
endfunction
• Assim para obter apenas estes índices ordenados pelo nome do
empregado bastaria:
L=select_venc(t,L0); L=bubble_sort_list_nome(t,L)
25 Novembro 2005
Algoritmos de Ordenação
Aplicação a Listas de Registos
14
Algoritmos de Ordenação e Listas
• Podemos agora dar resposta a cada uma das perguntas anteriores.
• Primeiro lê-se o ficheiro de texto para uma tabela:
[t,n] = ler_tabela("empresa_aux_var.txt");
• Para apresentar uma listagem dos empregados por ordem alfabética de
nomes ou por antiguidade, teríamos que considerar todos os índices,
ordená-los de acordo com o critério e apresentar os campos que
queremos visualizar dos respectivos registos:
L=[1:n];
L1=bubble_sort_list_nome(t,L);listagem_nome_venc(t,L1);
L2=bubble_sort_list_data(t,L);listagem_nome_venc(t,L2);
• Se além disto estivermos apenas interessados nos empregados com um
salário superior a 1000 €, temos que previamente seleccionar apenas os
índices dos registos que satisfazem o critério:
L=[1:n]; L=select_venc(t,L);
L1=bubble_sort_list_nome(t,L);listagem_nome_venc(t,L1);
L2=bubble_sort_list_data(t,L);listagem_nome_venc(t,L2);
25 Novembro 2005
Algoritmos de Ordenação
Aplicação a Listas de Registos
15