Implemente o algoritmo de ordenação por inserção visto em aula e conte o número total de cópias de valores do vetor dentro do while ao executar no seguinte array: 72126269 276741563374
Passo 1
O enunciado pede para usar o algoritmo de ordenação por inserção (insertion sort) no vetor dado e contar quantas cópias de valores do próprio vetor ocorrem dentro do laço while.
Passo 2
No insertion sort, para cada índice
de 1 até
, define-se a chave
e inicializa-se
. Em seguida executa-se:
while
e
:
← cópia a ser contada
por fim insere-se
em
.
Passo 3
O vetor original possui 20 elementos: \
Passo 4
Em cada iteração
contamos o número de cópias que o while realiza, chamando esse valor de
. Ao simular para
, obtivemos:
Passo 5
Somando todos os deslocamentos temos
Portanto, o número total de cópias dentro do while é 78.
Resposta
78 cópias