El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algorismes d'Ordenació Avançats

Següent ►
►

A la lliçó anterior tota la màgia de la cerca binària depenia d'una premissa: les dades ja estaven ordenades. Aquesta lliçó paga aquest deute. Rutalia genera cada dia centenars de milers de registres de lliurament — al mes, milions — i necessita ordenar-los per (zona, hora) per consolidar rutes, per codi postal per paletitzar, per pes per tarifar. A aquesta escala, la diferència entre un algorisme O(n²) i un O(n log n) no és "una mica més lent": és la diferència entre 3 segons i diversos dies. Aquí estudiarem mergesort i quicksort (els dos grans divideix i venceràs), heapsort (cobrant el heap que vam construir a 01-04), la fita inferior Ω(n log n) que cap algorisme per comparació no pot batre, les ordenacions sense comparació que sí que la baten (counting sort i radix sort), i finalment Timsort: el que Python executa de debò quan crides sorted, i com esprémer-lo amb key= i l'estabilitat.

Contingut

  1. Per què O(n²) no serveix a escala
  2. Mergesort: divideix i venceràs amb garanties
  3. Quicksort: partició, pivot i el pitjor cas
  4. Heapsort en breu: el heap de 01-04 posat a ordenar
  5. La fita inferior Ω(n log n): l'arbre de decisió
  6. Ordenar sense comparar: counting sort i radix sort
  7. Timsort: el que Python usa realment (sorted, key=, estabilitat)
  8. Taula comparativa final

Per què O(n²) no serveix a escala

A 01-01 vam dibuixar la jerarquia de creixement: log n ≪ n ≪ n log n ≪ n². Posem-hi números de Rutalia. Suposa ~10⁸ operacions elementals per segon (ordre de magnitud raonable per a Python amb constants petites):

n (registres de lliurament) n log₂ n (mergesort) n² (bombolla/inserció)
10.000 (un barri, un dia) ~0,001 s ~1 s
1.000.000 (la ciutat, una setmana) ~0,2 s ~2,8 hores
10.000.000 (històric mensual) ~2,3 s ~11,6 dies

Els algorismes quadràtics (bombolla, selecció, inserció) no són "dolents": la inserció és de fet excel·lent per a n petit o dades gairebé ordenades, i veurem que Timsort la fa servir per dins. Però com a algorisme principal a l'escala de les dades de Rutalia queden descartats. Necessitem n log n, i hi ha tres camins clàssics per arribar-hi: partir per la meitat (mergesort), partir per un pivot (quicksort) i usar una estructura (heapsort).

Mergesort: divideix i venceràs amb garanties

L'estratègia és la mateixa que vam usar a 01-03 amb la recursió: resoldre dues meitats i combinar. L'operació clau és la mescla (merge): donades dues llistes ja ordenades, produir-ne una d'ordenada en O(n) comparant sempre els caps.

def mergesort(a):
    """Ordena `a` retornant una llista nova. Estable. O(n log n) garantit."""
    if len(a) <= 1:                      # cas base: 0 o 1 elements ja estan ordenats
        return a
    meitat = len(a) // 2
    esq = mergesort(a[:meitat])          # ordenar la meitat esquerra
    dre = mergesort(a[meitat:])          # ordenar la meitat dreta
    return mesclar(esq, dre)             # combinar en O(n)

def mesclar(esq, dre):
    resultat = []
    i = j = 0
    while i < len(esq) and j < len(dre):
        if esq[i] <= dre[j]:             # el <= (no <) es el que dona l'ESTABILITAT
            resultat.append(esq[i]); i += 1
        else:
            resultat.append(dre[j]); j += 1
    resultat.extend(esq[i:])             # el que quedi d'una de les dues meitats
    resultat.extend(dre[j:])
    return resultat

lliuraments = [(14, "E-072"), (9, "E-013"), (14, "E-031"), (11, "E-055"), (9, "E-088")]
print(mergesort(lliuraments))
# [(9, 'E-013'), (9, 'E-088'), (11, 'E-055'), (14, 'E-031'), (14, 'E-072')]

Tres observacions que importen:

  • Cost. La recurrència és T(n) = 2·T(n/2) + O(n): dos subproblemes de mida meitat més una mescla lineal. Pel teorema mestre de 01-02 (cas 2: la feina es reparteix per igual entre nivells), T(n) = Θ(n log n) — i és així sempre: millor cas, pitjor cas i cas mitjà. Mergesort no té sorpreses.
  • Estabilitat. El <= de la mescla fa que, davant d'empat, guanyi l'element de la meitat esquerra — és a dir, el que anava abans a la llista original. Dos lliuraments amb el mateix minut (9) conserven el seu ordre relatiu (E-013 abans que E-088). Guarda't aquest concepte: serà la peça central de la secció de Timsort.
  • Memòria. Aquesta versió crea llistes noves a cada nivell: O(n) de memòria auxiliar. Existeix el mergesort gairebé in-place, però és complex i rarament compensa; assumir l'O(n) extra és el preu estàndard. Quan ni tan sols hi cap una còpia a la RAM (històrics d'anys), la mescla es fa per blocs des de disc — això és l'ordenació externa, que desenvoluparem a 06-03.
graph TD
    A["[14,9,14,11,9]"] --> B["[14,9]"]
    A --> C["[14,11,9]"]
    B --> D["[14]"]
    B --> E["[9]"]
    C --> F["[14]"]
    C --> G["[11,9]"]
    G --> H["[11]"]
    G --> I["[9]"]
    D & E --> J["mescla: [9,14]"]
    H & I --> K["mescla: [9,11]"]
    F & K --> L["mescla: [9,11,14]"]
    J & L --> M["mescla: [9,9,11,11,14... ] resultat final"]

Quicksort: partició, pivot i el pitjor cas

Quicksort també divideix, però al revés que mergesort: la feina es fa abans de recursar, a la partició. Es tria un element pivot i es reorganitza l'array en tres zones: menors, iguals i majors que el pivot. Després, les zones de menors i majors s'ordenen recursivament — i no hi ha res a combinar, perquè la partició ja va deixar cada element al costat correcte.

Primer, la versió pedagògica (clara però amb memòria extra):

import random

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = random.choice(a)                      # pivot ALEATORI: clau, mira mes avall
    menors = [x for x in a if x < pivot]
    iguals = [x for x in a if x == pivot]
    majors = [x for x in a if x > pivot]
    return quicksort(menors) + iguals + quicksort(majors)

I la versió in-place que dóna fama a quicksort (partició de Lomuto, la més fàcil de raonar):

def quicksort_inplace(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = particio(a, lo, hi)
        quicksort_inplace(a, lo, p - 1)
        quicksort_inplace(a, p + 1, hi)

def particio(a, lo, hi):
    """Col·loca a[hi] (el pivot) a la seva posicio definitiva i la retorna."""
    idx = random.randint(lo, hi)                 # triar pivot a l'atzar...
    a[idx], a[hi] = a[hi], a[idx]                # ...i portar-lo al final
    pivot = a[hi]
    i = lo - 1                                    # frontera dels "menors o iguals"
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]              # l'intercanvi TRENCA l'estabilitat
    a[i + 1], a[hi] = a[hi], a[i + 1]            # pivot al seu lloc
    return i + 1

L'invariant de la partició (un altre cop invariants, com a 04-01): en acabar cada volta del bucle, a[lo..i] conté només elements <= pivot i a[i+1..j] només elements > pivot.

El pitjor cas O(n²) i com mitigar-lo

Si el pivot parteix l'array en meitats semblants, la recurrència és la de mergesort: Θ(n log n). Però si el pivot és sempre el mínim o el màxim, una "meitat" té n−1 elements: T(n) = T(n−1) + O(n) = O(n²). I quan passa això amb el pivot ingenu "primer element"? Amb dades ja ordenades o gairebé ordenades — exactament el cas més comú a la pràctica (l'històric de Rutalia arriba gairebé ordenat per timestamp, amb alguna correcció fora d'ordre). Un quicksort ingenu és pitjor com més fàcil sembla l'entrada.

Mitigacions, de més simple a més robusta:

Tècnica Idea Garantia
Pivot aleatori Cap adversari ni patró d'entrada no pot forçar el pitjor cas sistemàticament O(n log n) esperat, per a qualsevol entrada
Mediana de tres Pivot = mediana de a[lo], a[mig], a[hi] Evita els casos ordenat/invers; el pitjor cas continua sent possible
Introsort Quicksort que mesura la seva profunditat; si supera ~2·log n, canvia a heapsort O(n log n) garantit (així ho fa std::sort de C++)

Dos apunts més: la profunditat de recursió també és O(n) en el pitjor cas (en Python, RecursionError; es mitiga recursant només sobre la part petita i iterant sobre la gran), i la partició amb intercanvis no és estable — dos lliuraments empatats poden acabar en ordre invers a l'original. A canvi, quicksort ordena in-place (O(log n) de pila, sense array auxiliar) i les seves constants són excel·lents pel seu bon ús de la memòria cau: per això, ben implementat, sol guanyar a mergesort a la pràctica.

Heapsort en breu: el heap de 01-04 posat a ordenar

A 01-04 vam construir min-heaps amb heapq per a la cua de repartiment prioritari, i a 02-03 i 03-03 els vam reutilitzar per al millor-primer i per a Dijkstra. Heapsort és l'observació que un heap ja és un algorisme d'ordenació: construeix un heap amb els n elements (O(n) amb heapify) i extreu el mínim n vegades (n × O(log n)).

import heapq

def heapsort(a):
    h = list(a)
    heapq.heapify(h)                              # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]   # n extraccions O(log n)

Balanç: O(n log n) garantit (com mergesort), in-place en la seva versió clàssica sobre array (la de dalt usa una còpia per claredat), però no estable i amb constants pitjors que quicksort (els salts per l'arbre del heap castiguen la memòria cau). El seu paper modern és de xarxa de seguretat: és el pla B d'introsort quan quicksort degenera. No li dediquem més espai perquè la mecànica del heap ja la domines del mòdul 1.

La fita inferior Ω(n log n): l'arbre de decisió

Tenim tres algorismes O(n log n). Pregunta natural: es pot baixar més? Per a algorismes que només obtenen informació comparant parells d'elements, la resposta és no, i l'argument és preciós i intuïtiu:

  1. Un algorisme d'ordenació per comparació és, vist des de fora, un arbre de decisió: cada node intern és una pregunta "a[i] < a[j]?" amb dues branques (sí/no), i cada fulla és un resultat final — una permutació concreta de l'entrada.
  2. Amb n elements diferents hi ha n! permutacions possibles, i l'algorisme ha de poder produir qualsevol d'elles: l'arbre necessita almenys n! fulles (si dues permutacions diferents arribessin a la mateixa fulla, l'algorisme s'equivocaria almenys en una).
  3. Un arbre binari de profunditat d té com a molt 2^d fulles. Necessitem 2^d ≥ n!, és a dir d ≥ log₂(n!).
  4. Per l'aproximació de Stirling, log₂(n!) ≈ n·log₂ n − 1,44·n = Ω(n log n).

La profunditat de l'arbre és el nombre de comparacions en el pitjor cas. Conclusió: cap algorisme per comparació, per enginyós que sigui, no baixa d'Ω(n log n) en el pitjor cas. Mergesort i heapsort són, en aquest sentit, òptims. És la mateixa mena de resultat "d'impossibilitat" que la NP-duresa pràctica de 02-02, però molt més fort: aquí està demostrat sense condicions.

La lletra petita és la porta a la secció següent: la fita només s'aplica a algorismes que comparen. Si sabem alguna cosa més sobre les claus, podem fer trampa legal.

Ordenar sense comparar: counting sort i radix sort

Counting sort

Si les claus són enters en un rang petit [0, k), no cal comparar res: es compta quantes vegades apareix cada clau i es reconstrueix la sortida. Exemple Rutalia: ordenar els lliuraments del dia per zona (9 zones: la xarxa urbana del mòdul 3).

def counting_sort(items, clau, k):
    """Ordena `items` per clau(item), entera en [0, k). Estable. O(n + k)."""
    recompte = [0] * k
    for it in items:                      # 1) comptar ocurrencies de cada clau
        recompte[clau(it)] += 1
    posicio = [0] * k                     # 2) posicio inicial de cada clau a la sortida
    for c in range(1, k):                 #    suma acumulada dels recomptes
        posicio[c] = posicio[c - 1] + recompte[c - 1]
    sortida = [None] * len(items)
    for it in items:                      # 3) col·locar cada item al seu forat, EN ORDRE
        c = clau(it)
        sortida[posicio[c]] = it          #    recorrer en ordre original => estable
        posicio[c] += 1
    return sortida

ZONES = ["ALM", "MER", "EST", "UNI", "RIO", "CEN", "IND", "HOS", "PAR"]
INDEX = {z: i for i, z in enumerate(ZONES)}
lliuraments = [("E-01", "CEN"), ("E-02", "ALM"), ("E-03", "CEN"), ("E-04", "MER")]
print(counting_sort(lliuraments, clau=lambda e: INDEX[e[1]], k=9))
# [('E-02', 'ALM'), ('E-04', 'MER'), ('E-01', 'CEN'), ('E-03', 'CEN')]

Cost O(n + k): lineal si k = O(n). Amb n = 1.000.000 de lliuraments i k = 9 zones, és imbatible. La condició d'aplicabilitat és dura: claus enteres (o mapejables a enters) en un rang k petit. Ordenar per import en cèntims fins a 10.000 EUR (k = 10⁶) encara val; ordenar per timestamp de nanosegons, no.

Radix sort

I si el rang és gran però les claus tenen dígits? Radix sort (LSD, least significant digit) ordena pel dígit menys significatiu, després pel següent, etc., usant a cada passada una ordenació estable (counting sort). L'estabilitat és el que fa que les passades anteriors no es destrueixin: en ordenar pel segon dígit, els empats conserven l'ordre pel primer.

Exemple canònic de Rutalia: paletitzar per codi postal de 5 dígits.

def radix_sort_cp(lliuraments, cp):
    """Ordena per codi postal de 5 digits: 5 passades de counting sort. O(5·(n+10))."""
    for d in range(4, -1, -1):                       # del digit menys al mes significatiu
        lliuraments = counting_sort(lliuraments, clau=lambda e: int(cp(e)[d]), k=10)
    return lliuraments

paquets = [("P-1", "08025"), ("P-2", "08013"), ("P-3", "28004"), ("P-4", "08025")]
print(radix_sort_cp(paquets, cp=lambda p: p[1]))
# [('P-1', '08025')... ordenats 08013, 08025, 08025, 28004]

Cost O(d · (n + b)) amb d dígits en base b. Per a codis postals, d = 5 i b = 10: lineal en n amb constant 5. La mateixa idea ordena enters de 64 bits en 8 passades de base 256 — així ordenen claus numèriques moltes biblioteques d'alt rendiment. La fita Ω(n log n) no es viola: no estem comparant, estem explotant l'estructura de la clau.

Timsort: el que Python usa realment

Quan escrius sorted(lliuraments) o lliuraments.sort(), Python no executa cap dels algorismes de llibre anteriors en estat pur: executa Timsort (creat per Tim Peters per a CPython el 2002; adoptat després per Java per a objectes i per molts altres llenguatges). Timsort és un híbrid mergesort + inserció dissenyat per a dades reals, no aleatòries:

  • Detecta runs: trams ja ordenats (ascendents o descendents, que inverteix). L'històric de Rutalia arriba gairebé ordenat per timestamp: Timsort detecta aquests trams enormes i es limita a mesclar-los. Sobre dades ja ordenades és O(n).
  • Inserció per a trams curts: els runs de menys de ~32 elements s'estenen amb ordenació per inserció — l'algorisme O(n²) que vam descartar, imbatible en n minúscul.
  • Mescles intel·ligents: apila els runs i els mescla amb regles que equilibren mides, amb galloping per saltar blocs quan una meitat domina.
  • Garanties: O(n log n) en el pitjor cas, O(n) en el millor, i — crucial — estable.

Moralitat d'enginyeria: en Python no reimplementis quicksort per a producció. sorted està escrit en C, és adaptatiu i estable; el teu quicksort en Python pur serà desenes de vegades més lent. Els algorismes d'aquesta lliçó s'estudien per entendre costos, garanties i quan una ordenació especialitzada (counting/radix, ordenació externa) supera el genèric — no per substituir sorted.

key=, estabilitat i ordenar per múltiples criteris

El que sí que faràs servir cada dia és la interfície. key= rep una funció que extreu la clau de cada element (es crida una vegada per element, no a cada comparació):

from operator import itemgetter, attrgetter

lliuraments = [
    {"id": "E-31", "zona": "CEN", "hora": "10:30", "pes": 7.5},
    {"id": "E-12", "zona": "ALM", "hora": "09:15", "pes": 2.0},
    {"id": "E-77", "zona": "CEN", "hora": "08:05", "pes": 12.0},
    {"id": "E-45", "zona": "ALM", "hora": "09:15", "pes": 5.5},
]

# Criteri compost en una passada: per zona i, dins de zona, per hora
per_ruta = sorted(lliuraments, key=lambda e: (e["zona"], e["hora"]))
# itemgetter fa el mateix i es mes rapid: key=itemgetter("zona", "hora")

# Criteris amb sentits BARREJATS (zona ascendent, pes descendent):
# opcio A — negar el criteri numeric dins de la tupla:
mixta = sorted(lliuraments, key=lambda e: (e["zona"], -e["pes"]))

# opcio B — ordenacions successives explotant l'ESTABILITAT,
# del criteri MENYS significatiu al MES significatiu:
tmp = sorted(lliuraments, key=itemgetter("pes"), reverse=True)   # 1r el secundari
mixta2 = sorted(tmp, key=itemgetter("zona"))                     # 2n el primari
assert mixta == mixta2

L'opció B és exactament el truc de radix sort a nivell d'usuari: com que sorted és estable, la segona ordenació no desfà els empats que va deixar la primera. És la tècnica imprescindible quan el criteri secundari no es pot negar (cadenes descendents, per exemple). I és la raó per la qual l'estabilitat, que semblava un tecnicisme a mergesort, és una propietat de primera classe a la pràctica.

Taula comparativa final

Algorisme Millor Mitjà Pitjor Memòria extra Estable In-place Quan triar-lo
Inserció O(n) O(n²) O(n²) O(1) Sí Sí n petit o gairebé ordenat (Timsort la usa per dins)
Mergesort O(n log n) O(n log n) O(n log n) O(n) Sí No Garanties + estabilitat; base de l'ordenació externa (06-03)
Quicksort (pivot aleatori) O(n log n) O(n log n) O(n²) O(log n) pila No Sí Màxim rendiment in-place; base d'introsort
Heapsort O(n log n) O(n log n) O(n log n) O(1) No Sí Garantia sense memòria extra; pla B d'introsort
Counting sort O(n + k) O(n + k) O(n + k) O(n + k) Sí No Claus enteres en rang k petit (zones)
Radix sort (LSD) O(d·(n+b)) O(d·(n+b)) O(d·(n+b)) O(n + b) Sí No Claus de d dígits/bytes (codis postals)
Timsort (sorted) O(n) O(n log n) O(n log n) O(n) Sí No El defecte correcte en Python, adaptatiu a dades reals

Errors Comuns i Consells

  • Reimplementar l'ordenació en producció. L'error número u. sorted (Timsort en C) guanya a qualsevol implementació teva en Python pur. Implementa per aprendre; desplega la biblioteca.
  • Quicksort amb pivot fix sobre dades gairebé ordenades. El pitjor cas O(n²) no és teòric: apareix just amb l'entrada més habitual. Pivot aleatori o mediana de tres, sempre.
  • Suposar que tota ordenació és estable. El sorted de Python ho és; quicksort i heapsort no; numpy.sort per defecte (quicksort) tampoc. Si encadenes criteris amb ordenacions successives, verifica l'estabilitat de l'algorisme que usis o el resultat serà subtilment incorrecte.
  • key= amb feina cara recalculada. key s'avalua una vegada per element, cosa que ja és òptima — però si la clau requereix parsejar una data o consultar un dict, extreu aquest càlcul si has d'ordenar diverses vegades (patró decorate-sort-undecorate si cal).
  • Usar counting sort amb k enorme. O(n + k) és lineal només si k = O(n). Amb claus de 64 bits, l'array de recompte no cap a la memòria de cap servidor de Rutalia. Per a rangs grans amb estructura de dígits: radix sort.
  • Comparar amb cmp mental en lloc de claus. En Python 3 no existeix el paràmetre cmp; pensa sempre "quina tupla-clau representa el meu criteri?" — gairebé qualsevol criteri compost s'expressa com a tupla, amb negacions per invertir camps numèrics.
  • Consell: per a dades que "arriben gairebé ordenades amb excepcions" (l'històric de Rutalia després de correccions manuals), mesura abans d'optimitzar: Timsort ja és gairebé O(n) en aquest cas, i potser no necessites res més.

Exercicis

Exercici 1 — Consolidació de rutes. Donada una llista de lliuraments (id, zona, hora, pes) (tuples), produeix l'ordre de treball de Rutalia: per zona alfabètica ascendent, dins de cada zona per hora ascendent, i a igualtat de totes dues, el paquet més pesant primer. Resol-ho de dues maneres: (a) amb una sola crida a sorted i una tupla-clau; (b) amb ordenacions successives explotant l'estabilitat. Comprova que coincideixen.

Exercici 2 — Quin algorisme triaries? Per a cada escenari de Rutalia, tria l'algorisme més adequat de la taula comparativa i justifica-ho en una frase: (a) ordenar 5.000.000 de paquets per codi postal de 5 dígits; (b) ordenar 40 parades d'una furgoneta per hora compromesa, en un microcontrolador amb memòria mínima; (c) ordenar l'històric mensual per timestamp sabent que arriba ordenat al 99 % amb algunes correccions intercalades; (d) ordenar 2.000.000 de lliuraments per zona (9 valors) conservant l'ordre d'arribada dins de cada zona.

Exercici 3 — Mescla de k rutes (pont amb 01-04). Cadascuna de les k furgonetes de Rutalia retorna el seu registre del dia ja ordenat per hora. Escriu mesclar_k(llistes) que produeixi el registre global ordenat en O(N log k), on N és el total de registres — usa un heap amb tuples (hora, index_llista, index_element) com a 01-04. Per què és millor que concatenar i cridar sorted? (Pista: pensa en el millor cas i en la memòria; nota també que aquesta mescla de k vies és el cor de l'ordenació externa de 06-03.)

Solucions

Solució 1:

lliuraments = [
    ("E-31", "CEN", "10:30", 7.5),
    ("E-12", "ALM", "09:15", 2.0),
    ("E-77", "CEN", "08:05", 12.0),
    ("E-45", "ALM", "09:15", 5.5),
]

# (a) una passada: tupla-clau amb el pes negat (numeric => es pot invertir negant)
a = sorted(lliuraments, key=lambda e: (e[1], e[2], -e[3]))

# (b) successives, del criteri MENYS significatiu al MES significatiu:
b = sorted(lliuraments, key=lambda e: e[3], reverse=True)   # 3r criteri: pes desc
b = sorted(b, key=lambda e: e[2])                           # 2n criteri: hora asc
b = sorted(b, key=lambda e: e[1])                           # 1r criteri: zona asc

assert a == b
print(a)
# [('E-45','ALM','09:15',5.5)... no: ('E-12','ALM','09:15',2.0) va DESPRES d'E-45 (5.5 > 2.0)]
# Resultat: E-45, E-12, E-77, E-31

Detall a interioritzar a (b): l'ordre de les passades és l'invers a la prioritat dels criteris, i funciona únicament perquè sorted és estable — cada passada respecta els empats que van deixar les anteriors.

Solució 2:

  • (a) Radix sort LSD amb counting sort estable per dígit: 5 passades O(n), molt per sota de n log n per a n = 5·10⁶. (A la pràctica, mesurar contra sorted: la constant del C compilat de vegades guanya igualment.)
  • (b) Heapsort (o inserció, amb n = 40 gairebé és igual): O(n log n) garantit amb O(1) de memòria extra; sense l'array auxiliar de mergesort ni el risc O(n²) de quicksort.
  • (c) Timsort (sorted tal qual): la seva detecció de runs el fa gairebé O(n) sobre dades gairebé ordenades; qualsevol esforç addicional és prematur.
  • (d) Counting sort per índex de zona (k = 9): O(n + 9) lineal i estable, que és exactament el requisit de "conservar l'ordre d'arribada dins de cada zona".

Solució 3:

import heapq

def mesclar_k(llistes):
    """Mescla k llistes ordenades en O(N log k)."""
    sortida = []
    heap = [(lst[0], i, 0) for i, lst in enumerate(llistes) if lst]  # caps
    heapq.heapify(heap)                                              # O(k)
    while heap:
        valor, i, j = heapq.heappop(heap)         # minim dels k caps: O(log k)
        sortida.append(valor)
        if j + 1 < len(llistes[i]):               # avancar a la llista i
            heapq.heappush(heap, (llistes[i][j + 1], i, j + 1))
    return sortida

rutes = [["08:10", "09:40", "12:00"], ["08:05", "10:15"], ["09:00", "09:05", "11:30"]]
print(mesclar_k(rutes))
# ['08:05', '08:10', '09:00', '09:05', '09:40', '10:15', '11:30', '12:00']

Avantatges respecte a sorted(concatenació): (1) cost O(N log k) davant d'O(N log N) — amb k = 20 furgonetes i N = 10⁶, log k ≈ 4,3 davant de log N ≈ 20; (2) és un algorisme de streaming: pot emetre resultats sense retenir les k llistes completes en memòria si arriben com a fluxos, que és just el que necessita la mescla de blocs de l'ordenació externa (06-03). A la biblioteca estàndard ja existeix: heapq.merge(*llistes).

Conclusió

Ja tens el mapa complet de l'ordenació: els quadràtics moren a escala (encara que la inserció sobreviu com a peça interna), mergesort i heapsort garanteixen el n log n que quicksort només promet en mitjana (i que introsort converteix en garantia combinant-los), i la fita Ω(n log n) de l'arbre de decisió demostra que per comparació no es pot fer millor — però counting i radix sort l'esquiven legalment quan la clau té estructura, com els codis postals o les 9 zones de Rutalia. I en el dia a dia amb Python, la resposta és gairebé sempre sorted amb una bona tupla-clau, recolzant-te en l'estabilitat de Timsort per compondre criteris. Quan els volums desbordin la RAM i calgui ordenar a disc o en diverses màquines, la mescla de k vies del darrer exercici serà la peça clau — ho veurem a 06-03.

Amb cercar (04-01) i ordenar (04-02) dominats sobre dades estàtiques, queda el tercer tipus de cerca, el més ambiciós: cercar no un valor en un array, sinó una solució en un univers de possibilitats — la ruta de repartiment entre obstacles, la seqüència de moviments que porta de l'estat inicial a l'objectiu. A la propera lliçó (04-03) formalitzem els espais d'estats, retrobem BFS, DFS i Dijkstra en la seva versió implícita, i complim per fi la promesa del mòdul 3: A*, el "Dijkstra amb brúixola".

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats