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 i de 1 até n-1, define-se a chave key = A[i] e inicializa-se j = i-1. Em seguida executa-se:
while j >= 0 e A[j] > key:
A[j+1] = A[j] ← cópia a ser contada
j = j - 1
por fim insere-se key em A[j+1].

Passo 3

O vetor original possui 20 elementos: \
v = lang<= 7,2,1,2,6,2,6,9,2,7,6,7,4,1,5,6,3,3,7,4rang<=.

Passo 4

Em cada iteração i contamos o número de cópias que o while realiza, chamando esse valor de si. Ao simular para i=1,2,dots,19, obtivemos:
si = 1,2,1,1,2,1,0,4,1,3,1,7,12,7,4,10,10,1,10.

Passo 5

Somando todos os deslocamentos temos
sumi=1^19 si = 78
Portanto, o número total de cópias dentro do while é 78.

Resposta

78 cópias

Exercícios relacionados