Nas aulas anteriores do nosso Curso de Algoritmos e Lógica de Programação aprendemos como funciona os algoritmos de ordenação BUBBLE SORTE e SELECTION SORT. Nesta aula vamos aprender como ordenar um vetor com o algoritmo INSERTION SORT, Ordenação por inserção.

Como o nome sugere, este algoritmo ordena o vetor inserindo os elementos na posição correta.

A verificação começa a partir do segundo elemento do vetor (i = 1). É feito uma cópia deste elemento para a variável copia. Este segundo elemento, copiado para a variável copia, será comparado com os anteriores (neste caso há apenas 1). Se o anterior for maior, então ele é “puxado” para a direita uma vez, liberando lugar para o elemento copiado.

Na iteração seguinte, quando a variável i assumir o valor 2, o elemento do índice 2, que será copiado, será comparado com o elemento do índice 1, que será “puxado” para a direita se for maior, e com o elemento do índice 0, que também será “puxado” para a direita se for maior, liberando assim lugar para o elemento do índice 2 que foi copiado.

Esse processo irá se repetir até o final do vetor. O último elemento do vetor será comparado com todos os elementos anteriores (ou até encontrar sua posição correta). Os maiores serão “puxados” para a direita, até que a posição correta seja encontrada e ele seja inserido ordenado.

Algoritmo de ordenação Insertion Sort em Portugol

programa
{

	/*
	 * 	Aula 127: Algoritmo de ordenação Insertion Sort
	 * 	
	 * 	Código escrito por Wagner Gaspar
	 * 	Abril de 2021
	*/

	funcao imprimir(inteiro vet[], inteiro tam){
		inteiro i

		para(i = 0; i < tam; i++)
			escreva(vet[i], " ")
		escreva("\n")
	}
	
	funcao inicio()
{
		inteiro vet[25] = {45,5,72,19,28,61,37,49,47,89,66,33,55,57,12,18,19,46,94,99,43,27,29,55,88}
		inteiro copia, indice, i

		imprimir(vet, 25)
		
		para(i = 1; i < 25; i++){
			copia = vet[i]
			indice = i

			enquanto(indice > 0 e vet[indice - 1] > copia){
				vet[indice] = vet[indice - 1]
				indice--
			}
			vet[indice] = copia
		}

		imprimir(vet, 25)
	}
}