El ordenamiento por inserción (insertion sort) en Python
En esta lección vas a implementar el ordenamiento por inserción colocando cada elemento en su sitio dentro de la parte ya ordenada.
Introducción
El problema
A menudo los datos llegan casi ordenados, o de uno en uno: una lista ordenada de puntuaciones recibe una puntuación nueva. Volver a ordenarlo todo es un desperdicio. El ordenamiento por inserción maneja muy bien este caso, y es como mucha gente ordena las cartas a mano.
Imagínalo así
El ordenamiento por inserción funciona igual que cuando ordenas las cartas que tienes en la mano. Tomas una carta cada vez y la deslizas a la izquierda, pasando cada carta mayor, hasta que queda en su sitio. Las cartas a su izquierda siempre están en orden.
current = result[index]🃏 Toma la siguiente cartaresult[position] > current👈 ¿La carta de la izquierda es mayor?result[position + 1] = result[position]➡️ Mueve la carta mayor un sitio a la derecharesult[position + 1] = current📥 Deja la carta en el huecoEl ordenamiento por inserción construye una parte ordenada elemento a elemento: desplaza a la derecha los elementos mayores y coloca el elemento actual en el hueco. Es O(n²) en el peor caso, pero casi O(n) con datos casi ordenados.
Puntos clave
for index in range(1, len(result)):empieza en el segundo elemento, porque un solo elemento ya está ordenado.currentguarda el valor que se inserta mientras se mueven los valores mayores.while position >= 0 and result[position] > current:desplaza cada valor mayor un sitio a la derecha.result[position + 1] = currentcoloca el valor en el hueco que se ha abierto.
¿Cuándo se usa?
- Listas pequeñas o casi ordenadas.
- Mantener una lista ordenada a medida que llegan elementos nuevos.
- Como paso final dentro de ordenamientos más rápidos, que cambian a inserción para los trozos pequeños.
Cuándo no hace falta
- Listas grandes y aleatorias: los desplazamientos se vuelven lentos, así que usa
sorted(). - Insertar a menudo en una lista ordenada grande:
bisect.insortencuentra la posición con búsqueda binaria.
Visualizador de El ordenamiento por inserción (insertion sort) en Python
O(n²)Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.
Código de ejemplo
def insertion_sort(values):
result = values.copy()
for index in range(1, len(result)):
current = result[index]
position = index - 1
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
position -= 1
result[position + 1] = current
return result
print(insertion_sort([9, 5, 1, 4, 3]))
Resultado de la ejecución
[1, 3, 4, 5, 9]
Explicación del código
La variable current guarda el valor que hay que insertar. El bucle while desplaza una posición a la derecha los valores mayores que current para dejar sitio, y después current se coloca en ese hueco. En el peor caso la complejidad es O(n²), pero con datos casi ordenados el algoritmo se acerca a O(n).
Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.
Ejercicios de práctica
Prueba a modificar el código siguiendo las ideas de abajo. Cambiar el código y ver el resultado te ayudará a entender la lección mucho mejor que solo leerla.
- Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
- Muestra el estado después de cada paso para ver el algoritmo en acción.
- Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Errores comunes
Escribir current dentro del bucle
El valor debe colocarse una sola vez, después de que se hayan movido todos los valores mayores.
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
result[position] = current
position -= 1
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
position -= 1
result[position + 1] = current
¿Terminaste esta lección?
Márcala como aprendida para seguir tu progreso.
Practica con un reto
Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.
Todos los retos