Deslocamentos do insertion sort
A missão
Problema
O insertion sort posiciona cada novo valor deslizando uma casa para a direita todos os valores maiores da parte já ordenada. Dada uma lista de números, retorne quantos deslizamentos de uma casa o insertion sort faz ao ordená-la em ordem crescente. Valores iguais nunca passam um pelo outro, e a lista de entrada não pode ser modificada.
Exemplos
Input: nums = [3, 1, 2]
Output: 2
Por quê: posicionar o 1 desliza o 3 uma vez, e posicionar o 2 desliza o 3 mais uma vez
Input: nums = [5, 4, 3, 2, 1]
Output: 10
Por quê: cada novo valor desliza todos os valores já posicionados
Input: nums = [2, 2, 2]
Output: 0
Por quê: edge case: valores iguais ficam onde estão
Dicas
0 / 3
Você não precisa de fórmula. A pergunta é sobre o que o algoritmo faz, então deixe o algoritmo trabalhar e observe.
Trabalhe em uma cópia da lista e rode o insertion sort nela, mantendo um contador ao lado da linha que move um valor uma casa para a direita.
Para cada índice a partir do segundo, segure o valor dele e, enquanto o valor à esquerda for estritamente maior, desloque esse valor para a direita e some um ao contador. Solte o valor segurado no espaço vazio. O contador no fim é a resposta.
- Tempo-alvo
- O(n²)
- Espaço-alvo
- O(n)
Solução
Rodar o insertion sort em uma cópia e contar dentro do loop interno responde exatamente à pergunta, porque cada deslizamento é uma execução do corpo desse loop. A comparação precisa ser de estritamente maior, e é isso que impede valores iguais de deslizar e mantém a ordenação estável. Cada deslizamento também corrige um par de valores que estava na ordem errada, e é por isso que uma lista invertida custa mais. O tempo é O(n²) no pior caso e O(n) em uma lista já ordenada, e o espaço é O(n) pela cópia.
def count_shifts(nums):
a = list(nums) # sort a copy, leave the input alone
shifts = 0
for i in range(1, len(a)):
cur, j = a[i], i - 1
while j >= 0 and a[j] > cur: # only strictly larger values make room
a[j + 1] = a[j]
shifts += 1
j -= 1
a[j + 1] = cur # drop the held value into the gap
return shifts
print(count_shifts([3, 1, 2])) # -> 2
print(count_shifts([5, 4, 3, 2, 1])) # -> 10
print(count_shifts([2, 2, 2])) # -> 0Travou na ideia, e não no código? Insertion sort explica isso.