La cerca binària (04-01) ens va deixar una factura pendent: exigeix la llista ordenada, i algú l'ha d'ordenar. Comencem l'estudi de l'ordenació per l'algorisme més natural de tots: l'ordenació per inserció, el que executes sense adonar-te'n en ordenar cartes a la mà o en quadrar a mà un panell d'arribades desordenat. No és el més ràpid en general — és O(n²) en el pitjor cas —, però té virtuts que el mantenen viu dins de les biblioteques estàndard més modernes: és O(n) sobre dades gairebé ordenades, no gasta memòria extra, és estable i funciona online. En aquesta lliçó l'implementarem, el traçarem sobre les arribades de la L1, l'analitzarem per casos amb el mètode de 02-03 i aprendrem un concepte nou que ens acompanyarà tot el mòdul: l'estabilitat.

1. La intuïció: ordenar cartes, quadrar panells
2. Implementació in situ comentada
3. Traça completa: sis arribades de la L1
4. Anàlisi per casos: millor O(n), pitjor i mitjà O(n²)
5. Estabilitat: què és i per què importa
6. El superpoder: dades gairebé ordenades
7. Espai i quan triar-lo

Imagina que reps cartes d'una en una i les vas col·locant a la mà: cada carta nova la fas lliscar cap a l'esquerra fins al seu lloc entre les que ja tens ordenades. En cap moment tens la mà desordenada; simplement creix.

L'operador de RutaBus fa el mateix quan el panell d'arribades d'una parada es desquadra: recorre la llista de dalt a baix i, cada vegada que troba una hora fora de lloc, l'extreu i la fa lliscar cap amunt fins on correspon. Aquesta és exactament l'estructura de l'algorisme:

• La llista es divideix conceptualment en dues zones: un prefix ja ordenat (al principi, comença sent només el primer element) i la resta sense processar.
• A cada pas es pren el primer element sense processar (la "carta nova") i s'insereix a la seva posició dins del prefix, desplaçant cap a la dreta els que són majors.
• Quan no queda resta, tota la llista és prefix ordenat.

L'invariant de bucle — la tècnica de raonament de 04-01 — és: abans de processar l'element i, els elements 0..i−1 estan ordenats entre si.

Detalls que convé entendre línia a línia:

• actual = arribades[i]: en guardem una còpia perquè els desplaçaments trepitjaran la posició i. Aquesta variable és tot l'espai extra que fa servir l'algorisme.
• El bucle while té dues condicions i l'ordre importa: j >= 0 s'ha d'avaluar abans que arribades[j] > actual, perquè si j arriba a −1, arribades[-1] en Python no falla — retorna el darrer element (índex negatiu!) — i produiria un error silenciós. L'avaluació en curtcircuit de l'and ens protegeix.
• arribades[j] > actual estricte: si són iguals, el bucle para i actual s'insereix després dels seus iguals. Aquesta tria, aparentment menor, és la que fa l'algorisme estable (apartat 5).
• arribades[j + 1] = actual: en sortir del bucle, j apunta al darrer element ≤ actual (o a −1 si no n'hi ha cap), així que el seu lloc és j + 1.

És in situ (in-place): reordena dins de la mateixa llista, sense construir-ne una còpia. Costarà O(1) d'espai auxiliar (02-02).

El panell de la Plaça Major rep les properes arribades de la L1 en l'ordre en què les van emetre els busos, no en ordre d'hora:

(Les hores en format "HH:MM" es comparen bé com a cadenes: l'ordre alfabètic coincideix amb el cronològic si el format és fix — el mateix truc que vam fer servir amb bisect a 02-03.)

Tracem volta a volta del for. El prefix ordenat va en negreta:

Total: 8 desplaçaments i 12 comparacions per a n = 6. Dues observacions de la traça:

• La volta i = 3 (18:59) va costar una sola comparació: l'element ja era al seu lloc. Com més elements arribin "en ordre", més voltes barates — aquesta és la llavor del millor cas O(n).
• Les voltes i = 4 i i = 5 van ser cares perquè l'element venia "molt fora de lloc". El cost de cada volta és proporcional a com de lluny és l'element de la seva posició final.

El cost el dominen les comparacions/desplaçaments del while interior. Apliquem l'anàlisi per casos de 02-03 — aquest algorisme és l'exemple de llibre de per què aquesta anàlisi existeix:

Millor cas — Θ(n): llista ja ordenada. Cada actual és ≥ que tot el prefix, el while fa una comparació i zero desplaçaments, i el for dona n−1 voltes barates. Total ≈ n−1 comparacions. Cap altre algorisme de comparació pot baixar d'aquí: com a mínim cal mirar cada element per certificar que està ordenat.

Pitjor cas — Θ(n²): llista en ordre invers. Cada actual és menor que tot el prefix i ha de viatjar fins al principi: la volta i costa i desplaçaments. Total:

La nostra vella coneguda suma aritmètica de 02-01 → Θ(n²). Amb el panell de 6 arribades invertit serien 15 desplaçaments; amb les 10.000 expedicions diàries de RutaBus, ≈ 50 milions.

Cas mitjà — Θ(n²): ordre aleatori. De mitjana, cada element ha de creuar la meitat del prefix (el mateix argument de distribució uniforme que vam fer servir amb cerca_parada a 02-03): la volta i costa ≈ i/2, i el total ≈ n(n−1)/4. La meitat del pitjor cas en valor absolut... i el mateix ordre Θ(n²) — "el doble de ràpid a la pràctica, el mateix ordre en teoria", tal com ho vam aprendre.

I no podríem trobar el forat amb cerca binària (04-01), ja que el prefix està ordenat? Sí — se'n diu inserció binària i redueix les comparacions a O(n log n)... però els desplaçaments continuen sent n(n−1)/2 en el pitjor cas, perquè els elements s'han de moure igualment. És la mateixa lliçó que insort a 02-03: la cerca binària accelera el trobar, no el moure. L'algorisme continua sent Θ(n²).

Un algorisme d'ordenació és estable si, quan dos elements empaten en la clau d'ordenació, conserven entre si l'ordre relatiu que portaven. Sona a detall pedant fins que et mossega en producció.

El panell de l'Estació Nord mostra arribades de diverses línies, i dues coincideixen en hora:

Ordenem per hora. Les dues arribades de les 18:30 empaten; una ordenació estable les deixa com venien (L2 abans que L1, potser perquè aquell era el seu ordre d'emissió o perquè la llista ja venia ordenada per línia); una d'inestable les pot intercanviar arbitràriament.

Per què importa? Perquè l'estabilitat permet ordenar per diverses claus encadenant ordenacions: si primer ordenes el panell per línia i després, amb un algorisme estable, per hora, obtens "per hora, i a igual hora per línia" — de franc. Amb un algorisme inestable, la segona ordenació destrueix la feina de la primera.

L'ordenació per inserció és estable, i ho és exactament per la comparació estricta arribades[j] > actual del while: davant d'un empat el bucle s'atura i l'element nou queda a la dreta dels seus iguals — és a dir, després, tal com va arribar. Si escrivissis >=, l'algorisme continuaria ordenant correctament... però deixaria de ser estable. Un caràcter de diferència.

Afinem l'anàlisi. El cost real de l'algorisme és proporcional al nombre d'inversions de l'entrada: parells d'elements que estan en ordre equivocat entre si. Una llista ordenada té 0 inversions; una d'invertida, n(n−1)/2; i cada desplaçament del while corregeix exactament una inversió. Per tant:

Això explica el seu nínxol d'or: les dades gairebé ordenades. El panell d'arribades de RutaBus s'alimenta d'esdeveniments que arriben gairebé en ordre cronològic — només algun bus amb retard d'emissió insereix una hora fora de lloc. Si cada element és com a màxim a k posicions del seu lloc, hi ha com a màxim n·k inversions i el cost és O(n·k): amb k petit i constant, lineal a la pràctica. Cap algorisme "sofisticat" dels que veurem després baixa d'O(n log n) en aquest escenari; la inserció ho fa en O(n).

D'aquí que continuï viva dins de les biblioteques modernes: els algorismes híbrids de producció (ho veurem amb Timsort a 04-03) deleguen en la inserció els trams petits o gairebé ordenats.

Espai auxiliar: O(1). Només actual, i i j; tot el moviment passa dins de la mateixa llista. Amb la terminologia de 02-02: espai total O(n), espai auxiliar O(1). És la referència davant la qual mesurarem l'O(n) extra de merge sort (04-03).

A més és online: pot anar ordenant a mesura que arriben els elements, sense conèixer la seqüència completa — just el que feia registra_arribada (02-03) mantenint el panell ordenat inserció a inserció.

• Invertir les condicions del while (arribades[j] > actual and j >= 0): amb j = -1, Python avalua arribades[-1] — que no llança cap error sinó que llegeix el darrer element — i el resultat és una llista mal ordenada sense cap excepció que t'avisi. El curtcircuit de l'and només et protegeix si j >= 0 va primer.
• Oblidar la còpia actual: si treballes directament amb arribades[i], el primer desplaçament la sobreescriu i dupliques un element perdent-ne un altre. Símptoma típic: la llista acaba "ordenada" però amb valors repetits que no hi eren.
• Inserir a j en comptes de j + 1: en sortir del bucle, j assenyala el darrer element menor o igual — el forat és la posició següent. Prova mental ràpida: si actual és el major de tots, el bucle no executa cap volta i j + 1 == i, que és deixar-lo on era. Correcte.
• Trencar l'estabilitat amb >=: ordena igual de bé, així que cap test de "està ordenada?" ho detecta; només ho notaràs quan l'ordre secundari dels empats importi. Si el teu test no inclou claus duplicades, no estàs provant l'estabilitat.
• Consell: per verificar una implementació d'ordenació, compara-la contra sorted() amb llistes aleatòries, incloent-hi la buida, la d'un element, amb duplicats i en ordre invers. Cinc línies de bucle de proves cacen el 99 % dels errors.

Traça (taula com la de l'apartat 3) ordena_insercio sobre el panell ["18:05", "18:12", "18:31", "18:59", "18:01"]. Abans de traçar, prediu: serà una execució barata o cara? Quin element s'endú gairebé tot el cost? Compta comparacions i desplaçaments totals.

El panell guarda tuples (hora, linia) i cal ordenar només per hora conservant l'estabilitat. Adapta ordena_insercio perquè compari únicament pel primer camp de la tupla, i demostra amb panell = [("18:30", "L2"), ("18:05", "L1"), ("18:30", "L1")] que els dos empats de les 18:30 conserven el seu ordre relatiu.

RutaBus rep cada nit el fitxer d'arribades del dia "gairebé ordenat": com a màxim, cada registre està desplaçat k = 3 posicions del seu lloc. L'equip debat entre inserció i un algorisme O(n log n). Amb n = 100.000: (a) estima les operacions de la inserció usant la fita O(n·k); (b) compara-la amb n·log₂ n; (c) què recomanaries i quina pregunta de 02-03 ("quin cas importa?") hi ha darrere de la decisió?

Solució 1

Predicció: els quatre primers elements ja venen ordenats, així que les seves voltes seran barates; "18:01" és el mínim i arriba l'últim — haurà de creuar tot el prefix. Execució gairebé-millor-cas amb una volta de pitjor cas.

Comparacions: 1 + 1 + 1 + 4 = 7. Desplaçaments: 4, tots de la darrera volta. Un sol element fora de lloc (amb 4 inversions) converteix una execució O(n) en O(n) + 4 — continua sent barata, coherent amb la fita "n + inversions".

Solució 2

Les dues arribades de les 18:30 mantenen L2 abans que L1, com a l'entrada: estable. Si canvies > per >= obtindràs [('18:05','L1'), ('18:30','L1'), ('18:30','L2')] — ordenat per hora igualment, però amb l'empat invertit.

Solució 3

(a) Fita de la inserció: n·k = 100.000 × 3 = 300.000 desplaçaments com a màxim (més les ~n comparacions barates: mateix ordre). (b) n·log₂ n ≈ 100.000 × 17 ≈ 1.700.000 operacions. La inserció fa ~5–6 vegades menys feina, amb un codi més simple i O(1) de memòria. (c) Recomanació: inserció, sempre que la premissa "k ≤ 3" estigui garantida. La pregunta de fons és la de 02-03: el cas favorable és el freqüent i està garantit? Si un dia el fitxer arriba en ordre arbitrari (una fallada upstream), la inserció es dispara a Θ(n²) ≈ 5·10⁹ operacions. Decisió d'enginyeria: o validar la premissa (mesurar el desordre abans de triar), o usar un híbrid que degradi amb elegància — exactament el que fa Timsort, com veurem a la propera lliçó.

L'ordenació per inserció manté un prefix ordenat i insereix cada element nou al seu lloc desplaçant els majors: estable (gràcies a una comparació estricta), in situ amb O(1) auxiliar, online, Θ(n) sobre dades ja ordenades i Θ(n²) en cas mitjà i pitjor cas — amb un cost real de "n + inversions" que la converteix en la reina del petit i del gairebé ordenat, com els panells d'arribades de RutaBus. Però el seu taló d'Aquil·les és evident: sobre les 10.000 expedicions diàries en ordre arbitrari, els ~25 milions d'operacions del cas mitjà no són acceptables. Per trencar la barrera de l'O(n²) hem de deixar de moure elements d'un en un i atacar el problema amb l'estratègia de 03-01: dividir la llista, ordenar les meitats i combinar-les. Aquesta és l'ordenació per mescla (merge sort) — i amb ella, per fi, resoldrem la recurrència T(n) = 2·T(n/2) + O(n) que vam deixar pendent al Mòdul 3.