1- for j = 2 to A.comprimento
2- k = A[ j ]
3- i = j - 1
4- while i > 0 e A[ i ]> k
5- A[ i + 1] = A[ i ]
6- i = i - 1
7- A[ i + 1 ] = k
Este algorítimo começa com o índice j assumindo o valor 2 inicialmente, uma vez que a primeira posição no array já está ordenada. A variável k guarda o valor da posição que está sendo ordenada. O valor do índice i é empurrado uma posição de cada vez para a direita desde que ele seja maior que 0 e seu valor no arranjo maior que a varável k o que implica ser maior que j já que nesta altura da execução k = j.
fig.: i j
1,2,3,4,5
A [5|4|7|9|2]
A corretude (funcionamento correto) deste algorítimo pode ser comprovada aplicando uma técnica semelhante a indução matemática chamada de invariante de laço (loop invariant) com a qual demonstramos o funcionamento do algorítimo. Os passos da invariante de laço são três:
1- Inicialização: Onde a propriedade é verdadeira antes da primeira iteração
2- Manutenção: Se é verdadeiro antes da primeira iteração, será verdadeiro antes da próxima iteração
3- Término: Quando o loop acaba, a invariante nos fornece o resultado do loop, uma propriedade útil.
Observe no algorítimo que a primeira propriedade está comprovada pois se j = 1, o arranjo 1 até j está ordenado pois só tem um componente que é ele mesmo. A manutenção também é verdade por hipótese, uma vez que é verdade antes da primeira iteração. Agora, executando j a partir do índice 2 mostramos que o loop funciona quando ele retorna um valor útil indicando o término com sucesso. A invariante de laço é usada para provar algorítimos iterativos, porém, quando tratamos de algorítimos recursivos, como o próximo que veremos, o merge-Sort, usamos de fato, a indução matemática para mostrar que a função recursiva funciona. No próximo post, continuamos a análise verificando a complexidade do mesmo.
Algorítimos, Cormen, et al, 2012 3ed. capítulo 2.
