Slide - Ordenação Por Fusão - Bubblesort e Sharkesort - 2023-2

1 Introdução à Computação II – 5954006 Introdução à Computação II 5954006 5. Algoritmos de Ordenação Prof. Renato Tinós Local: Depto. de Computação e Matemática (FFCLRP/USP) 2 Introdução à Computação II – 5954006 Principais Tópicos 5.1. Ordenação por Inserção 5.2. Ordenação por Seleção 5.3. Método da Bolha 5.4. Ordenação por Fusão 5.4.1. Operação de Fusão 5.4.2. Ordenação por Fusão Direta 5.5. Heapsort 5.6. Quicksort 5.7. Considerações sobre o Problema de Ordenação 5.8. Ordenação em Tempo Linear 3 Introdução à Computação II – 5954006 5.4. Ordenação por Fusão • Veremos aqui a ordenação por fusão para vetores na memória principal ▪ Isso é uma restrição se comparada com as possibilidades oferecidas pela estrutura de vetor ▪ Alguns métodos de ordenação (como ordenação por fusão) podem ser facilmente adaptados para dados descritos na forma de arquivos sequenciais ➢cuja característica é que, a cada instante, é possível o acesso (direto) a um e somente um dos seus componentes 4 Introdução à Computação II – 5954006 • Operação de fusão ▪ Operação essencial para a implementação da ordenação por fusão ➢é mais simples que o processo de ordenação ▪ combina duas ou mais sequências ordenadas para formar uma única sequência ordenada ▪ utiliza repetidas seleções entre os elementos acessíveis a cada momento 5.4.1. Operação de Fusão 5 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 a i 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 c k N=5 M=8 N+M=13 Se a[i] < b[j] então a[i] deve ser inserido em c[k] senão b[j] deve ser inserido em c[k] Exemplo 5.4.1. 5.4.1. Operação de Fusão 6 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 a i 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 c k N=5 M=8 N+M=13 Se a[i] < b[j] então a[i] deve ser inserido em c[k] senão b[j] deve ser inserido em c[k] Exemplo 5.4.1. 5.4.1. Operação de Fusão 7 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 a i 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 c k N=5 M=8 N+M=13 Se a[i] < b[j] então a[i] deve ser inserido em c[k] senão b[j] deve ser inserido em c[k] Exemplo 5.4.1. 5.4.1. Operação de Fusão 8 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 a i 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 c k N=5 M=8 N+M=13 Se a[i] < b[j] então a[i] deve ser inserido em c[k] senão b[j] deve ser inserido em c[k] Exemplo 5.4.1. 5.4.1. Operação de Fusão 9 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 a i 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 c k N=5 M=8 N+M=13 Se a[i] < b[j] então a[i] deve ser inserido em c[k] senão b[j] deve ser inserido em c[k] Exemplo 5.4.1. 5.4.1. Operação de Fusão 10 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 a i 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 c k N=5 M=8 N+M=13 Se a[i] < b[j] então a[i] deve ser inserido em c[k] senão b[j] deve ser inserido em c[k] Exemplo 5.4.1. 5.4.1. Operação de Fusão 11 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 a i 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 c k N=5 M=8 N+M=13 Se a[i] < b[j] então a[i] deve ser inserido em c[k] senão b[j] deve ser inserido em c[k] Exemplo 5.4.1. 5.4.1. Operação de Fusão 12 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 a i 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 8 c k N=5 M=8 N+M=13 Se a[i] < b[j] então a[i] deve ser inserido em c[k] senão b[j] deve ser inserido em c[k] Exemplo 5.4.1. 5.4.1. Operação de Fusão 13 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 a i 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 8 9 c k N=5 M=8 N+M=13 Se a[i] < b[j] então a[i] deve ser inserido em c[k] senão b[j] deve ser inserido em c[k] Exemplo 5.4.1. 5.4.1. Operação de Fusão 14 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 10 a i=6 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 8 9 c k N=5 M=8 N+M=13 Um dos vetores (a ou b) pode ter um número menor de elementos do que o outro vetor, ou seja, N ≠ M. Nesse caso, ao terminar um dos vetores, os demais elementos do outro vetor deverão ser copiados para o vetor destino c Exemplo 5.4.1. 5.4.1. Operação de Fusão 15 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 10 11 a i=6 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 8 9 c k N=5 M=8 N+M=13 Um dos vetores (a ou b) pode ter um número menor de elementos do que o outro vetor, ou seja, N ≠ M. Nesse caso, ao terminar um dos vetores, os demais elementos do outro vetor deverão ser copiados para o vetor destino c Exemplo 5.4.1. 5.4.1. Operação de Fusão 16 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 10 11 13 a i=6 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 8 9 c k N=5 M=8 N+M=13 Um dos vetores (a ou b) pode ter um número menor de elementos do que o outro vetor, ou seja, N ≠ M. Nesse caso, ao terminar um dos vetores, os demais elementos do outro vetor deverão ser copiados para o vetor destino c Exemplo 5.4.1. 5.4.1. Operação de Fusão 17 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 10 11 13 a i=6 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 8 9 c k 15 N=5 M=8 N+M=13 Um dos vetores (a ou b) pode ter um número menor de elementos do que o outro vetor, ou seja, N ≠ M. Nesse caso, ao terminar um dos vetores, os demais elementos do outro vetor deverão ser copiados para o vetor destino c Exemplo 5.4.1. 5.4.1. Operação de Fusão 18 Introdução à Computação II – 5954006 1 2 3 4 5 2 4 6 8 10 10 11 13 a i=6 1 2 3 4 5 6 7 8 3 5 7 9 11 13 15 17 b j=9 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 8 9 c k 15 17 N=5 M=8 N+M=13 Um dos vetores (a ou b) pode ter um número menor de elementos do que o outro vetor, ou seja, N ≠ M. Nesse caso, ao terminar um dos vetores, os demais elementos do outro vetor deverão ser copiados para o vetor destino c Exemplo 5.4.1. 5.4.1. Operação de Fusão 19 Introdução à Computação II – 5954006 Exercício 5.4.1. Desenvolva um algoritmo para realizar a operação de fusão de dois vetores descrita no exemplo anterior. 5.4.1. Operação de Fusão 20 Introdução à Computação II – 5954006 Ao término, k=N+M que é o número de elementos do vetor c enquanto (i ≤ N ) k  k + 1 c[k]  a[i] i  i + 1 } enquanto (j ≤ M ) k  k + 1 c[k]  b[j]; j  j + 1 } ... ... i  1 j  1 k  0 enquanto (i ≤ N ) e ( j ≤ M) k  k + 1 se ( a[i] < b[j] ) c[k]  a[i] i  i + 1 senão c[k]  b[j] j  j + 1 fim se fim enquanto 5.4.1. Operação de Fusão 21 Introdução à Computação II – 5954006 • Este mesmo algoritmo pode ser facilmente alterado para a situação na qual os elementos a serem intercalados encontram-se em um mesmo vetor • Nesse caso, deseja-se intercalar as seqüências ordenadas a[L],..., a[h] e a[h+1],..., a[R] para obter o vetor c[L], ..., c[R] , também ordenado 5.4.1. Operação de Fusão 22 Introdução à Computação II – 5954006 Algoritmo merge( a[ ], L , h , R , c[ ] ) pré:(a[L],...,a[h]) e (a[h+1],...,a[R]) são duas seqüências ordenadas com chaves a[L]≤ ... ≤ a[h] e a[h+1] ≤ ... ≤ a[R] Por exemplo: pós:(a[L],...,a[h]) e (a[h+1],...,a[R]) são intercaladas para obter a seqüência (c[L],...,c[R]) tal que c[L]≤ ... ≤ c[R] Por exemplo: 5 7 13 2 4 6 8 10 12 1 3 a R 15 17 h h+1 L 10 12 13 1 2 3 4 5 6 7 8 c R 15 17 L 5.4.1. Operação de Fusão 23 Introdução à Computação II – 5954006 Exercício 5.4.2. Desenvolva um algoritmo para realizar a operação de fusão em um único vetor descrita no exemplo anterior. 5.4.1. Operação de Fusão 24 Introdução à Computação II – 5954006 enquanto ( i ≤ h e j ≤ R ) k  k + 1 se ( a[ i ] < a[ j ] ) c[ k ]  a[ i ] i  i + 1 senão c[k]  a[j] j  j + 1 fim se fim enquanto enquanto ( i ≤ h ) k  k + 1 c[ k ]  a[ i ] i  i + 1 fim enquanto enquanto ( j ≤ R ) k  k + 1 c[ k ]  a[ j ] j  j + 1 fim enquanto Algoritmo merge(a[ ] ,L ,h ,R ,c[ ] ) pré:(a[L],...,a[h]) e (a[h+1],...,a[R]) são duas seqüências ordenadas com chaves a[L]≤ ... ≤ a[h] e a[h+1] ≤ ... ≤ a[R] pós:(a[L],...,a[h]) e (a[h+1],...,a[R]) são intercaladas para obter a seqüência (c[L],...,c[R]) tal que c[L]≤ ... ≤ c[R] i  L j  h + 1 k  L - 1 5.4.1. Operação de Fusão 25 Introdução à Computação II – 5954006 • Análise ▪ Em cada iteração dos laços enquanto, k incrementa de 1 em 1 ➢No total, dentro dos laços, k vai de L até R e o total de incrementos é 𝑓(𝑅, 𝐿) = ෍ 𝑘=𝐿 𝑅 1 = 𝑅 − 𝐿 + 1 ▪ Portanto, a complexidade de tempo O(R-L+1) ➢O mesmo vale para o número de comparações entre chaves e movimentações ▪ No, caso de todo o vetor (L=1 e R=N), temos complexidade O(N) 5.4.1. Operação de Fusão 26 Introdução à Computação II – 5954006 • Passos: 1. Dividir a sequência inicial a em duas sequências, b e c 2. Fundir b e c por meio da combinação de elementos isolados para formarem pares ordenados 3. Denominar a a sequência assim obtida e repetir os passos 1 e 2, desta vez efetuando a fusão de pares ordenados em quádruplas ordenadas 4. Repetir os passos anteriores, executando a fusão de quádruplas em óctuplas, e assim prosseguindo duplicando a cada vez o comprimento das subsequências envolvidas no processo de fusão, até que toda sequência esteja ordenada 5.4.2. Ordenação por Fusão Direta 27 Introdução à Computação II – 5954006 • que é particionado em • A fusão de elementos isolados em pares ordenados resulta em 45 56 12 43 95 19 8 67 a 45 56 12 43 b 95 19 8 67 c 45 95 19 56 8 12 43 67 a 5.4.2. Ordenação por Fusão Direta Exemplo 5.4.2. Considere o vetor 28 Introdução à Computação II – 5954006 • Particionando-se novamente • Obtém-se • A fusão de pares ordenados em quádruplas resulta em 45 95 19 56 b 8 12 43 67 c 8 12 45 95 19 43 56 67 a 45 95 19 56 8 12 43 67 a 5.4.2. Ordenação por Fusão Direta 29 Introdução à Computação II – 5954006 • Particionando o vetor obtido • Obtém-se dois vetores ordenados • A fusão de quáduplas ordenadas em óctuplas resulta em 8 12 45 95 b 19 43 56 67 c 8 12 19 43 45 56 67 95 a 8 12 45 95 19 43 56 67 a 5.4.2. Ordenação por Fusão Direta 30 Introdução à Computação II – 5954006 • No contexto do algoritmo de fusão, ▪ cada operação que trata de uma só vez todo o conjunto de dados é denominada fase • No exemplo anterior, a ordenação foi realizada em três passos, cada qual consistindo de uma fase de particionamento e uma fase de fusão • Como pode ser observado, para que seja possível a realização da ordenação, são necessárias três sequências 5.4.2. Ordenação por Fusão Direta 31 Introdução à Computação II – 5954006 • Na realidade, as fases de particionamento não oferecem nenhuma contribuição ao processo de ordenação ▪ Essas fases constituem a metade de todas as operações de movimentações e podem ser eliminadas através da combinação da fase de particionamento com a de fusão • Ao invés de efetuar uma fusão para produzir uma sequência única, o resultado do processo de fusão é imediatamente redistribuído em duas sequências, as quais constituirão as fontes de dados que alimentarão os passo seguinte 5.4.2. Ordenação por Fusão Direta 32 Introdução à Computação II – 5954006 • Em contraste com a ordenação descrita anteriormente e conhecida como fusão de duas fases, este novo método é denominado fusão de fase única ou fusão balanceada • A fusão de fase única é mais interessante, uma vez que são necessárias somente a metade das operações de movimentações exigidas na fusão de duas fases 5.4.2. Ordenação por Fusão Direta 33 Introdução à Computação II – 5954006 • A ideia básica do algoritmo mergesort é realizar várias passagens de fusão sobre os elementos do vetor ▪ Na primeira passagem, são intercaladas sequências de tamanho 1, na segunda o tamanho das sequências é 2 e na i-ésima passagem as sequências intercaladas são de tamanho 2i-1 ▪ O algoritmo mpass realiza uma passagem de ordenação por fusão • Ordenação por fusão (em fase única) é implementada por meio de 3 procedimentos: ▪ mergesort( a[ ] , N ) ▪ mpass( a[ ] , N , p ,c[ ] ) ▪ merge( a[ ], L , h , R , c[ ] ) 5.4.2. Ordenação por Fusão Direta 34 Introdução à Computação II – 5954006 Algoritmo mpass( a[ ] , N , p ,c[ ] ) /* pré: N>0 é o número de elementos do vetor a e p é o tamanho das subseqüências de a que serão intercaladas pós: Intercala pares adjacentes de comprimento p da seqüência a para c */ i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto // intercalar restante de comprimento < 2*p se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se 5.4.2. Ordenação por Fusão Direta 35 Introdução à Computação II – 5954006 6 12 8 2 4 1 5 3 17 7 15 a N=13 13 10 c p=2 i i+p-1 1 2 3 4 5 6 7 8 9 10 11 12 13 i+2p-1 N-2p+1 Algoritmo mpass( a[ ] , N , p ,c[ ] ) i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se 5.4.2. Ordenação por Fusão Direta 36 Introdução à Computação II – 5954006 Algoritmo mpass( a[ ] , N , p ,c[ ] ) i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se 6 12 8 2 4 1 5 3 17 7 15 a N=13 13 10 c p=2 i i+p-1 1 2 3 4 5 6 7 8 9 10 11 12 13 i+2p-1 merge( a , L , h , R , c ) N-2p+1 5.4.2. Ordenação por Fusão Direta 37 Introdução à Computação II – 5954006 6 12 8 2 4 1 5 3 17 7 15 a N=13 13 10 c p=2 i i+p-1 1 2 3 4 5 6 7 8 9 10 11 12 13 i+2p-1 R h h+1 L N-2p+1 Algoritmo mpass( a[ ] , N , p ,c[ ] ) i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se merge( a , L , h , R , c ) 5.4.2. Ordenação por Fusão Direta 38 Introdução à Computação II – 5954006 6 12 8 2 4 1 5 3 17 7 15 a N=13 13 10 1 2 4 5 c p=2 i i+p-1 1 2 3 4 5 6 7 8 9 10 11 12 13 i+2p-1 R h h+1 L N-2p+1 Algoritmo mpass( a[ ] , N , p ,c[ ] ) i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se merge( a , L , h , R , c ) 5.4.2. Ordenação por Fusão Direta 39 Introdução à Computação II – 5954006 Algoritmo mpass( a[ ] , N , p ,c[ ] ) i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se 6 12 8 2 4 1 5 3 17 7 15 a N=13 13 10 1 2 4 5 c p=2 i i+p-1 1 2 3 4 5 6 7 8 9 10 11 12 13 i+2p-1 R h h+1 L N-2p+1 5.4.2. Ordenação por Fusão Direta 40 Introdução à Computação II – 5954006 Algoritmo mpass( a[ ] , N , p ,c[ ] ) i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se 6 12 8 2 4 1 5 3 17 7 15 a N=13 13 10 1 2 4 5 3 7 15 17 c p=2 i i+p-1 1 2 3 4 5 6 7 8 9 10 11 12 13 i+2p-1 R h h+1 L N-2p+1 5.4.2. Ordenação por Fusão Direta 41 Introdução à Computação II – 5954006 Algoritmo mpass( a[ ] , N , p ,c[ ] ) i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se 6 12 8 2 4 1 5 3 17 7 15 a N=13 13 10 1 2 4 5 3 7 15 17 c p=2 i i+p-1 1 2 3 4 5 6 7 8 9 10 11 12 13 i+2p-1 R h h+1 L N-2p+1 5.4.2. Ordenação por Fusão Direta 42 Introdução à Computação II – 5954006 6 12 8 2 4 1 5 3 17 7 15 a N=13 13 10 6 8 12 1 2 4 5 3 7 15 17 c 13 p=2 i i+p-1 1 2 3 4 5 6 7 8 9 10 11 12 13 i+2p-1 R h h+1 L N-2p+1 Algoritmo mpass( a[ ] , N , p ,c[ ] ) i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se 5.4.2. Ordenação por Fusão Direta 43 Introdução à Computação II – 5954006 6 12 8 2 4 1 5 3 17 7 15 a N=13 13 10 6 8 12 1 2 4 5 3 7 15 17 c 13 p=2 i i+p-1 1 2 3 4 5 6 7 8 9 10 11 12 13 N-2p+1 Algoritmo mpass( a[ ] , N , p ,c[ ] ) i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se 5.4.2. Ordenação por Fusão Direta 44 Introdução à Computação II – 5954006 6 12 8 2 4 1 5 3 17 7 15 a N=13 13 10 6 8 12 1 2 4 5 3 7 15 17 c 13 10 p=2 i i+p-1 1 2 3 4 5 6 7 8 9 10 11 12 13 N-2p+1 Algoritmo mpass( a[ ] , N , p ,c[ ] ) i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se 5.4.2. Ordenação por Fusão Direta 45 Introdução à Computação II – 5954006 6 12 8 2 4 1 5 3 17 7 15 a 13 10 6 8 12 1 2 4 5 3 7 15 17 c 13 10 1 2 3 4 5 6 7 8 9 10 11 12 13 Término da passagem para p=2 Algoritmo mpass( a[ ] , N , p ,c[ ] ) i  1 enquanto ( i ≤ N-2*p+1 ) merge( a, i , i+p-1 , i+2*p-1 , c ) i  i + 2*p fim enquanto se ( i+p-1 < N ) merge( a , i , i+p-1 , N , c ) senão para j  i até j  N c[ j ]  a[ j ] fim para fim se 5.4.2. Ordenação por Fusão Direta 46 Introdução à Computação II – 5954006 Algoritmo mergesort( a[ ] , N ) p  1 enquanto ( p < N ) mpass( a, N , p , c ) p  2*p mpass( c, N , p , a ) p  2*p fim enquanto 12 6 13 4 2 5 1 17 3 7 15 a 8 10 6 12 8 2 4 1 5 3 17 7 15 c 13 10 1 2 3 4 5 6 7 8 9 10 11 12 13 N=13 p=1 5.4.2. Ordenação por Fusão Direta 47 Introdução à Computação II – 5954006 6 8 12 1 2 4 5 3 7 15 17 a 13 10 1 2 3 4 5 6 7 8 9 10 11 12 13 N=13 p=2 6 12 8 2 4 1 5 3 17 7 15 c 13 10 Algoritmo mergesort( a[ ] , N ) p  1 enquanto ( p < N ) mpass( a, N , p , c ) p  2*p mpass( c, N , p , a ) p  2*p fim enquanto 5.4.2. Ordenação por Fusão Direta 48 Introdução à Computação II – 5954006 6 8 10 1 2 3 4 5 7 15 17 c 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 N=13 p=4 6 8 12 1 2 4 5 3 7 15 17 a 13 10 Algoritmo mergesort( a[ ] , N ) p  1 enquanto ( p < N ) mpass( a, N , p , c ) p  2*p mpass( c, N , p , a ) p  2*p fim enquanto 5.4.2. Ordenação por Fusão Direta 49 Introdução à Computação II – 5954006 10 12 13 1 2 3 4 5 6 7 8 a 15 17 1 2 3 4 5 6 7 8 9 10 11 12 13 N=13 p=8 6 8 10 1 2 3 4 5 7 15 17 c 12 13 Algoritmo mergesort( a[ ] , N ) p  1 enquanto ( p < N ) mpass( a, N , p , c ) p  2*p mpass( c, N , p , a ) p  2*p fim enquanto 5.4.2. Ordenação por Fusão Direta 50 Introdução à Computação II – 5954006 5.4.2. Ordenação por Fusão Direta Exercício 5.4.3. Utilizando ordenação pelo método mergesort, obtenha o número de comparações e movimentações (p) em cada passo para os seguintes vetores ▪ [ 45 56 12 43 95 19 8 67 ] ▪ [ 8 12 19 43 45 56 67 95 ] ▪ [ 95 67 56 45 43 19 12 8 ] ▪ [ 19 12 8 45 43 56 67 95 ] 51 Introdução à Computação II – 5954006 Exercício 5.4.3. Solução p Ci Mi 45 56 12 43 95 19 8 67 1 4 8 45 56 12 43 19 95 8 67 2 5 8 12 43 45 56 8 19 67 95 4 6 8 8 12 19 43 45 56 67 95 8 0 8 8 12 19 43 45 56 67 95 15 32 p Ci Mi 8 12 19 43 45 56 67 95 1 4 8 8 12 19 43 45 56 67 95 2 4 8 8 12 19 43 45 56 67 95 4 4 8 8 12 19 43 45 56 67 95 8 0 8 8 12 19 43 45 56 67 95 12 32 p Ci Mi 19 12 8 45 43 56 67 95 1 4 8 12 19 8 45 43 56 67 95 2 5 8 8 12 19 45 43 56 67 95 4 5 8 8 12 19 43 45 56 67 95 8 0 8 8 12 19 43 45 56 67 95 14 32 p Ci Mi 95 67 56 45 43 19 12 8 1 4 8 67 95 45 56 19 43 8 12 2 4 8 45 56 67 95 8 12 19 43 4 4 8 8 12 19 43 45 56 67 95 8 0 8 8 12 19 43 45 56 67 95 12 32 5.4.2. Ordenação por Fusão Direta 52 Introdução à Computação II – 5954006 • Análise ▪ Em mergesort( a[ ] , N ), repare que a sequência de p é: ➢p=1,2,4,8,16,..., 2𝑟−1, 2𝑟= 20, 21, 22, 23, 24,..., 2𝑟−1, 2𝑟 sendo 2𝑟−1 < 𝑁 e 2𝑟 ≥ 𝑁 ➢Ou seja, o número de passagens é 𝒓 = 𝒍𝒐𝒈𝟐 𝑵 , isto é, O(𝒍𝒐𝒈𝟐 𝑵) ▪ Cada passagem de ordenação por intercalação realizada por mpass( a[ ] , N , p ,c[ ] ) chama várias vezes merge( a[ ], L , h , R , c[ ] ) ➢O procedimento merge( a[ ], L , h , R , c[ ] ) é O(R-L+1) ➢Como todo o vetor será percorrido pelas várias chamadas de merge(.) em mpass(.), no total teremos N elementos em cada passagem de mpass(.), fazendo com que este procedimento seja O(N) 5.4.2. Ordenação por Fusão Direta 53 Introdução à Computação II – 5954006 • Análise ▪ Portanto, para mergesort( a[ ] , N ), o tempo total é ▪ O(N log2N) ➢O mesmo vale para o número de comparações entre chaves e movimentações de registros ▪ Vale ressaltar, entretanto, que existem várias chamadas de procedimento envolvidas no processo, o que, normalmente, acarreta um grande número de operações 5.4.2. Ordenação por Fusão Direta 54 Introdução à Computação II – 5954006 Comentários • Agradecimentos ◼ Parte do material desta apresentação foi obtida através de slides da disciplina de Introdução à Computação II ministrada pelo Prof. José Augusto Baranauskas