Ordenação – Métodos e análises: BubbleSort – Parte 1

Nesta seqüência de 3 (ou mais) posts, minha intenção é falar um pouco sobre algoritmos de ordenação. Mais do que isso, queria focar um pouco na análise, mas também sem esquecer da implementação, para a qual usarei a linguagem C. Como eu disse no post de reapresentação, todo o conteúdo deste Blog, pelo menos por hora, é introdutório, logo voltado para pessoas que estão começando a se enveredar pelo mundo dos algoritmos.

O problema é muito simples, e é algo que nós fazemos o tempo todo, naturalmente: Dada uma seqüência de elementos comparáveis (ou seja, para os quais se tenha a noção de ordem), ordená-los da forma mais eficiente possível. Isto é: Dada uma seqüência de elementos

`a_1,\quad a_2,\quad a_3,\quad \ldots\quad, a_n`

Queremos um rearranjo desses elementos tal que

`a_1 \quad\le\quad a_2 \quad\le\quad a_3 \quad\le\quad \ldots \quad\le\quad a_n`

Em todos os exemplos, vamos mexer com vetores de números inteiros, mas lembre-se que os conceitos que vamos trabalhar são mais gerais do que isso, podendo ser aplicados para ordenar qualquer coisa.

O problema da Ordenação (ou sorting, em inglês) é um problema sobre o qual se quebrou muito a cabeça na computação, mas que hoje (na verdade há um bom tempo) é um assunto pra lá de resolvido. Apesar disso, ainda são desenvolvidos novos algoritmos de ordenação com propósitos específicos, mas que não vem ao caso para nós.

Vamos ao que interessa: Existem dezenas de diferentes métodos de ordenação, mas vou falar especificamente de 3, que pra mim sintetizam alguns dos conceitos mais importantes, para resolver este problema (tecnicamente) simples, e que posteriormente podem ser usados em muitas outras situações.

Vamos começar (obviamente) do começo. O BubbleSort, ou “método da Bolha”, na tradução que comumente se vê por aí. Ele é um algoritmo baseado em trocas (swapping) e é o assunto deste primeiro post, por ser o mais simples de todos. Esse algoritmo foi proposto em 1956, o que nos permite dizer que ele é um senhor algoritmo (piadinha infame...).

Qual é a idéia: “Varrer” (percorrer) o vetor várias vezes. A cada vez que varremos o vetor, vamos levando o maior elemento que encontrarmos pelo caminho para o final, até que nenhum deles precise mais mudar de posição. Na analogia da bolha, os números vão “subindo” (como uma bolha no fundo de um recipiente com água) até o fim do vetor, em ordem decrescente de tamanho.

Um pseudo-código, sem nenhum tipo de otimização para resolver o problema, poderia ser:

BubbleSort( vetor v, tamanho n) : Retorna Vetor ordenado.
   Repita n vezes
      Repita a partir do inicio do vetor, até o seu final
         Se vetor[c] > vetor[c+1] , troque-os de posição.

Vejamos como seria o passo-a-passo desse algoritmo para ordenar a seguinte lista de elementos:
[5, 13, 2, 7, 11, 14, 6]


[ 5, 13, 2, 7, 11, 14, 6]
[ 5, 13, 2, 7, 11, 14, 6]
[ 5, 2, 13, 7, 11, 14, 6]
[ 5, 2, 7, 13, 11, 14, 6]
[ 5, 2, 7, 11, 13, 14, 6]
[ 5, 2, 7, 11, 13, 14, 6]

[ 5, 2, 7, 11, 13, 6, 14]
[ 2, 5, 7, 11, 13, 6, 14]
[ 2, 5, 7, 11, 13, 6, 14]
[ 2, 5, 7, 11, 13, 6, 14]
[ 2, 5, 7, 11, 13, 6, 14]
[ 2, 5, 7, 11, 6, 13, 14]

[ 2, 5, 7, 11, 6, 13, 14]
[ 2, 5, 7, 11, 6, 13, 14]
[ 2, 5, 7, 11, 6, 13, 14]
[ 2, 5, 7, 11, 6, 13, 14]
[ 2, 5, 7, 6, 11, 13, 14]
[ 2, 5, 7, 6, 11, 13, 14]

[ 2, 5, 7, 6, 11, 13, 14]
[ 2, 5, 7, 6, 11, 13, 14]
[ 2, 5, 7, 6, 11, 13, 14]
[ 2, 5, 6, 7, 11, 13, 14] -- Coincidentemente, aqui o vetor já está ordenado.
[ 2, 5, 6, 7, 11, 13, 14]
[ 2, 5, 6, 7, 11, 13, 14]

Obs: O negrito vermelho sinaliza que, na próxima iteração as referidas posições terão sido trocadas, e apenas negrito uma comparação para a qual os elementos já estão em ordem. Note também que o algoritmo não parou assim que o vetor ficou ordenado, pois computador não tem como saber que essa condição foi alcançada (não com o algoritmo que fornecemos para ele). Ele continuará a fazer o que você o instruiu através do pseudo-código.

E.... isso é um BubbleSort! Parece bonitinho e tal, mas já vamos analisar um pouco melhor como esse algoritmo se comporta. Enquanto isso, vamos pensar em algumas coisas importantes. Tente responder essas perguntas para si mesmo, ou escreva as respostas em papel:

1 – E se o vetor fornecido para o algoritmo estivesse em ordem decrescente?
2 – Quantas vezes passamos pela linha de código “Se vetor[c] > vetor[c+1] ...”?

Pense nessas perguntas por uns dois minutos, ou até que você encontre a resposta (esse seria o ideal. Dê a si mesmo a chance de usar o cérebro em vez de ficar só lendo.

Tic-Tac
.
.
.
Tic-Tac

Então... Como você deve ter percebido, se os números forem fornecidos em ordem decrescente, cada uma das comparações feitas dentro do loop interno irá gerar uma troca, e embora isso possa parecer inevitável, é extremamente ineficiente.


Agora sim, respondendo às perguntas:

1 – O programa vai entrar na condição ‘Se’ todas as vezes que passar lá.
2 – Temos um “Repita n vezes”, e dentro dele um loop que também ocorre n vezes. Logo, passaremos por essa linha n . n = n² vezes.

Obviamente, este é o pior caso possível para o nosso BubbleSort (no que diz respeito a executar o “Se”, já que inevitavelmente passaremos lá), pois é quando faremos todas as trocas possíveis. Agora, pare e pense um instante: n é o tamanho do vetor (quantos elementos há nele). Isso quer dizer que, se quisermos ordenar, digamos, 100 números com o BubbleSort, corremos o risco de ter que fazer até 10000 operações de troca!!!
O que se diz nesses casos é que o algoritmo tem complexidade (ou seja, executa um numero de operações) que é da ordem de n², onde n é o tamanho da entrada, e que no nosso caso é o tamanho do vetor. Mais comumente em computação, expressamos essa constatação dizendo que:

A complexidade de tempo do BubbleSort é O(n²).

Mais detalhes da “notação O”, eu fico devendo para uma próxima, embora eu vá mencioná-la em outros momentos. Por hora, basta saber que ele representa uma estimativa da ordem de grandeza do tempo de execução de um algoritmo qualquer (mas também existe notação O para expressar a complexidade de outras coisas, como espaço em memória que o algoritmo precisa pra "rodar").

Como vamos ver nos próximos posts, esse valor, mesmo levando-se em consideração o pior caso possível, pode ser melhorado (e muito!). Pra isso, precisamos “botar a caixola pra funcionar” e pensar em diferentes formas de atacar o problema.

Para terminar, mostro uma implementação em C relativa ao pseudo-código que apresentei antes, sem tirar nem pôr. No entanto, fiz um programa completo que você pode salvar e executar sem problemas. Lembrando que ele pode ser melhorado, e que eu o farei no próximo post (é, ainda tem mais!).

/*
    Autor: Francisco Viégas Vianna
    Data:  04/10/2009
    Descrição: Impementação do método de ordenação BubbleSort.

    Por favor, mantenha esse comentário.
*/

#include < stdio.h >

#define MAXT 1000

void bubbleSort( int *vet, int n )
{
    int i, j, aux;

    for( i=0; i < n; i++ )
    {
        for( j = 0; j < n-1; j++ )
        {
            if( vet[j] > vet[j+1] )
            {
                aux = vet[j];
                vet[j] = vet[j+1];
                vet[j+1] = aux;
            }
        }
    }
}

int main()
{
    int vetor[MAXT];
    int n, i;

    printf( "Quantos elementos (MAX = %d)? ", MAXT );
    scanf( "%d", &n );

    for( i=0; i < n; i++ )
    {
        scanf("%d", &( vetor[i]) );
    }

    bubbleSort( vetor, n );

    printf( "\nOrdenando o vetor:\n" );
    for( i=0; i < n; i++ )
    {
        printf( "%d ", vetor[i] );
    }
    return 0;
}

É isso aí. Até a próxima!