Questão 772764

A ordenação por inserção é um algoritmo eficiente para ordenar um pequeno número de elementos. Considere o exemplo de um jogador de póquer que inicia uma partida com sua mão esquerda vazia e as suas cartas com a face virada para baixo na mesa. O jogador remove uma carta de cada vez da mesa e a insere na posição correta na mão esquerda. Para encontrar a posição correta de uma carta, esta é comparada a cada uma das cartas que já estão na mão, da direita para a esquerda, como ilustrado na figura abaixo. Em cada instante, as cartas seguras na mão esquerda são ordenadas. Essas cartas eram originalmente as cartas superiores da pilha na mesa.

O exemplo acima ilustra um pseudocódigo, que toma como parâmetro um arranjo A[1 ..n] contendo uma sequência de comprimento n que deverá ser ordenada. O pseudocódigo em questão, usado para ordenação por inserção, é apresentado como um procedimento chamado: