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

No último post, comecei a falar sobre o BubbleSort, e apresentei uma análise do algoritmo e uma implementação. Mas até ali, fizemos algo muito simples. O que vamos fazer agora é melhorar um pouco aquela implementação.
Como vocês bem se lembram, o nosso algoritmo executava sempre n² operações. O que vamos fazer é acrescentar algumas verificações que permitam que, na maioria dos casos, o algoritmo termine antes disso.

Para isso, vamos lembrar do algoritmo (apenas a função que implementa o BubbleSort:

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;
            }
        }
    }
}

E as duas primeiras iterações dele no nosso vetor de exemplo:

[ 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]


Da primeira iteração a gente não consegue escapar, pois ainda não fizemos nenhuma varredura por todo o vetor, e ainda não temos noção do que podemos encontrar. Mas a partir daí, podemos perceber, tanto pelo código quanto pelos exemplos que o maior valor do vetor está subindo até o final.

Qual seria o sentido então de permitir que, por exemplo, na 2ª iteração, o 13 que está subindo seja comparado com o 14 que foi colocado no fim do vetor na iteração anterior? Ele jamais será maior. (Veja a iteração sublinhada)

Espertos que somos, vamos ensinar o nosso programa a perceber e ignorar esses passos redundantes. Tente fazer por conta própria. Depois olhe abaixo para verificar se você fez certo ou para entender como se faz.

No programa, temos a variável i que controla o loop externo e “burramente” determina que o loop seja executado n vezes. O que faremos é: Em vez de ela simplesmente controlar o loop, vamos atribuir também a ela o papel de determinar até aonde no vetor o loop interno ainda precisa realizar as suas verificações.

Para isso, em vez de inicializál-la em 0 e fazê-la crescer até n, vamos inicializá-la em n, e decrementá-la até que alcancemos o valor 0. E que tal agora se fizermos o loop interno, que varre o vetor até a posição n-1, varrer apenas até a posição i-1? Será que funciona? É fácil perceber que sim (talvez você queira voltar alguns parágrafos, onde eu explico o porque).

Agora, nosso código ficará com a seguinte cara:

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

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

Será que obtivemos alguma melhora com isso? Vamos voltar ao nosso pior caso (um vetor em ordem decrescente) e pensar a respeito.

Na primeira iteração, teremos n-1 operações. Já na segunda, teremos no máximo n-2, já que o limite superior da parte do vetor a ser avaliada foi reduzido de 1. Generalizando esse raciocínio, teremos o seguinte número de operações:

`(n-1) + (n-2) + \ldots` `+ 1`

Pra quem se lembra, a soma dessa PA nos dará

`S = [(n-1) * ((n-1) + 1)] / [2]`
`S = [n * (n-1)]/[2]`

O que quer dizer que reduzimos o numero máximo de iterações a menos da metade! Ou seja: para um BubbleSort, essa melhoria é bastante significativa. (Não acredite 100% nisso ainda. Vamos falar mais sobre essa “melhoria” em alguns instantes).

Ainda temos mais um acerto para fazer, e a idéia é a seguinte. Será que precisamos continuar o algoritmo se, em alguma iteração, não acontecer nenhuma troca? Espero que você consiga perceber que não. O que vamos fazer então é adicionar uma flag ao programa, que começa como false a cada iteração do loop externo e é setada para true assim que ocorre uma troca no loop interno. Ao fim do loop interno, caso a flag ainda seja false, o algoritmo pode encerrar.

Com isso, nosso código ficará assim:

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

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

Repare que esta última modificação não melhora a performance, mas vai permitir que, na maior parte das vezes, que economizemos algumas operações.

Agora sim, temos uma versão aceitável para o BubbleSort!

Agora, retomemos a discussão sobre a melhoria que geramos com a primeira modificação: Na pratica, nós teremos sempre o número de operações reduzidas por um fator de aproximadamente ½. Apesar disso, quando falamos de complexidade de um algoritmo, esta melhoria é irrelevante.

Você deve estar se perguntando: "Mas, irrelevante? Por quê?" (Eu também me perguntei...)

Mesmo com a melhoria, ainda temos lá no resultado do numero de operações um termo `n^2`. Como estamos analisando um algoritmo que resolve um problema para vetores de qualquer tamanho, talvez você queira se perguntar como a função

`f(n) = [n*(n-1)] / [2]`

se comporta conforme n cresce arbitrariamente.

O que acontece é que a diminuição gerada pelo fator `½` vai se tornando cada vez mais irrelevante, pois é uma constante. Se você quiser, pode pensar em uma analogia (que na verdade não é uma analogia) com o cálculo.

`lim_(n->\infty)(n²) = ?`    ou    `lim_(n->\infty)((n² - n) / 2) = ?`

Este é o principio que se aplica aqui. Em ambos os casos, o resultado é `\infty`.

O que estou querendo dizer é: Quando se fala de complexidade de algoritmos, multiplicar, somar, dividir ou qualquer outra operação que envolva uma constante é irrelevante.

Temos então que: `O( [n*(n-1)]/[2] ) = O( [(n^2 - n)] / [2] ) = O(n^2)`

E na verdade, acabamos não ganhando nada em termos teóricos com essas melhorias. (Mas não se esqueça: De fato o número de operações diminui!).

Bem, isso é o que eu sei sobre BubbleSort. Na seqüência da série, falaremos sobre o MergeSort, um algoritmo que tem uma cara bem diferente do que vimos até aqui. No entanto, acho que vou fazer uma pausa antes, e falar sobre alguns assuntos que precisamos conhecer antes de falar sobre o MergeSort.

É isso aí, até mais!
Xico.