Pular para o conteúdo

Deslocamentos do insertion sort

Fácil#insertion-sort#stable-sort~15 min

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

Tempo-alvo
O(n²)
Espaço-alvo
O(n)

Travou na ideia, e não no código? Insertion sort explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado