Também conhecida como Insertion Sort, a Ordenação por Inserção consiste em inserir um elemento $n$ num vetor já ordenado de $n-1$ elementos. Neste artigo, apresento-lhes este simples algoritmo para ordenação de vetores.

O pseudocódigo da ordenação por inserção é o seguinte:

para j $\leftarrow{}$ 2 até comprimento do vetor, faça
 elemento $\leftarrow{}$ vetor[j]
 i $\leftarrow{}$ j - 1
 enquanto i > 0 e vetor[i] > elemento, faça
  vetor[i + 1] $\leftarrow{}$ vetor[i]
  i $\leftarrow{}$ i - 1
 fim-enquanto
 vetor[i + 1] $\leftarrow{}$ elemento
fim-para

Para explicar eu vou fazer uma coisa que sempre faço para corrigir meus algoritmos, fingir que sou o programa, executando cada passo manualmente (claro que geralmente faço mais rápido, porque não preciso escrever tudo que faço). Vamos iniciar com o seguinte vetor v.

Aí o código me manda começar com $j=2$ e iterar até o comprimento do vetor (6). A primeira ordem que ele me dá é para armazenar o elemento $a[j]$ ($a[2]$) na variável elemento. Para facilitar toda a explicação eu vou sempre pintar de cinza o $v[j]$ onde eu estou (no caso, o segundo elemento do vetor, 3) e de preto o vetor ainda não ordenado (elementos $\geq{}j$).

Então ele me diz que $i \leftarrow{} j-1$. Portanto, $i=1$. E agora ele me faz um enquanto (que poderia ser substituído por para) onde meu i deverá ir diminuindo. Vamos entrar no loop…

Bom, meu $i = 1$ é maior que 0. $v[1]=5$ é maior que o $elemento=3$? Sim, então vamos entrar no corpo do enquanto… Aqui ele me manda fazer um $vetor[i+1] = vetor[i]$, que nesse caso é fazer um $v[2]=v[1]=5$.

E agora subtrai de i um valor. Portanto, $i=0$. Ele retorna ao enquanto, mas agora não satisfazemos a condição $i>0$, por isso saímos do enquanto. Então ele pede para $vetor[i+1]=elemento$ ($v[1]=elemento$). Portanto, o vetor fica assim:

E incrementamos o j, agora $j=3$.

$elemento = 7$

$i = 3-1 = 2$

$i > 0$… E $5 > 7$? Não! Portanto, não entramos no enquanto.

$v[3] = elemento$ (nenhuma mudança)

E lá vamos para $j=4$ e continuando até que vamos ter o vetor ordenado:

Qual a lógica?

Como eu já disse na introdução, mas lá sem grandes explicações, a Ordenação por Inserção divide o vetor em dois. O primeiro (de elementos $< j$) contém todos seus valores ordenados e o segundo (de elementos $\geq{} j$) contém os valores que devem ser inseridos no primeiro vetor já ordenado (por isso ele se chama Algoritmo de Inserção). A chave do algoritmo é o enquanto que acontece para ir deslocando todos os elementos para seu índice $+1$) contém todos seus valores ordenados e o segundo (de elementos $\geq{}j$) contém os valores que devem ser inseridos no primeiro vetor já ordenado (por isso ele se chama Algoritmo de Inserção).

A variável elemento só serve para não perdermos o valor de $v[j]$ (porque depois fazemos $v[i+1]=v[i]$ quando $i=j-1$)

Acredito que não tenham restado dúvidas. Dê mais uma olhada no algoritmo e tente implementar. Se tiver dificulade, coloque mensagens de debug estratégicas para entender o algoritmo. (ex.: no início do para coloque para imprimir o valor de j e no início de cada enquanto coloque para imprimir os valores elemento, i e v[i])

Custo

Você deve ter percebido que este algoritmo não tem um custo fixo. Se todo o vetor estiver ordenado, ele nunca precisará iterar o $i$ e portanto será executado bem mais rápido do que se o vetor estiver inteiro em ordem decrescente (quando ele sempre precisará iterar $i$ até o fim - 0). Então, neste artigo, gostaria-lhes de apresentar a análise de algoritmos baseada em casos. Para este programa, dizemos que:

• Melhor caso é quando todos os elementos já estão ordenados. Custo: $\Theta{}(n)$
• Pior caso é quando os elementos estão em ordem decrescente. Custo: $\Theta{}(n^{2})$

Em alguns programas o caso médio é importante também, mas não é o caso da ordenação por inserção. Vemos que há uma diferença bem grande entre o custo dos dois casos. Por isso, precisamos conhecer onde que nosso algoritmo será implementado e quais as chances de ele ser o melhor ou pior caso. Em geral, o pior caso é o mais comum… Por isso, diremos que o custo deste algoritmo é $\Theta{}(n^{2})$.