Merge Sort

O Merge Sort, assim como o Quick Sort, é um algoritmo de ordenação eficiente, que implementa o princípio dividir para conquistar. Uma diferença importante entre esses algoritmos consiste no fato de que o Merge Sort precisa de memória adicional para fazer a ordenação do vetor.

A compreensão da execução deste algoritmo também pode ser um pouco complexa. Portanto, é importante que você também leia o algoritmo de forma atenta, executando cada etapa manualmente para compreender o papel de cada comando implementado.

🎬 Vídeo

🤯 Entendendo a ideia

🔁 A parte recursiva

  1. A função mergeSort recebe um vetor e dois índices: um para inicio, outro para o fim (última posição válida do vetor).
  2. Em seguida, verifica se o índice de inicio é menor que o índice de fim. Se não, a função retorna, indicando que o vetor já está ordenado.
  3. Calcula o índice do meio como a média aritmética entre os índices de inicio e fim.
  4. Chama recursivamente a função mergeSort para ordenar os subvetores à esquerda e à direita do meio.
  5. Chama a função intercalar para combinar (intercalar) os subvetores ordenados, usando os índices de inicio, meio e fim. Isso resulta na ordenação do vetor original entre os índices de início e fim.

🔀 A intercalação do vetor

  1. A função intercalar recebe um vetor e três índices: inicio, meio e fim.
  2. É definido o tamanho (TAM) do vetor a ser intercalado, com base nos índices de inicio e fim.
  3. São declaradas variáveis locais a, b e pos para controlar as posições nos subvetores.

As variáveis a e b são inicializadas, respectivamente, com os índices de inicio e meio + 1. A variável pos é inicializada como 0.

Entra em um loop enquanto a<=meio e b<=fim. Dentro do loop, compara os elementos nas posições a e b:

  • Se o elemento em a é menor ou igual ao elemento em b, o valor em a é copiado para o vetor auxiliar (aux) na posição pos, e a é incrementado.
  • Caso contrário, o valor em b é copiado, e b é incrementado. A posição pos também é incrementada.

Após o loop:

  • verifica-se se há elementos restantes no subvetor esquerdo (entre inicio e meio). Se sim, esses elementos são copiados para o vetor auxiliar.
  • verifica-se se há elementos restantes no subvetor direito (entre meio+1 e fim). Se sim, esses elementos também são copiados para o vetor auxiliar.

Finalmente, os elementos do vetor auxiliar são copiados de volta para o vetor original (vet) a partir do índice inicio.

👩🏾‍💻 A implementação

void intercalar(int vet[], int inicio, int meio, int fim){
    int a, b, pos;
    int TAM = fim-inicio + 1;
    int aux[TAM];

    a = inicio;
    b = meio + 1;
    pos = 0;
    
    while(a <= meio && b <= fim){
        if(vet[a] <= vet[b]){
            aux[pos] = vet[a];
            a++;
        }
        else{
            aux[pos] = vet[b];
            b++;
        }
        pos++;
    }

    for(int i = a; i <= meio; i++){
        aux[pos] = vet[i];
        pos++;
    }

    for(int i = b; i <= fim; i++){
        aux[pos] = vet[i];
        pos++;
    }

    for(int i = inicio; i<=fim; i++){
        vet[i] = aux[i-inicio];
    }
}

void mergeSort(int vet[], int inicio, int fim){
    if(inicio<fim){      
        int meio = (inicio+fim)/2;
        mergeSort(vet,inicio,meio);
        mergeSort(vet,meio+1,fim);
        intercalar(vet,inicio,meio,fim);
    }
}
Nesta página