27 de dezembro de 2023
Algoritmo: Merge Sort
Algoritmos
Lógica
Merge sort é um algoritmo eficiente para ordenar uma lista de elementos. Ele utiliza uma estratégia chamada dividir e conquistar, que recursivamente quebra o problema em partes menores para poder “resolver” essas partes e depois agrupá-las adequadamente.
Por exemplo, dado uma lista de 7 elementos, vamos separar os 4 primeiros em uma lista temporária e os 3 últimos elementos em outra. Vamos dividir novamente cada parte até termos 7 itens individuais.
Depois, podemos comparar o primeiro elemento com o segundo e fazer um merge em uma nova lista dupla temporária na ordem correta. Fazemos isso com o terceiro e quarto, quinto e sexto, e deixando o 7 sozinho por enquanto. Quando só tivermos listas duplas (e algum item sozinho no caso de tamanhos ímpares), vamos agrupar essas 3 listas duplas de 2 elementos (mais o sétimo elemento) em 2 listas, de tamanho 4 e 3. E finalmente vamos mesclar em uma única do tamanho original 7 devidamente ordenada.
A imagem abaixo ilustra essa lógica:
Implementação
Na linguagem C, Merge sort pode ser implementado dessa maneira:
1#include <stdio.h>
2#include <stdlib.h>
3#include <math.h>
4
5void *merge_sort(int numbers[], int begin, int end)
6{
7 if (begin < end) // {1}
8 {
9 int mid = begin + (end - begin) / 2; // {2}
10 merge_sort(numbers, begin, mid); // {3}
11 merge_sort(numbers, mid + 1, end); // {4}
12
13 merge(numbers, begin, mid, end); // {5}
14 }
15}{1} Quando a posição inicial da lista for igual à posição final, significa que possui apenas um elemento, o que de fato é o que queremos. Enquanto isso não acontece, vamos continuar “dividindo para conquistar”.
{2} Vamos encontrar o meio da lista para poder dividir a lista em duas partes.
{3}, {4} Passamos recursivamente a mesma função para ambas as partes da lista.
{5} No final, ao dividir todos os elementos, podemos fazer um merge. A função merge pega duas listas e as agrupam na ordem correta, como no código abaixo:
1void *merge(int numbers[], int begin, int mid, int end)
2{
3 int left_size = mid - begin + 1; // {1}
4 int right_size = end - mid; // {2}
5
6 int left[left_size], right[right_size]; // {3}
7
8 for (size_t i = 0; i < left_size; i++) // {4}
9 {
10 left[i] = numbers[begin + i];
11 };
12
13 for (size_t i = 0; i < right_size; i++) // {5}
14 {
15 right[i] = numbers[mid + i + 1];
16 };
17
18 int i = 0; // {6}
19 int j = 0; // {7}
20 int k = begin; // {8}
21
22 while (j < left_size && i < right_size) // {9}
23 {
24 if (left[j] <= right[i]) // {10}
25 {
26 numbers[k] = left[j]; // {11}
27 j++; // {12}
28 }
29 else
30 {
31 numbers[k] = right[i]; // {13}
32 i++;
33 }
34 k++; // {14}
35 }
36
37 while (j < left_size) // {15}
38 {
39 numbers[k] = left[j];
40 j++;
41 k++;
42 }
43
44 while (i < right_size) // {16}
45 {
46 numbers[k] = right[i];
47 i++;
48 k++;
49 }
50}{1}, {2} Vamos calcular o tamanho das duas listas.
{3} Declaramos elas como “left” e “right”.
{4}, {5} Copiamos a porção correspondente para right e left em cada lista pegando da lista original.
{6} i é posição atual que estamos analisando da lista right. {7} j é da lista left. Esses números nos dizem quais são os elementos em cada lista que estamos observando no momento. {8} é a posição da lista que estamos observando, vamos começar na posição inicial “begin”.
{9} Aqui está a parte mais lógica do merge. Enquanto a posição atual da lista right for menor que seu tamanho ou que a posição atual da lista left seja também menor que seu tamanho, iremos verificar se o elemento correspondente da lista left é menor que o elemento da lista right {10}.
Se isso for verdade, esse será armazenado na lista {11} e passamos para a próximo posição de left {12}.
Se não for verdade, ou seja, o correspondente de right for menor, fazemos o mesmo passo anterior, porém para a lista right {13}.
{14} A cada laço aumentamos 1 na posição da lista que está sendo ordenada. Os dois últimos laços {15} e {16} são para pegar “sobras” de right ou de left. (Releia a linha {9}).
Executando
1#include <stdio.h>
2#include "src/merge_sort.h"
3#include "utils/print_array.h"
4
5int main()
6{
7 int numbers[] = {1, 1, 1, 1, 3, 0, 0, 2, 4, 1000, 1, 7, 0, 1, 3};
8 int length = sizeof(numbers) / sizeof(numbers[0]);
9
10 merge_sort(numbers, 0, length - 1);
11 print_array(numbers, length);
12}1Output: 0 0 0 1 1 1 1 1 1 2 3 3 4 7 1000Tempo de execução
Em seu pior caso de execução, Merge sort possui o tempo de O(n*logn). Um tempo de execução muito menor que Insertion sort e Selection sort.
Referência
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009.
Fonte do diagrama: File:Merge sort algorithm diagram.svg - Wikipedia
