La búsqueda binaria (04-01) nos dejó una factura pendiente: exige la lista ordenada, y alguien tiene que ordenarla. Empezamos el estudio del ordenamiento por el algoritmo más natural de todos: el ordenamiento por inserción, el que ejecutas sin darte cuenta al ordenar cartas en la mano o al cuadrar a mano un panel de llegadas desordenado. No es el más rápido en general — es O(n²) en el peor caso —, pero tiene virtudes que lo mantienen vivo dentro de las bibliotecas estándar más modernas: es O(n) sobre datos casi ordenados, no gasta memoria extra, es estable y funciona online. En esta lección lo implementaremos, lo trazaremos sobre las llegadas de la L1, lo analizaremos por casos con el método de 02-03 y aprenderemos un concepto nuevo que nos acompañará todo el módulo: la estabilidad.

1. La intuición: ordenar cartas, cuadrar paneles
2. Implementación in-place comentada
3. Traza completa: seis llegadas de la L1
4. Análisis por casos: mejor O(n), peor y promedio O(n²)
5. Estabilidad: qué es y por qué importa
6. El superpoder: datos casi ordenados
7. Espacio y cuándo elegirlo

Imagina que recibes cartas de una en una y las vas colocando en la mano: cada carta nueva la deslizas hacia la izquierda hasta su sitio entre las que ya tienes ordenadas. En ningún momento tienes la mano desordenada; simplemente crece.

El operador de RutaBus hace lo mismo cuando el panel de llegadas de una parada se descuadra: recorre la lista de arriba abajo y, cada vez que encuentra una hora fuera de sitio, la extrae y la desliza hacia arriba hasta donde corresponde. Esa es exactamente la estructura del algoritmo:

• La lista se divide conceptualmente en dos zonas: un prefijo ya ordenado (al principio, empieza siendo solo el primer elemento) y el resto sin procesar.
• En cada paso se toma el primer elemento sin procesar (la "carta nueva") y se inserta en su posición dentro del prefijo, desplazando hacia la derecha los que son mayores.
• Cuando no queda resto, toda la lista es prefijo ordenado.

El invariante de bucle — la técnica de razonamiento de 04-01 — es: antes de procesar el elemento i, los elementos 0..i−1 están ordenados entre sí.

Detalles que conviene entender línea a línea:

• actual = llegadas[i]: guardamos una copia porque los desplazamientos van a pisar la posición i. Esta variable es todo el espacio extra que usa el algoritmo.
• El bucle while tiene dos condiciones y el orden importa: j >= 0 debe evaluarse antes que llegadas[j] > actual, porque si j llega a −1, llegadas[-1] en Python no falla — devuelve el último elemento (¡índice negativo!) — y produciría un error silencioso. La evaluación en cortocircuito de and nos protege.
• llegadas[j] > actual estricto: si son iguales, el bucle para y actual se inserta después de sus iguales. Esta elección, aparentemente menor, es la que hace al algoritmo estable (apartado 5).
• llegadas[j + 1] = actual: al salir del bucle, j apunta al último elemento ≤ actual (o a −1 si no hay ninguno), así que su sitio es j + 1.

Es in-place: reordena dentro de la propia lista, sin construir una copia. Costará O(1) de espacio auxiliar (02-02).

El panel de Plaza Mayor recibe las próximas llegadas de la L1 en el orden en que las emitieron los buses, no en orden de hora:

(Las horas en formato "HH:MM" se comparan bien como cadenas: el orden alfabético coincide con el cronológico si el formato es fijo — el mismo truco que usamos con bisect en 02-03.)

Trazamos vuelta a vuelta del for. El prefijo ordenado va en negrita:

Total: 8 desplazamientos y 12 comparaciones para n = 6. Dos observaciones de la traza:

• La vuelta i = 3 (18:59) costó una sola comparación: el elemento ya estaba en su sitio. Cuantos más elementos lleguen "en orden", más vueltas baratas — esta es la semilla del mejor caso O(n).
• Las vueltas i = 4 y i = 5 fueron caras porque el elemento venía "muy fuera de sitio". El coste de cada vuelta es proporcional a cuán lejos está el elemento de su posición final.

El coste lo dominan las comparaciones/desplazamientos del while interior. Apliquemos el análisis por casos de 02-03 — este algoritmo es el ejemplo de libro de por qué ese análisis existe:

Mejor caso — Θ(n): lista ya ordenada. Cada actual es ≥ que todo el prefijo, el while hace una comparación y cero desplazamientos, y el for da n−1 vueltas baratas. Total ≈ n−1 comparaciones. Ningún otro algoritmo de comparación puede bajar de ahí: como mínimo hay que mirar cada elemento para certificar que está ordenado.

Peor caso — Θ(n²): lista en orden inverso. Cada actual es menor que todo el prefijo y debe viajar hasta el principio: la vuelta i cuesta i desplazamientos. Total:

Nuestra vieja conocida suma aritmética de 02-01 → Θ(n²). Con el panel de 6 llegadas invertido serían 15 desplazamientos; con las 10.000 expediciones diarias de RutaBus, ≈ 50 millones.

Caso promedio — Θ(n²): orden aleatorio. En promedio, cada elemento debe cruzar la mitad del prefijo (el mismo argumento de distribución uniforme que usamos con buscar_parada en 02-03): la vuelta i cuesta ≈ i/2, y el total ≈ n(n−1)/4. La mitad del peor caso en valor absoluto... y el mismo orden Θ(n²) — "el doble de rápido en la práctica, el mismo orden en teoría", tal cual lo aprendimos.

¿Y no podríamos encontrar el hueco con búsqueda binaria (04-01), ya que el prefijo está ordenado? Sí — se llama inserción binaria y reduce las comparaciones a O(n log n)... pero los desplazamientos siguen siendo n(n−1)/2 en el peor caso, porque hay que mover los elementos igualmente. Es la misma lección que insort en 02-03: la búsqueda binaria acelera el encontrar, no el mover. El algoritmo sigue siendo Θ(n²).

Un algoritmo de ordenamiento es estable si, cuando dos elementos empatan en la clave de ordenación, conservan entre sí el orden relativo que traían. Suena a detalle pedante hasta que te muerde en producción.

El panel de Estación Norte muestra llegadas de varias líneas, y dos coinciden en hora:

Ordenamos por hora. Las dos llegadas de las 18:30 empatan; un ordenamiento estable las deja como venían (L2 antes que L1, quizá porque ese era su orden de emisión o porque la lista ya venía ordenada por línea); uno inestable puede intercambiarlas arbitrariamente.

¿Por qué importa? Porque la estabilidad permite ordenar por varias claves encadenando ordenaciones: si primero ordenas el panel por línea y después, con un algoritmo estable, por hora, obtienes "por hora, y a igual hora por línea" — gratis. Con un algoritmo inestable, la segunda ordenación destruye el trabajo de la primera.

El ordenamiento por inserción es estable, y lo es exactamente por la comparación estricta llegadas[j] > actual del while: ante un empate el bucle se detiene y el elemento nuevo queda a la derecha de sus iguales — es decir, después, como llegó. Si escribieras >=, el algoritmo seguiría ordenando correctamente... pero dejaría de ser estable. Un carácter de diferencia.

Afinemos el análisis. El coste real del algoritmo es proporcional al número de inversiones de la entrada: pares de elementos que están en orden equivocado entre sí. Una lista ordenada tiene 0 inversiones; una invertida, n(n−1)/2; y cada desplazamiento del while corrige exactamente una inversión. Por tanto:

Esto explica su nicho de oro: los datos casi ordenados. El panel de llegadas de RutaBus se alimenta de eventos que llegan casi en orden cronológico — solo algún bus con retraso de emisión inserta una hora fuera de sitio. Si cada elemento está a lo sumo a k posiciones de su sitio, hay a lo sumo n·k inversiones y el coste es O(n·k): con k pequeño y constante, lineal en la práctica. Ningún algoritmo "sofisticado" de los que veremos después baja de O(n log n) en ese escenario; la inserción lo hace en O(n).

De ahí que siga viva dentro de las bibliotecas modernas: los algoritmos híbridos de producción (lo veremos con Timsort en 04-03) delegan en inserción los tramos pequeños o casi ordenados.

Espacio auxiliar: O(1). Solo actual, i y j; todo el movimiento ocurre dentro de la propia lista. Con la terminología de 02-02: espacio total O(n), espacio auxiliar O(1). Es la referencia frente a la que mediremos el O(n) extra de merge sort (04-03).

Además es online: puede ir ordenando a medida que llegan los elementos, sin conocer la secuencia completa — justo lo que hacía registrar_llegada (02-03) mantieniendo el panel ordenado inserción a inserción.

• Invertir las condiciones del while (llegadas[j] > actual and j >= 0): con j = -1, Python evalúa llegadas[-1] — que no lanza error sino que lee el último elemento — y el resultado es una lista mal ordenada sin ninguna excepción que te avise. El cortocircuito de and solo te protege si j >= 0 va primero.
• Olvidar la copia actual: si trabajas directamente con llegadas[i], el primer desplazamiento lo sobrescribe y duplicas un elemento perdiendo otro. Síntoma típico: la lista termina "ordenada" pero con valores repetidos que no estaban.
• Insertar en j en vez de j + 1: al salir del bucle, j señala al último elemento menor o igual — el hueco es la posición siguiente. Prueba mental rápida: si actual es el mayor de todos, el bucle no ejecuta ninguna vuelta y j + 1 == i, que es dejarlo donde estaba. Correcto.
• Romper la estabilidad con >=: ordena igual de bien, así que ningún test de "¿está ordenada?" lo detecta; solo lo notarás cuando el orden secundario de los empates importe. Si tu test no incluye claves duplicadas, no estás probando la estabilidad.
• Consejo: para verificar una implementación de ordenación, compárala contra sorted() con listas aleatorias, incluyendo vacía, de un elemento, con duplicados y en orden inverso. Cinco líneas de bucle de pruebas cazan el 99 % de los errores.

Traza (tabla como la del apartado 3) ordenar_insercion sobre el panel ["18:05", "18:12", "18:31", "18:59", "18:01"]. Antes de trazar, predice: ¿será una ejecución barata o cara? ¿Qué elemento se lleva casi todo el coste? Cuenta comparaciones y desplazamientos totales.

El panel guarda tuplas (hora, linea) y hay que ordenar solo por hora conservando la estabilidad. Adapta ordenar_insercion para que compare únicamente por el primer campo de la tupla, y demuestra con panel = [("18:30", "L2"), ("18:05", "L1"), ("18:30", "L1")] que los dos empates de las 18:30 conservan su orden relativo.

RutaBus recibe cada noche el fichero de llegadas del día "casi ordenado": como mucho, cada registro está desplazado k = 3 posiciones de su lugar. El equipo debate entre inserción y un algoritmo O(n log n). Con n = 100.000: (a) estima las operaciones de la inserción usando la cota O(n·k); (b) compárala con n·log₂ n; (c) ¿qué recomendarías y qué pregunta de 02-03 ("¿qué caso importa?") está detrás de la decisión?

Solución 1

Predicción: los cuatro primeros elementos ya vienen ordenados, así que sus vueltas serán baratas; "18:01" es el mínimo y llega el último — tendrá que cruzar todo el prefijo. Ejecución casi-mejor-caso con una vuelta de peor caso.

Comparaciones: 1 + 1 + 1 + 4 = 7. Desplazamientos: 4, todos de la última vuelta. Un solo elemento fuera de sitio (con 4 inversiones) convierte una ejecución O(n) en O(n) + 4 — sigue siendo barata, coherente con la cota "n + inversiones".

Solución 2

Las dos llegadas de las 18:30 mantienen L2 antes que L1, como en la entrada: estable. Si cambias > por >= obtendrás [('18:05','L1'), ('18:30','L1'), ('18:30','L2')] — ordenado por hora igualmente, pero con el empate invertido.

Solución 3

(a) Cota de la inserción: n·k = 100.000 × 3 = 300.000 desplazamientos como mucho (más las ~n comparaciones baratas: mismo orden). (b) n·log₂ n ≈ 100.000 × 17 ≈ 1.700.000 operaciones. La inserción hace ~5–6 veces menos trabajo, con un código más simple y O(1) de memoria. (c) Recomendación: inserción, siempre que la premisa "k ≤ 3" esté garantizada. La pregunta de fondo es la de 02-03: ¿el caso favorable es el frecuente y está garantizado? Si un día el fichero llega en orden arbitrario (un fallo upstream), la inserción se dispara a Θ(n²) ≈ 5·10⁹ operaciones. Decisión de ingeniería: o validar la premisa (medir el desorden antes de elegir), o usar un híbrido que degrade con elegancia — exactamente lo que hace Timsort, como veremos en la próxima lección.

El ordenamiento por inserción mantiene un prefijo ordenado e inserta cada elemento nuevo en su sitio desplazando a los mayores: estable (gracias a una comparación estricta), in-place con O(1) auxiliar, online, Θ(n) sobre datos ya ordenados y Θ(n²) en promedio y peor caso — con un coste real de "n + inversiones" que lo convierte en el rey de lo pequeño y de lo casi ordenado, como los paneles de llegadas de RutaBus. Pero su talón de Aquiles es evidente: sobre las 10.000 expediciones diarias en orden arbitrario, los ~25 millones de operaciones del caso promedio no son aceptables. Para romper la barrera del O(n²) necesitamos dejar de mover elementos de uno en uno y atacar el problema con la estrategia de 03-01: dividir la lista, ordenar las mitades y combinarlas. Ese es el ordenamiento por mezcla (merge sort) — y con él, por fin, resolveremos la recurrencia T(n) = 2·T(n/2) + O(n) que dejamos pendiente en el Módulo 3.