Bubble Sort

Bubble Sort, ou ordenação da bolha, é um algoritmo de ordenação, baseado em trocas. É de fácil implementação e relativo desempenho satisfatório em pequenas coleções de dados. Porém pode gerar muitas computações em grandes coleções de dados, pois ele tem que analisar elemento por elemento, de forma exponencial, para verificar se é necessário realizar a troca.

Sua ideia consiste em analisar elemento a elemento de forma a colocar o extremo em seu lugar, e desconsiderá-lo na próxima varredura. Por exemplo, se a implementação tiver como base analisar pares de forma a descobrir o maior elemento, o maior elemento pode ser jogado para o fim da coleção, sendo desconsiderado na próxima iteração.

“A ideia é percorrer um vetor diversas vezes,e a cada passagem fazer flutuar, para o topo, o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.”

Veja no vídeo a seguir um pouco da ilustração de seu funcionamento:

O bubble sort tem os seguintes passos:

1. Compara elementos adjacentes. Se o primeiro é maior do que o segundo, troca eles.
2. Faz isto para cada par de elementos adjacentes, começando com os dois primeiros e terminando com os dois últimos. Neste ponto o último elemento deve ser o maior de todos.
3. Repete os passos para todos os elementos exceto para o último.
4. Continua repetindo, cada vez com um elemento a menso, até não existam mais pares para se comparar.

Uma breve implementação:

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

const int tamanho = 10;

void BubbleSort(int vetor[])
{
    for (int i = tamanho - 1; i > 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (vetor[j] > vetor[j + 1])
            {
                int temp = vetor[j];
                vetor[j] = vetor[j+1];
                vetor[j+1] = temp;
            }
        }
    }
}

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

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

    int vetor[tamanho];

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

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

    BubbleSort(vetor);
    printf("__________________\n");
    printf("Vetor Ordenado:\n");
    Listar(vetor);

    system("pause");
}

Percebam que é bem simples, sem recursividade, ponteiro ou qualquer outro artifício mais complexo. Bastam dois for. O mais abrangente limita as comparações, deixando de fora sempre o ultimo item ordenado, tendo em vista que ele foi o maior. O for de dentro compara os pares e faz a troca se necessário.

E vamos ao exercícios:

• 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.

Espero que tenham gostado