Buscar

Aula sobre Mergesort

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Mergesort
Katia Guimarães
*
*
Problema de Ordenação
Dado um array com n números naturais, 
ordenar estes números em ordem 
crescente. 
INPUT: 95 48 70 86 21 37
OUTPUT: 21 37 48 70 86 95
*
*
Abordagem Dividir-para-Conquistar
Método em Computação que consiste em 
 - Dividir a entrada em conjuntos menores
 - Resolver cada instância menor de 
 maneira recursiva
 - Reunir as soluções parciais para compor 
 a solução do problema original. 
*
*
Exemplo de Mergesort
INPUT: 47 26 33 05 99 38 64 15
 1. Divide: 47 26 33 05 99 38 64 15
 2. Resolve Recursivamente:
 a) Primeira metade 47 26 33 05 
 (Divide, Resolve recursivamente, Intercala
 Obtendo 05 26 33 47 )
 b) Segunda metade 99 38 64 15
 (Divide, Resolve recursivamente, Intercala
 Obtendo 15 38 64 99 )
*
*
Exemplo de Mergesort
INPUT: 47 26 33 05 99 38 64 15
2. Resolve Recursivamente:
 a) (Retorna 05 26 33 47 )
 b) (Retorna 15 38 64 99 )
3. Intercala as soluções parciais:
 05 15 26 33 38 47 64 99 
*
*
Algoritmo Mergesort
Entrada : (A, B, ini, fim) 
Saída : B [ ini .. fim], array A ordenado de ini até fim
begin
	if (fim = ini) 
		retorne(*);
	else
		MergeSort (A, B, ini, (ini + fim)/2 );
		MergeSort (A, B, (ini + fim)/2 +1, fim);
		Intercala (A, B, ini, (fim+ini)/2 +1, (fim-ini+1) );
		retorne(*);
end	
 (*) O array com a resposta depende do tamanho de A.
*
*
Algoritmo Intercala
Entrada: (A, B, ini1, ini2, n)
Saída: Elementos B[ini1 .. ini1+n-1] ordenados 
begin
	int i  ini1, j  ini2, k  ini1;
	while ( i < ini2 and j < ini1+n ) do
	 if (A[i]  A[j] ) 
	 then { B[k]  A[i]; i  i+1; k  k+1 }	 else { B[k]  A[j]; j  j+1; k  k+1 }
	while ( i < ini2 ) do /*copia 1a. metade.*/
		{ B[k]  A[i]; k  k+1; i  i+1 }
	while ( j < ini1+n ) do /*copia 2a. metade.*/
		{ B[k]  A[j]; k  k+1; j  j+1 }
	return ( B )
end
*
*
Exemplo de MergeSort
*
*
Implementação do Mergesort
O procedimento Intercala requer o uso de um 
segundo array, B, para receber os dados ordenados. 
 
Note que no retorno de Mergesort com um array de tamanho 1, a resposta encontra-se no array A (o array original de entrada). No próximo nível (array de comprimento 2) o resultado da intercalação estará no array B. 
Podemos administrar este problema de duas maneiras.
*
*
Implementação do Mergesort
Podemos administrar este problema de
duas maneiras:
 - Copiando a porção do array referente ao 
 resultado de volta para o array A, ou 
 - Utilizando uma chave para indicar a “direção”
 dos movimentos de Intercala.
*
*
Complexidade do Mergesort
TMergesort(n) = 
 2 • TMergesort(n/2) + cte • n + cte
	
	Forma Fechada de Recorrência
TMS (n) = 2 • TMS(n/2) + c • n + c
 = 2 •[ 2 • TMS(n/4) + c • n/2 + c ] + c • n + c 
 = 4 • TMS(n/4) + 2c • n + 3c
 = 4 •[ 2 • TMS(n/8) + c • n/4 + c ] + 2c • n + 3c
 = 8 • TMS(n/8) + 3c • n + 7c
 = ...
 TMS (n) = 2i • TMS(n/2i) + i • c • n + (2i-1) • c
*
*
Complexidade do Mergesort
Temos que TMS(n) = 2i • TMS(n/2i) + i • c • n + (2i-1) • c.
 Note que sabemos o valor de TMS(1).
 Para obter um valor fechado, queremos que (n/2i) = 1.
 Isso ocorre quando i = log2n.
 TMS(n) = 2log2n • cte + (log2n) • c • n + (2log2n - 1) • c
	 = n • cte + c • n • log2n + c •(n-1)
	 = c • nlog2n + (cte+c) • n - c
		TMS(n) = O(n • log2n)

Teste o Premium para desbloquear

Aproveite todos os benefícios por 3 dias sem pagar! 😉
Já tem cadastro?

Outros materiais