Existe na literatura diversos algoritmos de ordenação. Nesta aula vamos aprender como ordenar um vetor de inteiros com Portugol.

Na literatura o algoritmo que vamos aprender aqui é chamado de Bubble Sort ou algoritmo bolha. Ele recebe esse nome por causa de seu comportamento. Se imaginarmos a estrutura de um vetor na vertical, o algoritmo “carrega” o maior elemento para o final do vetor, subindo, como uma bolha dentro d’água.

Inicialmente vamos sortear valores aleatórios enter 1 e 100 para preencher nosso vetor utilizando a função sorteia da biblioteca Util.

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

Na sequência, vamos imprimir o vetor preenchido para ter certeza da desordem de seus valores.

		para(i = 0; i < tam; i++)
			escreva(vet[i], ",")

Agora, vamos a uma primeira versão do algoritmo Bubble Sort. A ideia central do algoritmo é para cada elemento da posição i, compará-lo com o elemento seguinte. Se o elemento i for maior que o seguinte, então trocamos os dois elementos, caso contrário passamos para o próximo.

Observe que, como cada elemento i é comparado com o seguinte, precisamos parar na penúltima posição do vetor (tam – 1), que será comparada com a última.

Ao percorrer o vetor completo uma vez, teremos colocado apenas um elemento em seu devido lugar. Assim, se nosso vetor tiver tamanho 10, precisamos repetir isso 10 vezes no pior caso, por isso a repetição externa de 1 até tam.

		para(j = 1; j <= tam; j++){
			para(i = 0; i < tam - 1; i++){
				se(vet[i] > vet[i+1]){
					copia = vet[i]
					vet[i] = vet[i+1]
					vet[i+1] = copia
				}
			}
		}

Este algoritmo funciona muito bem para vetores pequenos, que são ordenados rapidamente, mas não para vetores grandes, onde o algoritmo se torna extremamente demorado.

Para melhorar (um pouco) o desempenho do Bubble Sort, podemos trocar a repetição do tipo para por uma repetição do tipo enquanto. Repita enquanto for feito ao menos uma troca. Assim, quando o vetor já estiver ordenado, nenhuma troca será feita, finalizando a repetição.

		faca{
			troca = 0
			para(i = 0; i < tam - 1; i++){
				se(vet[i] > vet[i+1]){
					copia = vet[i]
					vet[i] = vet[i+1]
					vet[i+1] = copia
					troca = 1
				}
			}
		}enquanto(troca == 1)

Código completo em Portugol para o algoritmo de ordenação Bubble Sort

programa{

	inclua biblioteca Util
	
/*
	Aula 125: Como ordenar um vetor de inteiros

	Código escrito por Wagner Gaspar
	Abril de 2021
*/
	
	funcao inicio(){
		inteiro i, j, copia, troca = 0, tam = 40, vet[50]

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

		para(i = 0; i < tam; i++)
			escreva(vet[i], ",")

		// primeira versão (remover o comentário a seguir para testar)
		/*
		para(j = 1; j <= tam; j++){
			para(i = 0; i < tam - 1; i++){
				se(vet[i] > vet[i+1]){
					copia = vet[i]
					vet[i] = vet[i+1]
					vet[i+1] = copia
				}
			}
		}
		*/

		// segunda versão
		faca{
			troca = 0
			para(i = 0; i < tam - 1; i++){
				se(vet[i] > vet[i+1]){
					copia = vet[i]
					vet[i] = vet[i+1]
					vet[i+1] = copia
					troca = 1
				}
			}
		}enquanto(troca == 1)

		escreva("\n")
		para(i = 0; i < tam; i++)
			escreva(vet[i], ",")
	}
}