Merge sort (04-03) ens va donar la garantia Θ(n log n)... pagant O(n) de memòria. Quick sort ataca la mateixa pregunta amb la mateixa estratègia mare — divideix i venceràs (03-01) — però invertint on viu l'esforç: en merge sort dividir és un tall ximple i tota la feina és a combinar; en quick sort tota la feina és a dividir (la partició al voltant d'un pivot) i combinar és literalment no fer res. Aquesta inversió li regala el que merge sort no tenia — ordena in situ, sense memòria auxiliar lineal — a canvi del risc que venim anunciant des de 02-03: un cas mitjà excel·lent O(n log n) convivint amb un pitjor cas O(n²) que cal saber domar. En aquesta lliçó construirem la partició de Lomuto pas a pas, la traçarem sobre les arribades de RutaBus, saldarem la promesa de l'anàlisi de casos i tancarem amb la taula comparativa de les tres ordenacions del curs.

1. La idea invertida: la feina es fa en dividir
2. La partició de Lomuto, pas a pas
3. Traça de la partició sobre el panell de RutaBus
4. Implementació recursiva completa
5. Anàlisi de casos: la promesa de 02-03, cobrada
6. Domar el pitjor cas: pivot aleatori i mediana de tres
7. Estabilitat, espai i la taula final de les tres ordenacions

El pla de quick sort per ordenar un tram de la llista:

1. Dividir (aquí hi ha tota la feina): tria un element com a pivot i reorganitza el tram perquè quedi [menors o iguals que el pivot] + [pivot] + [majors]. Aquesta reorganització s'anomena partició i deixa el pivot a la seva posició final definitiva.
2. Conquerir: ordena recursivament el bloc de l'esquerra i el de la dreta.
3. Combinar: res. Zero. Si l'esquerra queda ordenada, el pivot és al seu lloc i la dreta queda ordenada, la llista ja està ordenada — els blocs no es toquen entre si.

Compara'l amb merge sort, el seu germà especular:

La darrera fila és la font de tota la glòria i tota la misèria de quick sort. Merge sort talla pel centre per construcció; quick sort talla per on caigui el pivot. Si el pivot resulta ser mitjà, meitats perfectes; si resulta ser el mínim o el màxim, una "meitat" buida i una altra amb gairebé tot — i aquí comença el drama de l'apartat 5.

Hi ha diversos esquemes de partició; el de Lomuto és el més fàcil de raonar. Treballa sobre el tram llista[esq..dret], pren com a pivot el darrer element i manté una frontera i que separa el que ja s'ha classificat com a "≤ pivot" de la resta:

L'invariant del bucle (la nostra eina de 04-01) és una foto en tres zones: en tot moment, llista[esq..i] conté elements ≤ pivot, llista[i+1..j−1] conté elements > pivot, i de j en endavant hi ha el pendent. Cada volta examina llista[j]:

• Si és > pivot: no cal fer res — ja està enganxat a la zona de majors.
• Si és ≤ pivot: s'intercanvia amb el primer element de la zona de majors (llista[i+1]), amb la qual cosa totes dues zones creixen una posició mantenint l'invariant.

En acabar el bucle, l'intercanvi final planta el pivot entre les dues zones: tot el que té a l'esquerra és ≤ i tot el que té a la dreta és >. El pivot ja no es mourà mai més.

Particionem el panell complet d'arribades de la L1 (tram 0..4, pivot = "18:31", el darrer):

La funció retorna 2: el pivot "18:31" ha quedat a l'índex 2, la seva posició final a la llista ordenada — pots comprovar-ho: és la mediana de les cinc hores. A la seva esquerra, {18:07, 18:12} (desordenats entre si, tant és: ja són "els correctes"); a la seva dreta, {18:42, 18:59}. Cada meitat es resoldrà amb una crida recursiva, i en aquest exemple totes dues són trams de 2 que una partició més deixa llestos.

Cost d'una partició: el bucle recorre el tram una vegada — O(n) en la mida del tram, amb intercanvis dins de la mateixa llista.

Detalls:

• Treballa sobre la mateixa llista amb índexs esq/dret, sense crear subllistes — a diferència dels talls amb còpia de merge_sort. Per això és in situ.
• Les crides recursives exclouen p: el pivot ja està col·locat per sempre. Incloure'l (quick_sort(llista, esq, p)) provoca recursió infinita tan bon punt un tram no s'encongeix.
• El cas base esq >= dret cobreix trams d'1 element i també els buits (esq > dret), que apareixen quan el pivot cau en un extrem.

A 02-03 vam anunciar quick sort com "l'exemple cèlebre" de la bretxa cas mitjà/pitjor cas. Cobrem la promesa. El cost total és la suma de totes les particions, i quant sumen depèn d'on cauen els pivots:

Millor cas — Θ(n log n): pivots mitjans. Si cada pivot parteix el seu tram en dues meitats ≈ iguals, l'arbre de crides és el de merge sort: log₂ n nivells, i les particions de cada nivell sumen O(n) en conjunt (recorren trams disjunts que cobreixen la llista). Total: la recurrència T(n) = 2·T(n/2) + O(n) que vam resoldre a 04-03 → Θ(n log n).

Pitjor cas — Θ(n²): pivots extrems. Si cada pivot resulta ser el màxim (o el mínim) del seu tram, la partició deixa un bloc de n−1 i un altre de buit. La recurrència degenera en T(n) = T(n−1) + O(n): particions de n, n−1, n−2, ... — la suma aritmètica n(n−1)/2 de 02-01 → Θ(n²). I aquí la ironia cruel: amb el pivot de Lomuto (el darrer element), aquesta catàstrofe la provoca... una llista ja ordenada (o invertida). Cada pivot és el màxim del seu tram, i l'algorisme "ràpid" s'arrossega a n²: exactament l'entrada on la humil inserció (04-02) corria en Θ(n). A més la recursió s'apila n nivells: amb el nostre panell de 10.000 arribades ja ordenades, Python rebenta el límit de pila (RecursionError, recorda 02-02) abans i tot d'acabar d'anar lent.

Cas mitjà — Θ(n log n): la realitat estadística. Amb entrades en ordre aleatori (distribució que cal declarar, 02-03), el pivot rarament és extrem. No cal que sigui la mediana: n'hi ha prou que caigui "pel centre" raonablement sovint. Fins i tot un pivot que només garanteixi un repartiment 10 %–90 % manté la profunditat logarítmica (log amb una altra base — constant fora, 01-03). L'anàlisi formal dona ≈ 1,39·n·log₂ n comparacions esperades: Θ(n log n) amb una constant petita. Aquesta constant petita, més la feina in situ sense còpies (localitat i sense cost de memòria), és el que fa que quick sort guanyi a merge sort a la pràctica gairebé sempre... llevat del dia que no.

Això és 02-03 aplicat: si les teves entrades són aleatòries i el volum mana, el cas mitjà et representa; si un usuari (o un atacant — taula d'"entrades hostils" de 02-03) et pot enviar l'entrada patològica, el pitjor cas és el teu contracte. Un endpoint de RutaBus que ordeni amb aquest quick sort el que enviï el client és un atac de denegació de servei esperant a passar: n'hi ha prou d'enviar llistes ja ordenades.

El pitjor cas no es pot eliminar, però sí fer-lo improbable o impracticable:

Pivot aleatori. Abans de particionar, intercanvia el darrer element amb un de triat a l'atzar:

Això converteix quick sort en un algorisme aleatoritzat (01-02): el cost ja no depèn de l'entrada sinó dels daus interns. Cap entrada és patològica per si mateixa — ni l'ordenada, ni la de l'atacant, que ja no pot predir els pivots —; el pitjor cas continua existint (podrien sortir n pivots extrems seguits) però la seva probabilitat s'enfonsa exponencialment. El cost esperat és Θ(n log n) per a tota entrada.

Mediana de tres. Alternativa determinista i barata: usar com a pivot la mediana entre el primer, el central i el darrer element del tram. Neutralitza en sec els casos "ja ordenada / invertida" (la mediana de tres d'una llista ordenada és l'element central: partició perfecta) i millora les constants a la pràctica, tot i que un adversari que conegui la regla encara pot construir entrades dolentes — per això les biblioteques serioses combinen trucs o canvien d'algorisme si detecten que la recursió s'enfonsa massa (els anomenats introsort).

No és estable. Els intercanvis de la partició salten per sobre de trams sencers i poden invertir empats. Amb el panell de tuples de 04-02, [("18:30", "L2"), ("18:05", "L1"), ("18:30", "L1")] i pivot ("18:30", "L1"): la partició col·loca el pivot davant del ("18:30", "L2") que originalment el precedia — empat invertit. Si necessites ordenar per hora conservant l'ordre per línia, quick sort no és la teva eina (merge sort o Timsort sí).

Espai: in situ, amb matís. La partició no usa memòria auxiliar — a diferència de l'O(n) de merge sort (02-02), aquí no hi ha llistes noves. L'única despesa és la pila de recursió: O(log n) marcs quan les particions són equilibrades, però O(n) en el pitjor cas — una altra raó per domar els pivots.

La taula que resumeix tres lliçons d'ordenació:

Cap columna domina les altres: és un menú de trade-offs, no un podi. Les biblioteques reals ho confirmen component: Timsort (Python) = merge + inserció; els introsort de C++ = quick + heap + inserció.

• Incloure el pivot a les crides recursives (quick_sort(llista, esq, p)): si un tram no s'encongeix, recursió infinita. El pivot està col·locat: s'exclou sempre (p − 1 i p + 1).
• Oblidar que la llista ja ordenada és el pitjor cas de Lomuto. És antiintuïtiu (l'entrada "fàcil"!) i molt freqüent en producció, perquè les dades reals arriben sovint gairebé ordenades. Si uses pivot fix, el teu benchmark amb dades aleatòries mentirà sobre la teva producció. Pivot aleatori o mediana de tres, sempre.
• Molts duplicats degraden Lomuto: si el panell té milers d'arribades amb la mateixa hora, tots els "≤ pivot" cauen al mateix costat i les particions surten desequilibrades encara que el pivot sigui raonable. La solució clàssica és la partició en tres zones (<, =, >), que agrupa els iguals al pivot i no els torna a tocar.
• Assumir estabilitat: quick sort ordena bé, així que l'error no dona símptomes fins que un empat importa (i llavors és un bug "aleatori" difícil de reproduir). Davant de claus amb empats rellevants, merge/Timsort.
• Consell: en Python real, sorted()/list.sort() (Timsort) guanyen a qualsevol quick sort casolà — implementar-lo aquí és per entendre'n el mecanisme i els trade-offs, que reapareixen tal qual a les biblioteques de C, C++, Java o Rust que sí que l'usen.

Traça la partició de Lomuto (taula com la de l'apartat 3) sobre ["18:20", "18:55", "18:04", "18:47", "18:33"] (pivot "18:33"). Indica la posició retornada i quins dos subtrams s'ordenaran recursivament.

Sense executar codi: quantes comparacions fa aquest quick sort (Lomuto, pivot darrer) sobre el panell ja ordenat ["18:01", "18:02", "18:03", "18:04", "18:05"]? Enumera el pivot de cada crida i generalitza el compte a n. Quin algorisme d'aquest mòdul hauria fet només n−1 comparacions amb aquesta entrada?

L'app de RutaBus necessita les 10 arribades més primerenques d'un llistat de n = 100.000, i a algú li fa mal ordenar-lo sencer. Basant-te en la partició: escriu k_mes_primerenques(llista, k) que usi la idea de quick sort però recursant només pel costat on hi ha la resposta (aquest algorisme s'anomena quickselect). Raona per què el seu cost mitjà és O(n) i no O(n log n). Pista: és l'argument de "comptar meitats" de 04-01, però sumant en comptes de comptant.

Solució 1

Pivot "18:33", i = −1:

Retorna 2. Subtrams recursius: [18:20, 18:04] (índexs 0–1) i [18:47, 18:55] (índexs 3–4). Fixa't en l'intercanvi "amb si mateix" de j = 0: inofensiu i normal en Lomuto.

Solució 2

Amb la llista ordenada, cada pivot (el darrer) és el màxim del seu tram: la partició compara tot el tram, deixa el pivot on era i recursa sobre un tram amb un element menys. Pivots successius: 18:05, 18:04, 18:03, 18:02. Comparacions: 4 + 3 + 2 + 1 = 10. En general: (n−1) + (n−2) + ... + 1 = n(n−1)/2 — la suma aritmètica, Θ(n²). La inserció (04-02) hauria fet n−1 = 4 comparacions: el seu millor cas és exactament el pitjor d'aquest quick sort.

Solució 3

Després de quickselect, les k−1 posicions anteriors contenen (sense ordre) els elements menors: llista[:k] són exactament les k més primerenques. Cost mitjà: cada partició costa la mida del tram, però en recursar només per un costat els trams esperats es redueixen a la meitat: n + n/2 + n/4 + ... ≤ 2n → O(n). Comparat amb el "comptar meitats" de 04-01: allà els nivells es comptaven (log n); aquí els seus costos se sumen (sèrie geomètrica → 2n). Ordenar sencer costaria n log n ≈ 1,7 milions d'operacions; quickselect, ≈ 200.000.

Quick sort és el mirall de merge sort: mateix pare (divideix i venceràs), esforç oposat — la partició de Lomuto col·loca el pivot a la seva posició definitiva en O(n) i deixa dos subproblemes independents, sense res a combinar. Hem cobrat la promesa de 02-03: cas mitjà Θ(n log n) amb constant petita que el fa el més ràpid a la pràctica, pitjor cas Θ(n²) que — ironia — dispara l'entrada ja ordenada amb pivot ingenu, i les dues vacunes: pivot aleatori (un algorisme aleatoritzat dels de 01-02, cost esperat n log n per a tota entrada) i mediana de tres. No és estable, però sí in situ — l'avantatge espacial que merge sort no tenia —, i la taula final d'inserció/merge/quick mostra que triar ordenació és triar trade-offs, no campions. Amb les llistes dominades, canviem d'estructura: la xarxa de parades de RutaBus que vam modelar com a graf a 03-04 ens espera amb la pregunta més útil de tota l'app — quin és el camí més curt entre dues parades? — i amb l'algorisme que a 03-02 vam anunciar com "el greedy que sí que és òptim": Dijkstra.