Algoritmos de Ordenação em C: Bolha, Seleção, Inserção e Fusão

A seguir estão implementações de quatro algoritmos clássicos de ordenação, escritos em linguagem C, com o código revisado e corrigido.

1. Ordenação por Bolha (Bubble Sort)

A função bolha() percorre o vetor repetidamente, trocando elementos adjacentes fora de ordem, até que nenhuma troca seja necessária.

void bolha()
{
    for (int i = 0; i < qtde; i++)
    {
        strcpy(vra[i].ra, vetor[i].ra);
        vra[i].aponta = i;
    } // for

    int flag, auxi;
    char aux[7];

    while (1)
    {
        flag = 0;
        for (int i = 0; i < qtde - 1; i++)
        {
            if (strcmp(vra[i].ra, vra[i + 1].ra) > 0)
            {
                // troca (swap)
                flag = 1;
                strcpy(aux, vra[i].ra);
                strcpy(vra[i].ra, vra[i + 1].ra);
                strcpy(vra[i + 1].ra, aux);
                auxi = vra[i].aponta;
                vra[i].aponta = vra[i + 1].aponta;
                vra[i + 1].aponta = auxi;
            }
        } // for
        if (flag == 0) break;
    } // while (1)
}

2. Ordenação por Seleção (Selection Sort)

A função selecao() encontra o menor elemento do restante do vetor e o posiciona na posição atual.

void selecao()
{
    int menor, pm;
    for (int j = 0; j < (qtde - 1); j++)
    {
        menor = vetor[j];
        pm = j;
        for (int i = j + 1; i < qtde; i++)
        {
            if (vetor[i] < menor)
            {
                menor = vetor[i];
                pm = i;
            }
        }
        trocas(vetor[j], vetor[pm]);
    }
} // selecao

3. Ordenação por Inserção (Insertion Sort)

A função insercao() constrói o vetor ordenado inserindo cada elemento em sua posição correta.

void insercao()
{
    int inicio = 1;
    for (int i = 0; i < qtde; i++)
    {
        strcpy(vra[i].ra, vetor[i].ra);
        vra[i].aponta = i;
    } // for

    for (int i = inicio; i < qtde; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (strcmp(vra[j].ra, vra[j - 1].ra) < 0)
                troca(&vra[j], &vra[j - 1]);
            else
                break;
        }
    } // for
} // insercao

4. Ordenação por Fusão (Merge Sort)

A função fusao() intercala duas metades já ordenadas de um vetor, utilizando um vetor auxiliar.

void fusao(int inicio, int meio, int fim)
{
    int esq = inicio, dir = meio + 1, k = 0, i;

    while (esq <= meio && dir <= fim)
    {
        if (vetor[esq] < vetor[dir])
        {
            aux[k] = vetor[esq];
            esq++;
        }
        else
        {
            aux[k] = vetor[dir];
            dir++;
        }
        k++;
    } // while

    if (esq > meio)
        for (i = dir; i <= fim; i++)
            aux[k++] = vetor[i];
    else
        for (i = esq; i <= meio; i++)
            aux[k++] = vetor[i];

    for (i = 0; i < k; i++)
        vetor[inicio + i] = aux[i];
} // fusao