Algoritmos en Python

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.

  • Intermedio
  • 2 min de lectura
  • 1 ejemplo ejecutable

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.

De ordenar cartas al código
current = result[index]🃏 Toma la siguiente carta
result[position] > current👈 ¿La carta de la izquierda es mayor?
result[position + 1] = result[position]➡️ Mueve la carta mayor un sitio a la derecha
result[position + 1] = current📥 Deja la carta en el hueco
La parte izquierda siempre está ordenada, y cada elemento nuevo se inserta en ella.
En una frase

El 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

  1. for index in range(1, len(result)): empieza en el segundo elemento, porque un solo elemento ya está ordenado.
  2. current guarda el valor que se inserta mientras se mueven los valores mayores.
  3. while position >= 0 and result[position] > current: desplaza cada valor mayor un sitio a la derecha.
  4. result[position + 1] = current coloca 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.insort encuentra 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

Ejecutar código →
main.py
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]))
Obtén un botón Run para este ejemplo

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.

  1. Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
  2. Muestra el estado después de cada paso para ver el algoritmo en acción.
  3. Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Ejecutar en el compilador de Python →

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.

Problema
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    result[position] = current
    position -= 1
Solución
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