M Todos De Classifica O Intercala O

Métodos de Classificação –
Intercalação e Distribuição de
Chaves
Prof. Msc. Thiago Salhab Alves [e-mail] Métodos de Classificação - Intercalação
Os métodos de classificação por intercalação dividem a tabela em dois ou mais segmentos, ordenam estes segmentos e depois os intercalam, terminando, ao final, com um único segmento (toda a tabela) ordenado. O principal algoritmo desta família é o MergeSort (ou
Intercalação Simples).

3

Métodos de Classificação - Intercalação
MergeSort (Intercalação Simples)
A idéia por traz do MergeSort é bastante simples: divide-se a tabela em diversos segmentos menores para a seguir ordenar-se estes segmentos.
Feito isto, estes segmentos são agrupados entre sí
(intercalados) e este processo produz novos segmentos ordenados (maiores que os segmentos iniciais). 4

Métodos de Classificação - Intercalação
O processo de agrupamento e ordenação dos segmentos (intercalação) continua até que se obtenha um único segmento que contenha toda a tabela e esteja totalmente ordenado.
Exemplo:

Tabela original:

5

Métodos de Classificação Intercalação
Divisão em segmentos de tamanho igual a 2:

Ordenação destes segmentos de tamanho igual a 2:

6

Métodos de Classificação Intercalação
Intercalação em novos segmentos de tamanho igual a 4:

Ordenação destes segmentos de tamanho igual a 4:

7

Métodos de Classificação Intercalação
Intercalação em novos segmentos de tamanho igual a 8:

Ordenação destes segmentos de tamanho igual a 8:

8

Métodos de Classificação Intercalação
Intercalação em segmentos de tamanho igual a 16 (toda tabela):

Ordenação destes segmentos de tamanho igual a 16 (toda tabela):

9

Métodos de Classificação - Intercalação
Desempenho
A complexidade para o pior caso da ordenação por
MergeSort é O(nlog2n), que também a complexidade para o caso médio (mais freqüente) das ordenações.
Já o melhor caso ocorre, por exemplo, quando a tabela já está ordenada ou quando a tabela está em ordem inversa à desejada.
Para o