Upload
estela-fartaria-vilarinho
View
243
Download
18
Embed Size (px)
Citation preview
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 custo2. 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 b e c
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 partes2. Intercalar os vetores ordenados de maneira independente
• Vantagens:1. Pior caso: O(n log n)2. Exige apenas acesso seqüencial aos dados3. 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 ordena-da 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:
A S O R T I N G A N D M E R G I N G E X A M P L EA S O R T I N G A N D M E R G I N G E X A M P L E
• 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ída1. Para o exemplo são lidos os registros A S O e escrito o
bloco A O S na fita 12. 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: A A G I N O R S T
fita 5: D E G G I M N N R
fita 6: A E E L M P X
• 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 = 1Exemplo: 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
AO R D E N62 3 4 51
i = 1
D Ei = 2
D E Oi = 3
NAi = 4
i = 5
Vetor A AR87
O R
R
RA
i = 6 RNAA
OA A D E N RRi = 7
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