Merge Sort

O Merge Sort é um algoritmo de ordenação, onde sua fundamentação esta na junção, ou melhor, na possibilidade de mesclar vetores.

Mas antes de mesclar vetores, temos de quebrar o vetor original no meio, e continuando a repartí-lo até chegarmos em vetores de uma única posição, isolando cada elemento. Uma vez com cada elemento isolado, temos de compará-los com o seu par e agrupá-los de forma ordenada em um vetor temporário. Então mesclamos os vetores, sempre comparando seus elementos, de forma que o novo vetor criado seja sempre ordenado.

Antes de destruir o vetor temporário ordenado (que deve ser criado usando alocação dinâmica de memória com o malloc(), e liberado com o free(), pois não sabemos quantos e quais os tamanhos dos vetores temporários que serão criados), devemos copiar os itens para o vetor original.

A vantagem deste método é que, ao criamos um vetor, garantimos que os elementos menores sempre sejam os últimos, gastando menos tempo na hora de mesclar dois vetores, gerando menos computação.

Acompanhe seu funcionamento no vídeo a seguir:

Este algoritmo recursivo que é classificado como “dividir para conquistar”. Para essa afirmação temos:

• Dividir os dados em subseqüências pequenas.
• Conquistar, ou seja, classifica as duas metades recursivamente.
• Combinar as duas metades em um único conjunto ordenado.

Foi criado por Von Neumann em 1945.

O Legal nele é que exploramos a alocação de memória e a recursividade.

Veja um exemplo de sua implmentação:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>

void Merge(int vetor[], int tamanho)
{
    // -> cria um novo vetor com tamanho compatível
    int* temp = (int*) malloc(tamanho * sizeof(int));
   
    int meio = tamanho / 2;
    int i = 0;
    int j = meio;
    int k = 0;

    // -> troca os itens entre as metades
    while (i < meio && j < tamanho)
    {
        if (vetor[i] < vetor[j])
        {
            temp[k] = vetor[i];
            ++i;
        }
        else
        {
            temp[k] = vetor[j];
            ++j;
        }
        ++k;
    }

    if (i == meio) // -> termina de copiar a segunda metade
    {
        while (j < tamanho)
        {
            temp[k] = vetor[j];
            ++j;
            ++k;
        }
    }
    else // -> termina de copiar o início
    {
        while (i < meio)
        {
            temp[k] = vetor[i];
            ++i;
            ++k;
        }
    }

    // -> copia os itens ordenados para o vetor original
    for (i = 0; i < tamanho; ++i)
    {
        vetor[i] = temp[i];
    }

    // -> Libera a mamórtia do vetor temporário
    free(temp);
}

void MergeSort(int vetor[], int tamanho)
{
    if (tamanho > 1)
    {
        int meio = tamanho / 2; // -> divide o vetor no meio
        MergeSort(vetor, meio); // -> passa a primeira metade
        MergeSort(vetor + meio, tamanho - meio); // -> passa a segunda metade
        Merge(vetor, tamanho); // -> ordena e mescla
    }
}

void Listar(int vetor[], int tamanho)
{
    for (int i = 0; i < tamanho; i++)
    {
        printf("%i\n", vetor[i]);
    }
}

void main()
{   
    srand(time(NULL));

    const int TAMANHO_TOTAL = 11;
    int vetor[TAMANHO_TOTAL];

    for(int i = 0; i < TAMANHO_TOTAL; i++)
    {
        vetor[i] = rand();
    }

    printf("Vetor Gerado:\n");
    Listar(vetor, TAMANHO_TOTAL);

    MergeSort(vetor, TAMANHO_TOTAL);
    printf("__________________\n");
    printf("Vetor Ordenado:\n");
    Listar(vetor, TAMANHO_TOTAL);

    system("pause");
}

Bem, agora fica o exercício:

• Implemente um programa, utilizando a linguagem C, que leia 5 ou 11 alunos (composto por: RA, Nome, Ano de Nascimento). Após ler, o usuário irá escolher um tipo de relatório/listagem em tela, podendo ser ordenado por cada um dos atributos do aluno de forma crescente ou decrescente.