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