Um Algoritmo Simples de Ordenação

Ordenação é um dos inúmeros problemas clássicos da computação com diversas variações, algumas mais simples, outras mais complexas. Vou apresentar aqui uma das versões mais simples e, claro, não é a mais eficiente.

Na literatura este algoritmo é conhecido por algoritmo bolha ou bubble sort. Ele recebe este nome por causa de seu funcionamento. Imaginando um vetor na vertical, basicamente o que o algoritmo faz é percorrer o vetor várias vezes levando o maior elemento para o topo, como uma bolha de ar que vai subindo do fundo de uma lago.

Os passos poderiam ser descritos da seguinte forma:

1 – percorrer o vetor até a penúltima posição executando os passos 2 e 3;
2 – comparar cada posição i com a posição seguinte (i + 1);
3 – se o elemento da posição i for maior que o seguinte, então os dois são trocados de posição;
4 – quando todo o vetor tiver sido percorrido, verificar:
5 – se foi realizado ao menos uma troca, voltar o passo 1;
6 – senão, finalizar.

Abaixo apresento uma codificação desse algoritmo em Portugol. Criei um vetor de inteiros de tamanho 15, e três variáveis inteiras, i para a estrutura de repetição para, auxiliar para realizar a troca de posição dos elementos do vetor e, por fim, trocou, para sinalizar se devemos percorrer o vetor mais uma vez ou não.

Em seguida, fazemos uma repetição para sortear números entre 1 a 100 e popular nosso vetor, imprimirmos na tela o vetor gerado e, então iniciamos o processo de ordenação, realizando exatamente cada um dos passos descritos acima.

1 – enquanto houver ao menos uma troca (o valor 1 na variável trocou possui essa informação), a variável trocou, que iniciou com o valor 1, recebe o valor 0;

2 – todo o vetor é percorrido até a penúltima posição (a penúltima posição será comparada com a última posição, por isso não podemos percorrer o vetor até a última posição);

3 – se o elemento da posição i for maior que o seguinte, trocar os dois elementos de posição e alterar o valor da variável trocou para 1;

Por fim, escrevemos outro para para imprimir o vetor agora ordenado.

programa
{
	inclua biblioteca Util
	funcao inicio()
	{
		inteiro vet[15], i, auxiliar, trocou = 1

		para(i = 0; i < 15; i++){
			vet[i] = Util.sorteia(1, 100)
		}

		escreva("Vetor gerado: ")
		para(i = 0; i < 15; i++){
			escreva(vet[i], " ")
		}
		escreva("\n")
		enquanto(trocou == 1){
			trocou = 0
			para(i = 0; i < 15 - 1 ; i++){
				se(vet[i] > vet[i+1]){
					auxiliar = vet[i]
					vet[i] = vet[i+1]
					vet[i+1] = auxiliar
					trocou = 1
				}
			}
		}
		escreva("\nVetor ordenado: ")
		para(i = 0; i < 15; i++){
			escreva(vet[i], " ")
		}
		escreva("\n")
	}
}

A seguir apresentamos um print da execução no ambiente de programação Portugol Studio.