ALGORITMOS AULA 04

Prévia do material em texto

Protocolos de Redes e de Computadores
AULA 02
ALGORITMOS AVANÇADOS – AULA 04
Prof. Msc. Alexandre José Braga da Silva
alex.professor@gmail.com
CCT0312 – Algoritmos Avançados
Objetivos da Aula:
 Conhecer a definição de Ordenação por Intercalação (mergesort)
 Realizar ordenação por fusão
 Desenvolver algoritmo de ordenação por intercalação mergesort
CCT0312 – Algoritmos Avançados
Ordenação Mergesort:
A ordenação por intercalação é um método eficiente baseado na 
técnica recursiva chamada dividir para conquistar, onde quebramos o
problema em vários subproblemas de menor tamanho que são 
similares ao problema original, resolvemos esses subproblemas 
recursivamente e então combinamos essas soluções para produzir 
uma solução para o problema original.
CCT0312 – Algoritmos Avançados
Ordenação Mergesort:
A técnica de dividir para conquistar é uma técnica geral de construção 
de algoritmos, tendo a recursão como base, que envolve três passos 
em cada nível da recursão:
 Dividir o problema em um número de subproblemas;
 Conquistar os subproblemas solucionando-os recursivamente. No 
entanto, se os tamanhos dos subproblemas são suficientemente 
pequenos, resolva os subproblemas de uma maneira simples;
 Combinar as soluções dos subproblemas na solução do problema 
original.
CCT0312 – Algoritmos Avançados
Problema da Intercalação:
Antes de apresentar o método da ordenação por intercalação, 
precisamos resolver um problema anterior, que auxilia esse método, 
chamado de problema da intercalação. 
Este problema pode ser descrito de forma mais geral: dados dois 
conjuntos crescentes A e B, com m e n elementos respectivamente, 
obter um conjunto crescente C a partir de A e B. 
Variantes sutis desse problema geral podem ser descritas como no 
caso em que se permite ou não elementos iguais nos dois conjuntos 
de entrada A e B tais que A ∩ B ≠ Ø ou A ∩ B = Ø.
CCT0312 – Algoritmos Avançados
Problema da Intercalação:
O problema da intercalação que queremos resolver aqui é mais 
específico e pode ser assim descrito: dados dois vetores crescentes 
v[p..q-1] e v[q..r-1], rearranjar v[p..r-1] em ordem crescente. Isso 
significa que queremos de alguma forma intercalar os vetores v[p..q-
1] e v[q..r-1]. 
Nesse caso parece que os vetores de entrada podem ter elementos 
em comum. Entretanto, este não é o caso, já que estamos 
considerando o mesmo conjunto inicial de elementos armazenados 
no vetor v. Uma solução menos eficiente, que usa um vetor auxiliar, é 
mostrada a seguir:
CCT0312 – Algoritmos Avançados
Problema da Intercalação:
void intercala(int p, int q, int r, int v[MAX]){
int i, j, k, w[MAX];
i=p;
j=q;
k=0;
while(i<q && j<r){
 if(v[i] < v[j]){
 w[k]=v[i];
 i++;
 } else {
 w[k]=v[j];
 j++;
 }
 k++;
}
 while(i<q){
 w[k]=v[i];
 i++;
 k++;
 }
 while(j<r){
 w[k]=v[j];
 j++;
 k++;
 }
 for(i=p;i<r;i++)
 v[i]=w[i=p];
}
CCT0312 – Algoritmos Avançados
Problema da Intercalação:
A função intercala tem tempo de execução de pior caso proporcional 
ao número de comparações entre os elementos do vetor r - p. Assim, 
podemos dizer que o consumo de tempo no pior caso da função 
intercala é proporcional ao número de elementos do vetor de 
entrada.
Se este vetor for muito grande, a função levará muito tempo para 
ordenar os elementos.
CCT0312 – Algoritmos Avançados
Problema da Intercalação:
Vamos agora descrever uma função que implementa o método da 
ordenação por intercalação. Nesse método, dividimos ao meio um 
vetor v com r-p elementos, ordenamos recursivamente essas duas 
metades de v e então as intercalamos. 
A função mergesort a seguir é recursiva e a base da recursão ocorre 
quando p >= r-1, quando não é necessário qualquer processamento.
CCT0312 – Algoritmos Avançados
Problema da Intercalação:
void mergesort(int p, int r, int v[MAX]){
int q;
if(p<r-1){
q = (p+r)/2;
mergesort(p,q,v);
mergesort(q,r,v);
intercala(p,q,r,v);
}
}
CCT0312 – Algoritmos Avançados
Problema da Intercalação:
CCT0312 – Algoritmos Avançados
O Algoritmo Mergesort:
Pode ser expresso de várias formas:
1. O algoritmo é recursivo. A base da recursão é o caso p ≥ r-1
void mergesort (int p, int r, int v[]) {
 if (p < r-1) { 
 int q = (p + r)/2; 
 mergesort (p, q, v); 
 mergesort (q, r, v); 
 intercala (p, q, r, v); 
 }
}
CCT0312 – Algoritmos Avançados
O Algoritmo Mergesort:
2. A versão iterativa do algoritmo Mergesort recebe um vetor v[0..n-1] e 
rearranja o vetor em ordem crescente.
void mergesort_i (int n, int v[]) {
 int p, r, b = 1;
 while (b < n) {
 p = 0;
 while (p + b < n) {
 r = p + 2*b;
 if (r > n) r = n;
 intercala (p, p+b, r, v);
 p = p + 2*b; 
 }
 b = 2*b;
 }
}
CCT0312 – Algoritmos Avançados
O Algoritmo Mergesort:
Para o MergeSort não tem tanta importância se o vetor está no 
melhor, médio ou pior caso, porque para qualquer que seja o caso ele 
sempre terá a complexidade de ordem O(n . log n).
Isso ocorre pelo fato de que o MergeSort independentemente em que
situação se encontra o vetor, ele sempre irá dividir e intercalar.
CCT0312 – Algoritmos Avançados
Ordenação por Fusão:
A fusão é utilizada quando duas ou mais sequências encontram-se 
ordenadas.
O objetivo é intercalar as sequências ordenadas em uma sequência 
ordenada única.
Assim sendo, a operação de fusão é muito mais simples que a de 
ordenação, sendo empregada como operação auxiliar no processo 
mais complexo de ordenação sequencial.
CCT0312 – Algoritmos Avançados
Algoritmo de Fusão:
int i=1,j=1,k=0;
while (i <= N && j <= M) { 
 k++;
 if(a[i] < b[j]) { 
 c[k] = a[i];
 i++;
 } eles { 
 c[k] = b[j];
 j++;
 }
}
while (i <= N) { 
 k++;
 c[k] = a[i];
 i++;
}
while (j <= M) { 
 k++;
 c[k] = b[j];
 j++;
}
CCT0312 – Algoritmos Avançados
Ordenação por Fusão - Exemplo:
Considere o vetor:
Que é particionado em:
A fusão de elementos isolados em pares ordenados resulta:
CCT0312 – Algoritmos Avançados
Ordenação por Fusão - Exemplo:
Dividindo-se ao meio:
Obtém-se:
A fusão de pares ordenados em quádruplas resulta em:
CCT0312 – Algoritmos Avançados
Ordenação por Fusão - Exemplo:
Uma terceira divisão ao meio:
Resulta em:
A fusão de quádruplas ordenadas em óctuplas resulta em:
CCT0312 – Algoritmos Avançados
Algoritmo MergeSort - Exemplo:
#include <iostream>
using namespace std;
void intercala(int p, int q, int r, int v[10]){
 int i, j, k, w[10];
 i=p;
 j=q;
 k=0;
 while(i<q && j<r){
 if(v[i] < v[j]){
 w[k]=v[i];
 i++;
 } else {
 w[k]=v[j];
 j++;
 }
 k++;
 }
 while(i<q){
 w[k]=v[i];
 i++;
 k++;
 }
 while(j<r){
 w[k]=v[j];
 j++;
 k++;
 }
 for(i=p;i<r;i++)
 v[i]=w[i=p];
}
void mergesort(int p, int r, int v[10]){
 int q;
 if(p<r-1){
 q = (p+r)/2;
 mergesort(p,q,v);
 mergesort(q,r,v);
 intercala(p,q,r,v);
 }
}
int main(){
 int p, q, r, v[10];
 p = 0;
 r = 2;
 v[10]=(50, 3, 12, 5, 1, 23, 7, 10, 31, 40);
 mergesort(p,r,v);
}
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20