Saltar al contenido

Desplazamientos de insertion sort

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

La misión

Problema

El insertion sort (ordenamiento por inserción) coloca cada valor nuevo desplazando una casilla a la derecha cada valor mayor de la parte ya ordenada. Dada una lista de números, devuelve cuántos desplazamientos de una casilla hace el insertion sort al ordenarla en orden ascendente. Los valores iguales nunca se adelantan entre sí, y la lista de entrada no debe modificarse.

Ejemplos

Input:  nums = [3, 1, 2]
Output: 2
Por qué: colocar el 1 desplaza el 3 una vez, y luego colocar el 2 desplaza el 3 una vez más
Input:  nums = [5, 4, 3, 2, 1]
Output: 10
Por qué: cada valor nuevo desplaza todos los valores ya colocados
Input:  nums = [2, 2, 2]
Output: 0
Por qué: caso límite: los valores iguales se quedan donde están

Pistas

0 / 3

Tiempo objetivo
O(n²)
Espacio objetivo
O(n)

¿Lo que te frena es la idea y no el código? Insertion sort lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio