ESTRUTURA DE DADOS
Métodos de Ordenação Externa
Ordenação Externa
• Ordenação: re-arranjar um conjunto de registros
em ordem ascendente ou descendente
• Os algoritmos sempre trabalham sobre os
registros de um arquivo, sendo que apenas parte
deste registro (a chave) é usada na ordenação
• Ordenação externa ou ordenação de arquivos:
– O número de registros a serem ordenados usa mais
memória interna do que a disponível no computador
• Os métodos de ordenação externa são muito
diferentes dos de ordenação interna
Ordenação Interna x Externa
• Na ordenação externa deve-se levar em conta
que os dados estão armazenados em unidades
de memória externa, muito mais lentas
• Memórias externas (discos, fitas, etc) armazenam
os dados como um arranjo seqüencial: apenas 1
registro pode ser acessado por vez
– Compare com o acesso aos elementos de uma estrutura
do tipo vetor na memória...
Problemas na Ordenação Externa
1. Custo de acesso dos itens é muito superior ao
custo de processamento na memória interna:
•
Transferência de dados entre memória externa e interna é
a parte principal do custo
2. Acesso aos dados:
•
•
Fita só permite acesso aos itens de forma seqüencial
Discos podem acessar itens diretamente, mas com custo
maior do que seqüencialmente, inviabilizando o acesso
direto
3. Métodos dependem da tecnologia:
•
Como boa parte do custo para a ordenação é dependente
do tempo de acesso à memória externa, os métodos
podem se tornar dependentes de parâmetros
tecnológicos
Ordenação Externa Eficiente
•
•
Buscar a minimização do número de vezes que
cada item é transferido entre memória interna e
externa
Método mais importante: FUSÃO (“merge”)
– Fundir: combinar duas ou mais seqüências ordenadas
para formar uma única seqüência ordenada através da
aplicação de repetidas seleções entre os componentes
acessíveis em cada ocasião
•
A operação de fusão é muito mais simples que a
de ordenação e é empregada como uma operação
auxiliar no processo mais complexo de ordenação
externa
Passos a seguir na Ordenação por
Fusão ou Intercalação
1. Realizar uma leitura do arquivo e quebrar o
arquivo em blocos de tamanho da memória
interna disponível; ordenar em seguida cada bloco
na memória interna.
2. Fundir/intercalar os blocos ordenados após várias
passadas sobre o arquivo; a cada passada blocos
ordenados maiores são criados até que todo o
arquivo esteja ordenado
• Eficiência:
– Redução do número de leituras do arquivo
– Redução do número de vezes em que um item é escrito
ou lido na memória auxiliar
Fusão Direta [Wirth]
1. Dividir a seqüência a em duas metades, chamadas
bec
2. Fundir b e c por meio da combinação de elementos
isolados para formarem pares ordenados
3. Denominar a a seqüência assim obtida e repetir os
passos 1 e 2, desta vez efetuando a fusão de pares
ordenados em quádruplas ordenadas
4. Iterar os passos anteriores, executando a fusão das
quádruplas em óctuplas, e assim prosseguir
duplicando o comprimento das subseqüências
envolvidas no processo de fusão a cada vez, até
que toda a seqüência esteja ordenada
Ordenação por Fusão (Merge)
•
Princípio:
1. Dividir o vetor (arquivo) em duas partes
2. Intercalar os vetores ordenados de maneira independente
•
Vantagens:
1. Pior caso: O(n log n)
2. Exige apenas acesso seqüencial aos dados
3. Trabalha bem com dados em lista encadeada
•
Desvantagens:
1. Exige espaço extra: O(n)
Exemplo (Wirth, Cap 2)
Seja a seqüência inicial:
44 55 12 42 94 18 06 67
No passo 1, o particionamento produz as seqüências
44 55 12 42
94 18 06 67
A fusão dos componentes isolados (que são seqüências ordenadas
de comprimento 1) em pares ordenados resulta em:
44 94 18 55 06 12 42 67
Divindo-se novamente a seqüência ao meio e efetuando-se a fusão:
06 12 44 94 18 42 55 67
Uma outra divisão seguida de fusão produz finalmente o resultado
esperado:
06 12 18 42 44 55 67 94
Um pouco mais sobre a Fusão Direta
• Cada operação que trata de uma só vez todo o
conjunto de dados é denominada fase
• O menor subprocesso que implementa o processo
de ordenação propriamente dito através de repetições sucessivas é chamado passo
• O exemplo anterior produz uma seqüência ordenada em 3 passos, cada qual consistindo de 1 fase de
partição e de 1 fase de fusão
• Note que para que a ordenação seja efetuada, são
necessárias 3 fitas (séries de dados)
Melhorando a Fusão Direta
• O método pode ser melhorado pela combinação
das fases de particionamento e fusão:
– Ao invés de se efetuar uma fusão para produzir uma
seqüência única, o resultado do processo de fusão é
imediatamente redistribuído em duas fitas as quais vão
se tornar as fontes de dados que alimentarão o próximo
passo...
• Este método é chamado Fusão de Fase Única ou
Fusão Balanceada
– O método tem desempenho superior ao anterior, mas o
preço a pagar é o uso de uma quarta fita...
Exemplo de Fusão Balanceada (Ziviani)
• Seja um arquivo composto pelos registros com
as seguintes chaves armazenado numa fita:
ASORTINGANDMERGINGEXAMPLE
• Os registros devem ser ordenados de acordo
com as chaves e re-inseridos na fita
• Os registros são lidos um após outro (como
numa fita magnética, por ex)
• Suponha ainda que a memória do computador só
tem espaço para 3 registros, e o número de
unidades de fita é 6.
Primeira Parte
•
Na 1a. Parte, o arquivo é lido de 3 em 3 registros
– Cada bloco de 3 registros é ordenado e escrito em uma
das fitas de saída
1. Para o exemplo são lidos os registros A S O e escrito o
bloco A O S na fita 1
2. Em seguida, são lidos os registros R T I e escrito o bloco I
R T na fita 2, e assim sucessivamente...
– 3 fitas são usadas em uma fusão de 3 caminhos...
•
Assim, a repetição dos passos 1 e 2 produz:
fita 1:
AOS
DMN
AEX
fita 2:
I RT
EGR
LMP
fita 3:
AGN
GIN
E
Segunda Parte
•
Na 2a. Parte, os blocos devem ser fusionados
1. O 1o. registro de cada uma das três fitas é lido para a
memória interna, ocupando-a totalmente
2. O registro contendo a menor chave é retirado e o próximo
registro da mesma fita é lido para a memória interna
3. O processo é repetido até a leitura de todos os registros
Segunda Parte
•
•
•
•
Quando o terceiro registro de uma fita é lido, aquela fita fica
“inativa” até que todas as outras fitas sejam lidas e escritas na
fita de saída, formando um bloco com 9 registros ordenados
Em seguida, o 2o. bloco de 3 registros de cada fita é lido para
formar outro bloco ordenado de 9 registros, que é escrito em
outra fita
Por fim, 3 novos blocos ordenados são obtidos:
fita 4:
AAG I N O R S T
fita 5:
DEGGIMNNR
fita 6:
AEELMPX
Após mais uma fusão das fitas 4, 5 e 6 para as fitas 1, 2 e 3
finaliza a ordenação
MergeSort Externo
• Executa em 2 etapas
• Etapa 1 – Sort
– Quebra-se o conjunto em partições
• tamanho da partição depende da disponibilidade de buffers em
memória (nbuf = no de buffers disponíveis)
• gera um arquivo temporário ordenado para cada partição
• Etapa 2 – Merge de “n” iterações
– ordena um conjunto de temporários a cada iteração
• gera um novo temporário resultante da ordenação
• ordenação termina quando existir somente um temporário que
mantém a relação inteira ordenada
Algoritmo do Mergesort
Mergesort(A,Esq,Dir);
if Esq < Dir then
m:= |(Esq+Dir) div 2|
Mergesort(A,Esq,m);
Mergesort(A,m+1,Dir);
Merge(A,Esq,m+1,Dir);
Nbuf =
1
Exemplo:
A = [O R D E N A R A]
[O] [R]
[D] [E]
[N] [A]
[R] [A]
[O R]
[D E]
[A N]
[A R]
[D E O R]
[A A N R]
[A A D E N O R R]
procedure Mergesort(var A:vetor; Esq,Dir: integer);
var i, j, k, m: integer;
begin
if Esq < Dir then begin
m:= (Esq+Dir) div 2;
Mergesort(A,Esq,m);
Mergesort(A,m+1,Dir);
for i:=m donwto Esq do
A[i]:=B[j];
for j:=m+1 to Dir do
B[Dir+m+1-j]:=A[j];
for k:=Esq to Dir do begin
if B[i] < B[j] then begin
A[k]:=B[i];
i:=i+1;
end
else begin
A[k]:=B[j];
j:=j-1;
end
end;
Ordenação por Mergesort
1
2
3
4
5
6
7
8
Vetor A
O
R
D
E
N
A
R
A
i=1
O
R
D
E
O
R
A
N
A
R
i=2
i=3
D
E
i=4
i=5
i=6
i=7
A
A
D
E
A
A
N
R
N
O
R
R
Outros métodos
• Capítulo 2 do Wirth traz todos os métodos, com
análises aprofundadas.
• Capítulo 4 de Ziviani traz alguns métodos com
boas explicações
Referências do Curso
• Transparências disponibilizadas pelo Prof.
Ziviani, a partir do Livro Projeto de Algoritmos
com Implementação em Pascal e C, M. A. da Silva
Bigonha e Nívio Ziviani, Campus
• Algoritmos e Estruturas de Dados, N. Wirth,
Prentice-Hall