Desplazamientos de insertion sort
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
No necesitas una fórmula. La pregunta es sobre lo que hace el algoritmo, así que deja que el algoritmo lo haga y observa.
Trabaja sobre una copia de la lista y ejecuta insertion sort en ella, con un contador junto a la línea que mueve un valor una casilla a la derecha.
Para cada índice desde el segundo en adelante, guarda su valor y, mientras el valor a su izquierda sea estrictamente mayor, desplaza ese valor a la derecha y suma uno al contador. Deja caer el valor guardado en el hueco. El contador al final es la respuesta.
- Tiempo objetivo
- O(n²)
- Espacio objetivo
- O(n)
Solución
Ejecutar insertion sort sobre una copia y contar dentro de su bucle interno responde la pregunta exactamente, porque cada desplazamiento es una ejecución del cuerpo de ese bucle. La comparación debe ser estrictamente mayor que, que es lo que impide que los valores iguales se desplacen y mantiene el ordenamiento estable. Cada desplazamiento además corrige un par de valores que estaban en el orden equivocado, y por eso una lista invertida es la que más cuesta. El tiempo es O(n²) en el peor caso y O(n) en una lista que ya está ordenada, y el espacio es O(n) por la copia.
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])) # -> 0¿Lo que te frena es la idea y no el código? Insertion sort lo explica.