Ordenação por Inserção

Algoritmos são escritos por meio de uma linguagem chamada pseudocódigo. Esta linguagem é semelhante em alguns aspectos a linguagens de programação de alto nível, o que diverge é que o pseudocódigo é o mais próximo possível da linguagem comum, de forma a apresentar a informação o mais clara possível.

Um algoritmo possui uma entrada (que são os dados iniciais do problema), e uma saída (que são os dados processados pelo algoritmo, o resultado).

Ordenação por inserção é um exemplo de algoritmo. É utilizado para ordenar de maneira eficiente um número pequeno de elementos. Funciona semelhante à maneira como as pessoas ordenam cartas na mão em jogos de baralho: as cartas são empilhadas na mesa, enquanto a mão está vazia; a primeira carta é retirada e colocada na mão; em seguida uma carta de cada vez é removida da mesa, comparando-a com cada carta da mão, da direita para a esquerda, encaixando na posição de ordenação correta, e realizando assim a ordenação.

O pseudocódigo do algoritmo de ordenação por inserção é chamado de insertion-sort. Para melhor entendimento, ele pode ser visualizado como um arranjo de sequência. Inicialmente é definido o comprimento do arranjo – [A], que corresponde ao número de elementos a serem ordenados – comprimento[A]. Assim, os números são ordenados no local, dentro do arranjo, ficando sempre no máximo um número fora. Ao final, o mesmo arranjo conterá a sequência ordenada. A figura abaixo demonstra isso:

Abaixo o algoritmo escrito:

AlgoritmoOrdenaçãoInsercao(A)

para j ¬ 2 até comprimento[A] faça

            chave ¬ A[j]

            i ¬ j -1

            enquanto A[i] > chave e i > 0 faça

                        A[i + 1] ¬ A[i]

                        i ¬ i -1

            A[i + 1] ¬ chave

O conceito de loop invariante ajuda a analisar programas, verificar erros, e atestar a coerência do algoritmo. O mesmo possui três propriedades: Inicialização (o loop é verdadeiro antes da primeira interação), Manutenção (se o loop for verdadeiro antes da primeira interação, então permanecerá verdadeiro antes da próxima interação), e Término (quando o loop termina, o invariante aponta uma propriedade útil que mostra que o algoritmo está correto).

Tomando como exemplo o algoritmo de ordenação por inserção, é possível verificar que o mesmo possui a primeira propriedade (Inicialização), pois o loop é válido antes da primeira de iniciar, a atribuição à variável é realizada. Este algoritmo também possui a segunda propriedade (Manutenção), já que o loop continua invariante à medida que ocorre cada interação e a ordenação começa a aparecer. A terceira propriedade (Término) também pode ser vista, dado que ao final da última interação, o arranjo inteiro é ordenado; o que significa que o algoritmo está correto.

Exercícios (Livro Algoritmos Teoria e Prática – Thomas Cormen 2012):

1-     Usando a Figura acima como modelo, ilustre a operação de INSERTION-SORT no arranjo A = (31, 41, 59, 26, 41, 58).

  

2-     Reescreva o procedimento INSERTION-SORT (OrdenaçãoInserção) para ordenar em ordem não crescente, em vez da ordem não decrescente.

. AlgoritmoOrdenaçãoInsercao(A)

para j ¬ 2 até comprimento[A] faça

            chave ¬ A[j]

            i ¬ j -1

            enquanto A[i] < chave e i > 0 faça

                        A[i + 1] ¬ A[i]

                        i ¬ i -1

            A[i + 1] ¬ chave

3-     Considere o problema de pesquisa: Entrada: Uma sequência de n números A = (a₁, a₂, ..., a_n) e um valor v. Saída: Um índice i tal que v = A[i] ou o valor especial NIL, se v não aparecer em A. Escreva o pseudocódigo para pesquisa linear, que faça a varredura da sequência, procurando por v. Usando um loop invariante, prove que seu algoritmo é correto. Certifique-se de que seu loop invariante satisfaz às três propriedades necessárias.

Pesquisa(A, v)

i ¬ NIL

para j ¬ 1 até comprimento(A) faça

            se v = A[j] então

                        i = A[j]

escreva(i)

4-     Considere o problema de somar dois inteiros binários de n bits, armazenados em dois arranjos de n elementos A e B. A soma dos dois inteiros deve ser armazenada em forma binária em um arranjo de (n + 1) elementos C. Enuncie o problema de modo formal e escreva o pseudocódigo para somar os dois inteiros.

Escreva o algoritmo para a soma de dois inteiros binários de n bits, os quais estão armazenados em dois arranjos (A e B) em forma binária, onde o resultado deve ser armazenado em forma binária no arranjo C de n + 1 elementos.

SomaBinarios(A, B)

C: vetor[comprimento(A) + 1]

resto = 0

resultado = 0

para j ¬ comprimento(C)  até 1 faça

resultado = resto + A[j] + B[j]

            se resultado > 1 então

                        se resultado = 2 então

                                    resultado = 0

                                   resto = 1

                        senão  

                                   resultado = 1

                                   resto = 1

            senão

                        resto = 0

C[0] = resto

escreva(i)