quinta-feira, 16 de abril de 2015

Programação em C - Merge Sort

Olá pessoal, seguindo com os nossos posts sobre implementações de algoritmos de ordenação, dessa vez iremos abordar o Merge Sort (ordenação por integração).

Já abordamos o Insertion Sort, Selection Sort, Bubble Sort e Heap Sort. O que deu mais trabalho desses 4 foi com certeza o Heap Sort, não que ela seja difícil de entender, pelo contrário, mas do ponto de vista de implementação é um pouquinho mais trabalhoso.

O Merge Sort também não é difícil o entendimento e a implementação não oferece tanta dificuldade. É importante que você tenha noção de recursão (recursão ocorre quando uma função faz chamada a si própria).

O Merge Sort e Quick Sort são métodos que fazem divisão e conquista. A diferença é que no Merge Sort, sempre divide o problema de forma balanceada (gerando subproblemas de mesmo tamanho) ao passo que o Quick Sort utiliza o conceito de pivô para dividir o problema em subproblemas.

Não precisa saber como funciona o Quick Sort, em um outro post iremos falar sobre ele, dê uma busca por "quick sort" (sem as aspas duplas) para encontrar posts sobre ele.

O algoritmo do Merge Sort é simples:

a) divida o conjunto de entrada em 2 subconjuntos.
b) ordene cada conjunto separadamente (recursão pára quando atinge subconjuntos com 1 elemento).
c) intercale os 2 subconjuntos ordenados em um único subconjunto.

Não entendeu? Calma, esse algoritmo foi só para introduzir a ideia do Merge Sort, iremos entendê-lo de outras formas.

O que seria intercalar?

Bem, veja esse conjunto de entrada dividido em duas partes (ambas já estão ordenadas):

1,2,4,6,    3,5,7,8

Vamos supor que temos um "i" iniciando de 0 e um "j" iniciando de 4. O vetor se chama "A".

Quem é o menor? A[i] ou A[j]?

A[i] = A[0] =1
A[j] = A[4] =3

É o 1, então coloca ele em um vetor e incrementa o "i".

vetor: 1
i = 1
j = 4

Quem é o menor? A[1] ou A[4] ?

A[1] = 2
A[7] = 3

É o 2, então coloca ele no vetor e incrementa o "i".

vetor: 1,  2
i = 2
j = 4

Quem é o menor? A[2] ou A[4] ?

A[2] = 4
A[4] = 3

É o 3, então coloca ele no vetor e incrementa o "j".

vetor: 1, 2, 3
i = 2
j =5

Quem é o menor? A[2] ou A[5] ?

A[2] = 4
A[5] = 5

É o 4, então coloca ele no vetor e incrementa o "i".

vetor: 1, 2, 3, 4
i = 3
j = 5

Quem é o menor? A[3] ou A[5] ?

A[3] = 6
A[5] = 5

É o 5, então coloca ele no vetor e incrementa o "j".

vetor: 1, 2, 3, 4, 5
i = 3
j = 6

Quem é o menor? A[3] ou A[6] ?

A[3] = 6
A[6] = 7

É o 6, então coloca ele no vetor e incrementa o "i".

vetor: 1, 2, 3, 4, 5, 6
i = 4
j = 6

Perceba que todos os elementos da primeira parte (1,2,4,6) já foram colocados, então eu só faço adicionar o "resto" dos elementos da segunda parte que ainda não foram adicionados que são os elementos 7 e 8. O vetor ficará assim:

vetor: 1, 2, 3, 4, 5, 6, 7, 8

Não entendeu? Calma, o código está bem comentado, mas antes assista a esse vídeo para entender melhor o Merge Sort, o código foi baseado nas explicações desse vídeo:


Melhorou? A explicação do vídeo é muito boa, com ela fica fácil entender o Merge Sort e implementar já que também foram mostrados códigos no vídeo. Veja a implementação do GeeksBR feita em C baseada nas explicações do vídeo anterior:


Qualquer que seja a entrada,  o Merge Sort terá complexidade theta nlogn. É indicado para aplicações que não podem tolerar um caso desfavorável. O Merge Sort também é estável, embora dependa da implementação.

As desvantagens é que utiliza memória auxiliar e na prática é mais lento que o quicksort no caso médio.

Assista a essa vídeo-aula que analisa o Merge Sort:


Quaisquer dúvidas deixem nos comentários, até a próxima!


Nenhum comentário: