PGINF591 – Algoritmos e Estruturas de Dados
Ordenação por Intercalação
(Merge Sort)
Prof. Dr. Rafael Giusti
[email protected] Divisão e conquista
» Divisão e conquista é um paradigma de projeto
» Algoritmos de divisão e conquista compartilham
as seguintes características
» A entrada é (normalmente) dividida em dois
sub-problemas de tamanhos aproxim. iguais
» Cada sub-problema é resolvido separadamente
» A solução dos sub-problemas é juntada para
construir a solução da entrada original
Por que dividir?
» Ordenação quadrática vs. quasilinear
» Os algoritmos de ordenação que estudamos
até agora são quadráticos
~ Bolha método de força bruta
~ Inserção redução e conquista
~ Seleção força bruta
» Todos eles fazem comparação entre elementos
adjacentes ou entre um elemento e os demais
do vetor
Por que dividir?
» Métodos da bolha e da inserção: comparam apenas
elementos adjacentes
7 8 5 3 6 2 4 1
j=1 i=n
» Método da seleção: compara um elemento contra
todos os restantes do vetor
i=1 j=4
3 2 3 2 2 1 5
menor
Método da bolha é pouco eficiente: change my mind...
» Esses algoritmos são pouco eficientes porque ganham
pouca informação sobre os dados em cada passo
» Após a primeira passagem pelo vetor...
7 8 5 3 6 2 4 1
j=1 i=n
Método da bolha é pouco eficiente: change my mind...
» Esses algoritmos são pouco eficientes porque ganham
pouca informação sobre os dados em cada passo
» Após a primeira passagem pelo vetor...
7 8
5 8
5 3 6 2 4 1
j=2 i=n
Método da bolha é pouco eficiente: change my mind...
» Esses algoritmos são pouco eficientes porque ganham
pouca informação sobre os dados em cada passo
» Após a primeira passagem pelo vetor...
7 5 8
3 8
3 6 2 4 1
j=3 i=n
Método da bolha é pouco eficiente: change my mind...
» Esses algoritmos são pouco eficientes porque ganham
pouca informação sobre os dados em cada passo
» Após a primeira passagem pelo vetor...
7 5 3 8
6 6
8 2 4 1
j=4 i=n
Método da bolha é pouco eficiente: change my mind...
» Esses algoritmos são pouco eficientes porque ganham
pouca informação sobre os dados em cada passo
» Após a primeira passagem pelo vetor...
7 5 3 6 2
8 8
2 4 1
j=5 i=n
Método da bolha é pouco eficiente: change my mind...
» Esses algoritmos são pouco eficientes porque ganham
pouca informação sobre os dados em cada passo
» Após a primeira passagem pelo vetor...
7 5 3 6 2 8
4 8
4 1
j=6 i=n
Método da bolha é pouco eficiente: change my mind...
» Esses algoritmos são pouco eficientes porque ganham
pouca informação sobre os dados em cada passo
» Após a primeira passagem pelo vetor...
7 5 3 6 2 4 81 81
j=7 i=n
Método da bolha é pouco eficiente: change my mind...
» Esses algoritmos são pouco eficientes porque ganham
pouca informação sobre os dados em cada passo
» Após a primeira passagem pelo vetor…
...tudo o que descobrimos é que o elemento no índice
A[n] é maior que todos os demais
7 5 3 6 2 4 1 8
i=n
Em nenhum momento tentamos estabelecer relações
entre coleções de elementos. Precisamos verificar
todos os pares pelo menos uma vez
Um algoritmo um pouco melhor: o Professor Sort
» Um algoritmo “quase” de divisão e conquista
» Professor Sort
~ Divida o vetor em dois
~ Aplique o método da bolha em cada metade
separadamente
~ Faça intercalação das duas metades...
Um algoritmo um pouco melhor: o Professor Sort
» À primeira vista, esse algoritmo não parece ser mais
eficiente do que o método da bolha…
» Suponha que o tempo necessário para ordenar um
vetor de 100.000 elementos é de 400 segundos…
100.000 elementos 400s
» Ao dividirmos o vetor em 2…
50.000 elementos 200s 50.000 elementos 200s
O tempo total não continua sendo o mesmo? Isto é, 200 segundos +
200 segundo = 400 segundos?
Um algoritmo um pouco melhor: o Professor Sort
» À primeira vista, esse algoritmo não parece ser mais
eficiente do que o método da bolha…
» Suponha que o tempo necessário para ordenar um
vetor de 100.000 elementos é de 400 segundos…
100.000 elementos 400s
» Ao dividirmos o vetor em 2…
50.000 elementos 200s
100s 50.000 elementos 200s
100s
O tempo total não continua sendo o mesmo? Isto é, 200 segundos +
200 segundo = 400 segundos? Não. O certo seria 100s em
cada metade e um total de aprox. 200s
Por que funciona?
» Considerando-se que o método da bolha é Θ(n²),
podemos estimar a complexidade do ProfessorSort
como sendo a seguinte
Algoritmo
Algoritmo ProfessorSort(A)
ProfessorSort(A)
Ae
Ae ←← metade
metade esquerda de AA ΘΘ(1)
esquerda de (1)
Ad
Ad ←← metade
metade direita
direita de
de AA Θ
Θ(1)
(1)
BubbleSort(Ae)
BubbleSort(Ae) Θ
Θ((((n/2)²
n/2)²))
BubbleSort(Ad)
BubbleSort(Ad) Θ
Θ((((n/2)²
n/2)²))
AA ←← intercale
intercale Ae Ad ΘΘ((n)n)
Ae ++ Ad
Por que funciona?
» Considerando-se que o método da bolha é Θ(n²),
podemos estimar a complexidade do ProfessorSort
como sendo a seguinte
Algoritmo
Algoritmo ProfessorSort(A)
ProfessorSort(A)
Ae
Ae ←← metade
metade esquerda de AA ΘΘ(1)
esquerda de (1)
Ad
Ad ←← metade
metade direita
direita de
de AA Θ
Θ(1)
(1)
BubbleSort
BubbleSort(Ae)
(Ae) Θ
Θ((n²/4)
n²/4)
BubbleSort
BubbleSort(Ad)
(Ad) Θ
Θ((n²/4)
n²/4)
AA ←← intercale
intercale Ae Ad ΘΘ((n)n)
Ae ++ Ad
Por que funciona?
» Considerando-se que o método da bolha é Θ(n²),
podemos estimar a complexidade do ProfessorSort
como sendo a seguinte
Algoritmo
Algoritmo ProfessorSort(A)
ProfessorSort(A)
Ae
Ae ←← metade
metade esquerda
esquerda de
de AA
Ad
Ad ←← metade
metade direita
direita de
de AA
BubbleSort
BubbleSort(Ae)
(Ae)
BubbleSort
BubbleSort(Ad)
(Ad)
AA ←← intercale
intercale Ae
Ae ++ Ad
Ad
Θ
Θ(1)
(1) + Θ
Θ(1)
(1) + Θ
Θ((n²/4)
n²/4) + Θ
Θ((n²/4)
n²/4) + Θ
Θ((n)
n) = Θ
Θ((n²/2)
n²/2)
Bolha vs. professor
Bolha vs. professor
» O algoritmo “ProfessorSort” é quadrático, assim como
o método da bolha
» Ambos têm pior caso Θ(n²)
» Mas o “ProfessorSort” leva aproximadamente um
quarto do tempo utilizado pelo método da bolha
» Como o método da bolha é quadrático, reduzir o
tamanho do vetor pela metade “corta” o tempo
necessário para ordenar cada metade em 75%
E se continuarmos dividindo o
vetor ao meio até que sobre
apenas um elemento????
Merge Sort
» A ordenação pelo Método da Intercalação (também
chamado Merge Sort) é um método de divisão e
conquista que faz dois passos:
» Divisão:
~ O vetor, de tamanho n, é dividido em duas metades
com tamanhos ⌊n/2⌋ e ⌈n/2⌉
~ Cada metade é ordenada separadamente
» Conquista:
~ As duas metades ordenadas são intercaladas,
produzindo a ordenação do vetor original
Merge Sort
Divisão
5 3 6 2 7 4 1
Merge Sort
Divisão
5 3 6 2 7 4 1
Merge Sort
Caso base
5 3 6 2 7 4 1
Merge Sort
Divisão
5 3 6 2 7 4 1
Merge Sort
Caso base
5 3 6 2 7 4 1
Merge Sort
Caso base Caso base
5 3 6 2 7 4 1
Merge Sort
Conquista
5 3 6 2 7 4 1
3 6
Vetor auxiliar para intercalação
Merge Sort
Conquista
5 3 6 2 7 4 1
3 6
Vetor auxiliar para intercalação
Merge Sort
Conquista
5 3 6 2 7 4 1
3 5 6
Vetor auxiliar para intercalação
Merge Sort
Conquista
3 5 6 2 7 4 1
3 5 6
Vetor auxiliar para intercalação
Merge Sort
3 5 6 2 7 4 1
Vetor auxiliar para intercalação
Merge Sort
Divisão
3 5 6 2 7 4 1
Vetor auxiliar para intercalação
Merge Sort
Divisão
3 5 6 2 7 4 1
Vetor auxiliar para intercalação
Merge Sort
Caso base
3 5 6 2 7 4 1
Vetor auxiliar para intercalação
Merge Sort
Caso base
3 5 6 2 7 4 1
Vetor auxiliar para intercalação
Merge Sort
Caso base Caso base
3 5 6 2 7 4 1
Vetor auxiliar para intercalação
Merge Sort
Caso base Caso base
3 5 6 2 7 4 1
Vetor auxiliar para intercalação
Merge Sort
Conquista
3 5 6 2 7 4 1
2 7
Vetor auxiliar para intercalação
Merge Sort
Divisão
3 5 6 2 7 4 1
Vetor auxiliar para intercalação
Merge Sort
Caso base
3 5 6 2 7 4 1
Vetor auxiliar para intercalação
Merge Sort
Caso base Caso base
3 5 6 2 7 4 1
Vetor auxiliar para intercalação
Merge Sort
Conquista
3 5 6 2 7 4 1
1 4
Vetor auxiliar para intercalação
Merge Sort
Conquista
3 5 6 2 7 1 4
1 4
Vetor auxiliar para intercalação
Merge Sort
Conquista
3 5 6 2 7 1 4
1 2 4 7
Vetor auxiliar para intercalação
Merge Sort
Conquista
3 5 6 1 2 4 7
1 2 4 7
Vetor auxiliar para intercalação
Merge Sort
3 5 6 1 2 4 7
Vetor auxiliar para intercalação
Merge Sort
Conquista
3 5 6 1 2 4 7
1 2 3 4 5 6 7
Vetor auxiliar para intercalação
Merge Sort
Conquista
1 2 3 4 5 6 7
1 2 3 4 5 6 7
Vetor auxiliar para intercalação
Merge Sort
1 2 3 4 5 6 7
Vetor auxiliar para intercalação
Merge sort
» Algoritmo MergeSort(A)
se |A| ≥ 2
meio ← ⌊|A|/2⌋
esq ← MergeSort(A[1..meio])
dir ← MergeSort(A[meio+1..|A|])
A ← intercala(esq, dir)
retorne A
Complexidade do MergeSort
» O Merge Sort é um algoritmo recursivo
Algoritmo
Algoritmo MergeSort(A)
MergeSort(A)
se
se |A|
|A| ≥≥ 22
meio
meio ←← ⌊⌊|A|//22⌋⌋
|A|
esq
esq ←← MergeSort(A[1..meio])
MergeSort(A[1..meio])
dir
dir ←← MergeSort(A[meio+1..|A|])
MergeSort(A[meio+1..|A|])
AA ←← intercala(esq,
intercala(esq, dir)
dir)
retorne
retorne AA
» Seja n = |A| o tamanho da entrada
» Então como descrever o tempo do algoritmo por
meio de uma função T(n)?
Relação de recorrência
» O tempo de um algoritmo recursivo pode ser descrito
na forma de uma relação de recorrência
Algoritmo
Algoritmo fatorial(n)
fatorial(n)
se
se nn ≤≤ 11
retorne
retorne 11
senão
senão
retorne
retorne nn ** fatorial(n
fatorial(n -- 1)
1)
» Passos necessários para n = 1?
» T(1) =
» Passos necessários para n > 1? (ex.: n = 5)
» T(5) =
Relação de recorrência
» O tempo de um algoritmo recursivo pode ser descrito
na forma de uma relação de recorrência
Quando
Quandonn==1...
1...
Algoritmo
Algoritmo fatorial(n)
fatorial(n)
se
se nn ≤≤ 11 ...estas
...estasduas
duaslinhas
linhassão
são
retorne
retorne 11 executadas
executadasumaumavez
vezcada.
cada.
senão
senão
retorne
retorne nn ** fatorial(n
fatorial(n -- 1) 1)
» Passos necessários para n = 1?
» T(1) = 2
» Passos necessários para n > 1? (ex.: n = 5)
» T(5) =
Relação de recorrência
» O tempo de um algoritmo recursivo pode ser descrito
na forma de uma relação de recorrência
Quando
Quandonn==5...
5...
Algoritmo
Algoritmo fatorial(n)
fatorial(n)
se
se nn ≤≤ 11
...estas
...estasduas
duaslinhas
linhas
executadas retorne
retorne 11
executadasumaumavez
vez
cada...
cada... senão
senão
retorne
retorne nn ** fatorial(n
fatorial(n -- 1)
1)
…e
…e esta
estalinha
linha executa
executa 11vez.
vez.Além
Alémdisso,
disso,precisamos
precisamos contar
contar
» Passos necessários também
para
tambémtodo
n = 1?
todoootempo
temponecessário
necessáriopara
paraoocalculo
calculode
de
fatorial(4),
fatorial(4),que
queééT(4)...
T(4)...
» T(1) = 2
» Passos necessários para n > 1? (ex.: n = 5)
» T(5) = 3 + T(4) Então
EntãoT(5)
T(5)ééootempo
tempogasto
gastona
nachamada
chamada
fatorial(5)
fatorial(5)++ootempo
tempogasto
gastocom
comfatorial(4)
fatorial(4)
Relação de recorrência
» O tempo de um algoritmo recursivo pode ser descrito
na forma de uma relação de recorrência
Algoritmo
Algoritmo fatorial(n)
fatorial(n)
se
se nn ≤≤ 11
retorne
retorne 11
senão
senão
retorne
retorne nn ** fatorial(n
fatorial(n -- 1)
1)
» Como uma relação de recorrência
Extrapolando
Extrapolandopara
paraqualquer
qualquervalor
valorde
den...
n...
Relação de recorrência
» O tempo de um algoritmo recursivo pode ser descrito
na forma de uma relação de recorrência
Algoritmo
Algoritmo fatorial(n)
fatorial(n)
se
se nn ≤≤ 11
retorne
retorne 11
senão
senão
retorne
retorne nn ** fatorial(n
fatorial(n -- 1)
1)
» Como uma relação de recorrência
Observe
Observeque
queos
osvalores
valoresexatos
exatosdas
dasconstantes
constantesnão
não
são
sãoimportantes…
importantes…podemos
podemostrocar
trocar“2”
“2”ee“3”
“3”por
porcc
Relação de recorrência
» O tempo de um algoritmo recursivo pode ser descrito
na forma de uma relação de recorrência
Algoritmo
Algoritmo fatorial(n)
fatorial(n)
se
se nn ≤≤ 11
retorne
retorne 11
senão
senão
retorne
retorne nn ** fatorial(n
fatorial(n -- 1)
1)
» Como uma relação de recorrência
Tempo do Merge Sort
» Qual T(n) para o Merge Sort?
Algoritmo
Algoritmo MergeSort(A)
MergeSort(A)
se
se |A|
|A| ≥≥ 22
meio
meio ←← ⌊⌊|A|//22⌋⌋
|A|
esq
esq ←← MergeSort(A[1..meio])
MergeSort(A[1..meio])
dir
dir ←← MergeSort(A[meio+1..|A|])
MergeSort(A[meio+1..|A|])
AA ←← intercala(esq,
intercala(esq, dir)
dir)
retorne
retorne AA
» Quando n = 1 (caso base)…
» T(1) =
» Quando n > 1…
» T(n) =
Tempo do Merge Sort
» Qual T(n) para o Merge Sort?
Algoritmo
Algoritmo MergeSort(A)
MergeSort(A)
se
se |A|
|A| ≥≥ 22
meio
meio ←← ⌊⌊|A|//22⌋⌋
|A|
esq
esq ←← MergeSort(A[1..meio])
MergeSort(A[1..meio])
dir
dir ←← MergeSort(A[meio+1..|A|])
MergeSort(A[meio+1..|A|])
AA ←← intercala(esq,
intercala(esq, dir)
dir)
retorne
retorne AA
Tempo do Merge Sort
» Como encontrar uma fórmula fechada em notação O
para a relação de recorrência?
» Existem três técnicas
» Método da substituição
» Método da árvore
» Teorema Mestre
Método da árvore
» Podemos expandir a relação e representar os termos
em uma árvore...
Exemplo T(4) = ?
T(4)
Método da árvore
» Podemos expandir a relação e representar os termos
em uma árvore...
Exemplo T(4) = 4c + T(2)
2T(4/2)
2T(2)+ T(2)
T(4)
Método da árvore
» Podemos expandir a relação e representar os termos
em uma árvore...
Exemplo T(4) = 4c + T(2) + T(2)
T(4)
T(2) T(2)
Método da árvore
» Podemos expandir a relação e representar os termos
em uma árvore...
Exemplo T(4) = 4c + T(2) + T(2)
T(4)
4c
T(2) T(2)
Método da árvore
» Podemos expandir a relação e representar os termos
em uma árvore...
Exemplo T(4) = 4c + T(2) + T(2)
T(2) = 2c + T(1) + T(1)
4c
T(2) T(2)
Método da árvore
» Podemos expandir a relação e representar os termos
em uma árvore...
Exemplo T(4) = 4c + 2c + T(1) + T(1) + 2c + T(1) + T(1)
T(2) = 2c + T(1) + T(1)
4c
T(2) T(2)
Método da árvore
» Podemos expandir a relação e representar os termos
em uma árvore...
Exemplo T(4) = 4c + 2c + T(1) + T(1) + 2c + T(1) + T(1)
T(2)
4c
T(2) T(2)
T(1) T(1) T(1) T(1)
Método da árvore
» Podemos expandir a relação e representar os termos
em uma árvore...
Exemplo T(4) = 4c + 2c + T(1) + T(1) + 2c + T(1) + T(1)
T(2)
4c
T(2)
2c T(2)
2c
T(1) T(1) T(1) T(1)
Método da árvore
» Podemos expandir a relação e representar os termos
em uma árvore...
Exemplo T(4) = 4c + 2c + T(1)
c + T(1)
c + 2c + T(1)
T(2) c + T(1)
c
T(1) = c
4c
T(2)
2c T(2)
2c
T(1) T(1) T(1) T(1)
Método da árvore
» Podemos expandir a relação e representar os termos
em uma árvore...
Exemplo T(4) = 4c + 4c
2c + 4c
c2c
+c +c c+++T(1)
T(1) c c+
c +c+c +
2cc+ T(1)
T(2) c + T(1)
c
4c
T(2)
2c T(2)
2c
T(1)
c T(1)
c T(1)
c T(1)
c
Método da árvore
cn cn
cn/2 cn/2 cn/2 + cn/2
cn
log2(n) níveis
cn/4 cn/4 cn/4 cn/4 cn + cn/4 + cn/4 + cn/4
cn/4
× cn (soma dos nós
em cada nível)
T(n) = cn×log2(n)
T(n) = O(n logn)
c c c c c c c c ... c c+c+c+c+c+c+…+c
cn
Complexidade do Merge Sort
» Complexidade temporal
» O(n logn)
» Complexidade espacial (vetor auxiliar para
intercalação)
» O(n)
C’est fini!
