Classificação de dados por Intercalação:
MergeSort
Prof. Alexandre Parra Carneiro da Silva
[email protected]
Principais Métodos

Classificação por Trocas

Classificação por Seleção

Classificação por Inserção

Classificação por Intercalação
Classificação por Intercalação


Caracteriza-se pela utilização do padrão de projeto
Divisão e Conquista.
Idéia básica (MergeSort): é muito fácil criar uma
seqüência ordenada a partir de duas outras também
ordenadas.
Divisão e Conquista: MergeSort



Divisão: se S tem zero ou um elemento, retorna-se S (já está
ordenado). Em qualquer outro caso (S tem pelo menos 2
elementos), removem-se todos os elementos de S e colocam-se
em duas seqüências, S1 e S2, cada um contendo
aproximadamente a metade dos elementos de S;
Recursão: ordena-se recursivamente as seqüências S1 e S2;
Conquista: os elementos são colocados de volta em S, unindo
as seqüências S1 e S2 em uma seqüência ordenada.
Exemplo Divisão e Conquista (MergeSort)
85
24
63
45
17
31
96
50
17
24
31
45
50
63
85
96
85
24
63
45
17
31
96
50
24
45
63
85
17
31
50
96
85
24
63
45
17
31
96
50
24
85
45
63
17
31
50
96
45
17
31
96
50
85
24
63
45
17
31
96
50
85
24
63
(a) Fase de Divisão
(b) Fase de Conquista
Exemplo do Processo MergeSort
MergeSort: Junção ou Merge

Utiliza um vetor temporário (Vtemp) para
manter o resultado da ordenação dos 2 subvetores.
MergeSort: Junção ou Merge

Após a ordenação, o conteúdo de Vtemp é
transferido para o vetor.
MergeSort: Junção ou Merge

Número de operações críticas ?
MergeSort: Junção ou Merge
Visão Geral do Processo MergeSort
MergeSort (parte do pseudo-código)
Algoritmo merge(S1,S2,S):
{ Entrada: Seqüências ordenadas S1 e S2 e uma seqüência vazia de S, todos implementados como
arranjos. }
{ Saída: Seqüência ordenada S contendo os elementos de S1 e S2. }
i  j 0
enquanto i < S1.size() e j < S2.size() faça
se S1.get(i) <= S2.get(j) então
S.addLast(S1.get(j)) { copia o i-nésimo elemento de S1 para o final de S }
ii+1
senão
S.addLAst(S2.get(j)) { copia o j-nésimo elemento de S2 para o final de S }
jj+1
fimse
fimenquanto
enquanto i < S1.size() faça { copia os elementos restantes de S1 para S }
S.addLast(S1.get(i))
ii+1
fimenquanto
enquanto j < S2.size() faça { copia os elementos restantes de S2 para S }
S.addLast(S2.get(j))
j  j +1
fimenquanto
Exercício

Dado o vetor com as chaves [9 25 10 18 5
7
15
3], aplicar o método MergeSort para
ordená-lo crescentemente.
MergeSort: Análise de Desempenho



Cenário do Melhor Caso ???
Cenário do Pior Caso ???
Cenário do Caso Médio ???
(1/4)
MergeSort: Melhor Caso


(2/4)
Característica: nunca é necessário trocar
após comparações.
Quando isto ocorre !?
MergeSort: Pior Caso (3/4)


Característica: sempre é necessário trocar
após comparações.
Quando isso ocorre !?
MergeSort: Caso Médio (4/4)


Característica: há necessidade de haver
trocas após comparações.
Quando isso ocorre !?
Considerações Finais

É possível implementar o Merge Sort utilizando
somente um vetor auxiliar ao longo de toda a
execução, tornando assim a complexidade de espaço
adicional igual a Θ(n).

É possível também implementar o algoritmo com
espaço adicional Θ(1).

Algoritmo criado por Von Neumann.

Comprovado matematicamente que é praticamente
impossível fazer um algoritmo mais eficiente.
Site sobre ordenação

http://math.hws.edu/TMCM/java/xSortLab/





BubbleSort
QuickSort
SelectionSort
InsertionSort (Busca Seqüencial)
MergeSort