Algoritmo: Bubble Sort

Vou iniciar uma série sobre algoritmos de ordenação, começando hoje pelo Bubble Sort, também conhecido como o método da bolha. Para facilitar, vamos pegar o seguinte caso: tenho um vetor de  inteiros chamado vet com os seguintes valores: {55, 76, 26, 64, 26, 80, 71, 46} e temos que organizar os números desse vetor em ordem crescente.

Vamos para o pseudocódigo:

01. var x,y,aux : INTEIRO   
02. PARA x=0 ATE vet.tamanho PASSO 1
03.     PARA y=x+1 ATE vet.tamanho PASSO 1
04.      SE(vet[x] > vet[y]) ENTAO
05.       var aux = vet[x]
06.       vet[x] = vet[y]
07.       vet[y] = aux
08.      FIMSE
09.     FIMPARA
10.    FIMPARA

Vamos para a explicação:

O Bubble Sort é um dos algoritmos mais simples de se implementar. Consiste em pegar a posição na ordem e procurar o valor correto daquela posição. Para isso, usamos dois indicadores (variáveis x e y) para percorrer o vetor. 
 
No pseudo-código, podemos ver dois PARAs (linha 02 e 03). O primeiro controla a variável x, a variável que indica qual posição está sendo analisada. O segundo controla a variável y, que faz a procura de um valor que possa ser substituido, que neste caso (ordenar do menor para o maior), são quaisquer números que sejam menores que o número da posição x. Note que o valor de y sempre será maior que o x, isso porque todas as posições anterior de x já estarão com seus valores encontrado.

O SE da linha 03 faz a verificação da condição, como mencionado anteriormente, neste caso é que se o número que está na posição x for maior que o número da posição y, então esses números deve ser trocados.

Para realizar a troca, precisaremos de uma variável auxiliar (aux) para armazenar temporariamente o valor que está na posição x. Uma vez feito isso, podemos sobreescrever a posição x com o valor da posição y. Por último, sobreescrevemos a posição y para guardar o valor que está na variável auxiliar, efetuando a troca de posição.

Para tentar esclarecer, vou usar imagens:

Usamos duas variáveis para percorrer o vetor, partindo do início.
Comparamos os dois valores
Se a condição não for verdadeira
A posição y verifica a próxima casa
Se a condição for verdadeira
Realize a troca, começando copiando o valor da posição x para o auxiliar
e depois copia o valor da posição y para a posição x
e finalmente copiando o valor guardado no auxiliar para a posição y
Depois segue para a próxima posição, seguindo os mesmos passos até o final do vetor



Depois que a variável y percorreu todo o vetor, a variável x é incrementada, e o processo se repete até que a variável x atinja a última posição.

Neste teste de mesa, vamos ver o vetor sendo ordenado conforme a variável x vai avançando para o final do vetor:

x	y	vet
1	2	{26,55,76,64,26,80,71,46}
1	3	{26,55,76,64,26,80,71,46}
1	4	{26,26,76,64,55,80,71,46}
1	5	{26,26,76,64,55,80,71,46}
1	6	{26,26,76,64,55,80,71,46}
1	7	{26,26,76,64,55,80,71,46}
2	3	{26,26,64,76,55,80,71,46}
2	4	{26,26,55,76,64,80,71,46}
2	5	{26,26,55,76,64,80,71,46}
2	6	{26,26,55,76,64,80,71,46}
2	7	{26,26,46,76,64,80,71,55}
3	4	{26,26,46,64,76,80,71,55}
3	5	{26,26,46,64,76,80,71,55}
3	6	{26,26,46,64,76,80,71,55}
3	7	{26,26,46,55,76,80,71,64}
4	5	{26,26,46,55,76,80,71,64}
4	6	{26,26,46,55,71,80,76,64}
4	7	{26,26,46,55,64,80,71,76}
5	6	{26,26,46,55,64,71,80,76}
5	7	{26,26,46,55,64,71,80,76}
6	7	{26,26,46,55,64,71,76,80}
7	8	{26,26,46,55,64,71,76,80}