Novidades

Merge Sort: implementação em java

Por Dificuldade Zero - sexta-feira, 16 de dezembro de 2016 Sem comentários


Merge Sort é um algoritmo que utiliza recursão para ordenar, do tipo dividir para conquistar. Aqui vamos mostrar um algoritmo de Merge Sort para ordenação de vetor de inteiros em ordem crescente.

Como funciona?

Por ser um algoritmo que utiliza-se da técnica de divisão e conquista, sua ideia básica consiste em dividir o problema (vetor) em vários subproblemas (intervalos do vetor) e resolvê-los. Depois disso, ocorre a conquista (a união das resoluções).

Esse algoritmo tem capacidade de ordenar uma parte específica do vetor. São passados três parâmetros: o vetor (a ser ordenado), um inteiro p (índice inicial do intervalo a ser ordenado do vetor) e um inteiro r (índice final do intervalo a ser ordenado do vetor).

Como ocorre a resolução dos subproblemas?



Considere o vetor 4, 2, 3, 1.

1º passo: dividir o vetor em intervalo da direita: intervalo A (4, 2).

2º passo: dividir A em intervalo da direita: intervalo B (4).

3º passo: tentar dividir B (impossível, pois só tem um elemento).

4º passo: dividir A em intervalo da esquerda: intervalo C (2).

5º passo: tentar dividir C (impossível, pois só tem um elemento).

INTERCALAR: temos B e C ordenados, intercala-os: temos A ordenado.

6º passo: dividir o vetor em intervalo da esquerda: intervalo D (3, 1).

7º passo: dividir D em intervalo da esquerda: intervalo E (3).

8º passo: tentar dividir E (impossível, pois só tem um elemento).

9º passo: dividir D em intervalo da direita: intervalo F (1).

10º passo: tentar dividir F (impossível, pois só tem um elemento).

INTERCALAR: temos E e F ordenados, intercala-os: temos D ordenado.

INTERCALAR: temos A e D ordenados, intercala-os: temos o vetor ordenado.

Como funciona o intercalar?

O algoritmo de intercalação recebe dois intervalos ordenados e compara-os. Considere o intervalo A ordenado (2, 4) e o intervalo D ordenado (1, 3).

1º passo: cria um vetor auxiliar com o tamanho de A + tamanho de D.

2º passo: compara 2 com 1. O número 1 é menor. Então copia 1 para a primeira posição do vetor auxiliar.

3º passo: compara 2 com 3. O número 2 é menor. Então copia 2 para a segunda posição do vetor auxiliar.

4º passo: compara 4 com 3.  O número 3 é menor. Então copia 3 para a terceira posição do vetor auxiliar.

5º passo: o vetor D já foi todo copiado. Então copia, em ordem, o restante do vetor A para as posições vazias do vetor auxiliar (no caso, 4 é copiado para a quarta posição do vetor auxiliar).

6º passo: copia o vetor auxiliar para o vetor original.

Performance

Seja o intervalo a ser ordenado com n números. Então a performance em todos os casos é θ(n*lg(n)). Por quê?

Quanto custa a intercalação: θ(n)

Quantos níveis a árvore de recursão alcança: θ(lg(n))

Lg é o log de base 2. Isso acontece, pois ocorre uma árvore de chamadas. Por exemplo:



O vetor original tem n elementos. Ocorrem lg(n) níveis abaixo. Em cada nível, diminui-se o número de elementos, dividindo-se por 2. Resolvendo esta recorrência, obtemos: θ(n*lg(n)).

Algoritmo



------------------------------- 
Fique por dentro das novidades curtindo-nos no Facebook e Twitter.

Sem comentários em " Merge Sort: implementação em java "

Por favor, clique apenas uma vez no botão de publicar comentário e espere carregar. Evite a duplicação deles!

Obrigado pela participação!