A la lliçó anterior vam descobrir que la cerca binària resol en vint comparacions el que a la lineal li costa un milió, però exigeix un requisit que TascaFàcil encara no compleix: que les dades estiguin ordenades. També va quedar dit que ordenar costa. És hora d'esbrinar quant i com, obrint la segona caixa negra del curs: què fa sorted per dins.

Ordenar és, probablement, l'operació més rendible que aprendràs. No només perquè un llistat ordenat es llegeix millor: una col·lecció ordenada habilita la cerca binària, permet detectar duplicats d'un cop d'ull, fa trivials els informes per rangs i converteix «els cinc encàrrecs més urgents» en un tall. En aquesta lliçó implementaràs tres algorismes clàssics amb la seva traça pas a pas, entendràs què significa que una ordenació sigui estable i acabaràs fent servir l'eina de debò —sorted i .sort()— sabent per fi què passa a dins.

1. Què significa ordenar i per què compensa
2. El criteri d'ordre
3. Estabilitat: per què importa a Estudi Alba
4. Ordenació per selecció
5. Ordenació per inserció
6. Ordenació per bombolla i el sentinella
7. Els tres algorismes, comparats
8. Algorismes per divisió: mergesort i quicksort
9. Ordenar en Python de debò
10. Mesurar la diferència amb time.perf_counter()
11. TascaFàcil v0.13: prioritat, dies i el pla de demà
12. Errors comuns i consells
13. Exercicis
14. Conclusió

Ordenar és reorganitzar els elements d'una col·lecció de manera que cadascun sigui «menor o igual» que el següent segons un criteri. La definició amaga dues decisions que cal prendre abans d'escriure una sola línia: què es compara i què es fa amb els empats. La primera és el criteri d'ordre, la segona és l'estabilitat, i les dues seccions següents se n'ocupen.

El que fa de l'ordenació una inversió i no una despesa és tot allò que habilita després:

Per això ordenar un cop i consultar moltes vegades gairebé sempre guanya a consultar sense ordenar. És el mateix raonament de l'índex invertit de 06-01: pagar un cost inicial perquè tot el que vingui després surti barat.

Els nombres i els textos tenen un ordre natural (3 < 7, "Luis" < "Marta" per l'ordre dels caràcters que vas veure a 05-02), però un diccionari no: ningú no sap si «la tasca del cartell» és major o menor que «la del menú». El criteri d'ordre és la regla que converteix cada element en una cosa comparable.

Aquest key és el callback de 04-05: una funció que rep un element i retorna el valor pel qual es compara. Tots els algorismes d'aquesta lliçó s'escriuen primer comparant nombres, perquè així es veu el mecanisme, i després es generalitzen amb key. La idea clau és que l'algorisme d'ordenació i el criteri són coses separades: el mateix algorisme ordena per dies, per títol o per prioritat canviant només la funció de comparació.

Una ordenació és estable quan els elements que empaten conserven l'ordre que tenien abans. Sona a subtilesa acadèmica fins que se'n veu un cas real.

La Marta ordena l'agenda per dies estimats, de menys a més, per veure primer el que es despatxa ràpid:

Després la reordena per prioritat. Amb una ordenació estable, dins d'«alta» es manté l'ordre anterior: primer Logotip Vidal (2 dies) i després Cartell fira (3). El resultat és el que la Marta volia: ordenat per prioritat i, a igualtat de prioritat, per dies. Amb una ordenació inestable, aquestes dues tasques podrien sortir en qualsevol ordre i la feina de la primera ordenació es perdria.

D'aquí la tècnica clàssica: per ordenar per diversos criteris, s'ordena pel menys important primer i pel més important al final, i l'estabilitat conserva l'anterior. A la secció 9 veuràs l'alternativa moderna, que encara és més clara. I retén la dada: sorted() i .sort() de Python són estables, sempre, i això ho garanteix el llenguatge.

La idea és la que faries servir amb una mà de cartes: buscar la més petita de totes, posar-la la primera; buscar la més petita de les que queden, posar-la la segona, i així successivament.

Tres coses per entendre aquí. El bucle exterior recorre les posicions que es van fixant; arriba fins a n - 1 perquè quan queda un sol element ja està col·locat per força. El bucle interior és la cerca del mínim del patró de 03-02, però desant la posició i no el valor, perquè cal intercanviar. I l'intercanvi a, b = b, a és el desempaquetatge de tuples de 05-04 fent la seva feina sense variable auxiliar.

Traça sobre els dies estimats [3, 5, 2, 4, 1]:

Fixa't en la passada 4: la llista ja estava ordenada i tot i així l'algorisme va fer la passada completa. La selecció no s'assabenta mai que ha acabat: sempre fa exactament el mateix nombre de comparacions, estigui la llista ordenada o del revés. A canvi, fa molt pocs intercanvis: un per passada com a màxim, cosa que la fa interessant quan moure un element és car.

I un advertiment important per a la secció 7: la selecció clàssica no és estable, precisament per aquest intercanvi a distància, que pot saltar un element igual per damunt d'un altre.

És la que fa servir tothom en ordenar cartes a la mà: s'agafa la següent i es col·loca al seu lloc entre les que ja estan ordenades, desplaçant les majors cap a la dreta.

La part delicada és el while, i convé llegir-lo amb calma. Retrocedeix des de la posició anterior mentre es compleixin dues condicions: que no ens hàgim sortit per l'esquerra (j >= 0) i que l'element examinat sigui major que el que portem a la mà. L'ordre d'aquestes dues condicions no és casual: gràcies a l'avaluació mandrosa de l'and que vas veure a 02-02, si j arriba a -1 la segona comparació ni s'avalua, i així no s'accedeix a valors[-1], que en Python seria l'últim element i produiria un error silenciós.

Traça sobre [3, 5, 2, 4, 1]; la part ja ordenada va en negreta:

Aquí hi ha la gran virtut de la inserció, i és la raó que continuï viva al programari professional: amb dades gairebé ordenades és rapidíssima. Si cada element ja és a prop del seu lloc, el while fa una volta o cap i l'ordenació sencera costa poc més que un recorregut. Sobre una llista ja ordenada, la inserció fa una sola comparació per element i cap desplaçament: és el millor cas possible. I és estable, perquè el while s'atura així que troba un element igual i mai no el salta.

La bombolla compara veïns i intercanvia els que estan del revés, passada rere passada, fins que no en queda cap de desordenat. A cada passada el major dels que queden «flota» fins al final, d'aquí el nom.

Dues millores conviuen en aquest codi. El range(n - 1 - passada) escurça cada passada, perquè després de la primera l'últim element ja és el major i no cal tornar-lo a mirar. I hi_ha_hagut_canvi és el sentinella: el patró bandera de 03-02 aplicat aquí. Si una passada completa no intercanvia res, la llista està ordenada i el break surt del bucle. Sense sentinella, la bombolla faria sempre totes les passades encara que la llista arribés ja ordenada.

Traça sobre [3, 5, 2, 4, 1], mostrant l'estat al final de cada passada:

Amb cinc elements, range(n - 1) dona quatre passades i aquí s'esgoten totes. Però si la llista d'entrada fos [1, 2, 3, 4, 5], la primera passada no intercanviaria res, hi_ha_hagut_canvi continuaria en False i el break acabaria la feina amb quatre comparacions en total. Aquest és tot el valor del sentinella.

La bombolla és estable —només intercanvia veïns estrictament desordenats, mai iguals— i és, a la pràctica, l'algorisme més lent dels tres, perquè fa moltíssims intercanvis. S'ensenya perquè el seu mecanisme es veu d'un cop d'ull, no perquè es faci servir.

Els tres tenen en comú una cosa que es veu al codi: dos bucles imbricats. Recorda el que es va dir a 03-03: amb dos bucles imbricats, doblar les dades quadruplica la feina. Deu elements són unes cent operacions; mil elements, un milió. Aquest és el seu sostre, i a Eficiència i notació Big-O li posarem nom formal.

Si t'haguessis de quedar amb un per implementar-lo a mà, és la inserció: és estable, és simple i és la millor amb dades gairebé ordenades, que és la situació més habitual a la vida real (una agenda a la qual s'afegeix una tasca al final ja està gairebé ordenada).

Els tres algorismes anteriors comparteixen un sostre del qual no es pot baixar amb la seva estratègia. Per superar-lo cal canviar d'idea: en comptes de recórrer la llista un cop i un altre, partir-la en trossos, ordenar cada tros i combinar els resultats. És l'estratègia anomenada divideix i venceràs, i d'ella surten els dos algorismes que es fan servir de debò. L'ordenació per barreja (mergesort) parteix la llista per la meitat, ordena cada meitat i fusiona les dues meitats ordenades en una sola passada; és estable i el seu rendiment no depèn de les dades d'entrada. L'ordenació ràpida (quicksort) tria un element com a pivot, col·loca a l'esquerra els menors i a la dreta els majors, i repeteix a cada costat; és més ràpida a la pràctica, però no és estable i té un cas dolent.

La diferència d'escala és brutal: on la bombolla necessita un milió d'operacions per a mil elements, aquests en necessiten unes deu mil. Tots dos es recolzen en el fet que un algorisme es crida a si mateix sobre els trossos més petits, així que necessiten una eina que encara no tens. La coneixeràs a la lliçó següent, i allà implementarem el mergesort complet amb la seva traça: la idea de dividir es reprèn a Recursivitat.

Tot l'anterior existeix perquè entenguis el mecanisme. En un programa real es fa servir el que porta el llenguatge, i Python porta dues maneres d'ordenar que convé no confondre:

operator.itemgetter("dies") construeix una funció que fa exactament el mateix que lambda t: t["dies"], però està escrita en C i es llegeix millor quan hi ha diversos camps. I aquesta última línia és la tècnica moderna per ordenar per diversos criteris: la clau retorna una tupla, i Python compara tuples element a element —primer el primer, i només si empaten mira el segon—, que és justament el que significa «per prioritat i, dins de la mateixa, per dies».

Aquest diccionari ORDRE_PRIORITAT, que TascaFàcil ja tenia des de la v0.10, resol un problema real: alfabèticament «alta» va abans que «baixa» i que «mitjana», cosa que és pura coincidència i no l'ordre que volem. Traduir cada prioritat a un nombre imposa l'ordre lògic en comptes de l'alfabètic. Si a més volguessis invertir només un dels dos criteris i l'altre no, el truc habitual amb nombres és negar-los: (-t["dies"], t["titol"]) ordena per dies de major a menor i, en els empats, per títol de la A a la Z.

I què hi ha dins de sorted? Un algorisme anomenat Timsort, escrit per Tim Peters per a Python el 2002 i adoptat després per Java i Android. És un híbrid: detecta els trams que ja estan ordenats a les dades reals —que gairebé sempre n'hi ha—, ordena els trams curts amb inserció, la mateixa de la secció 5, i els fusiona amb la tècnica del mergesort. És estable i aprofita l'ordre preexistent, així que sobre una llista gairebé ordenada s'acosta a una sola passada.

Discutir sense mesurar és opinar. time.perf_counter() retorna un nombre de segons d'alta precisió; la diferència entre dues lectures és el temps transcorregut.

La còpia amb list(dades) és imprescindible: com que aquests algorismes ordenen al lloc, sense ella la segona mesura rebria una llista ja ordenada i el resultat seria fals. Resultats aproximats en un portàtil corrent —els teus variaran, però les proporcions es mantindran:

Llegeix la taula en vertical, que és on hi ha la lliçó. En multiplicar per deu les dades, sorted passa de 0,0002 a 0,003 segons —unes quinze vegades més—, mentre que la bombolla passa de 0,09 a 11 segons, més de cent vegades més. Aquesta és la diferència entre un algorisme amb dos bucles imbricats i un que divideix, i per això cap quantitat de trucs de programació salvarà un algorisme mal triat.

La moralitat de sempre, aquesta vegada avalada per números: en producció es fa servir sorted() o .sort(). Estan escrits en C, són estables, aprofiten l'ordre preexistent i cap implementació teva no se'ls acostarà. El d'aquí dalt s'implementa per entendre què fan per dins i per saber triar.

Apliquem el que hem après en dos llocs. El llistat passa a ordenar-se per dos criteris amb una clau de tupla, i afegim l'informe que la Marta demana cada tarda: què fa demà cada membre de l'equip. El menú passa a nou opcions.

Les decisions de disseny que val la pena assenyalar:

• clau_ordre és una funció amb nom, no una lambda. Es fa servir en dos llocs diferents i mereix un docstring que expliqui el criteri; és exactament el límit que vam marcar a 04-05 per ascendir una lambda a def.
• La clau retorna una tupla de tres elements, amb el títol com a tercer criteri de desempat. Així el llistat surt sempre igual davant de les mateixes dades, sense dependre de l'ordre de registre. Un llistat que canvia d'ordre sense motiu desconcerta l'usuari.
• pla_de_dema combina les dues lliçons del mòdul: l'índex invertit de 06-01 per agrupar per persona i l'ordenació per dos criteris per triar la tasca més urgent de cadascun. pendents[0] és la resposta a «per on començo demà?» precisament perquè la llista està ordenada.
• S'ordena en mostrar, no en desar. L'agenda viu en l'ordre en què es va registrar; l'ordre és una decisió de presentació. Ordenar la llista real obligaria a reordenar-la després de cada canvi i perdria l'ordre de registre, que és una dada en si mateixa.

Esperar que .sort() retorni la llista ordenada. llista_ordenada = agenda.sort() deixa llista_ordenada valent None, i l'error apareix més tard i lluny, quan alguna cosa intenta recórrer aquest None. La regla: .sort() modifica, sorted() retorna.

Ordenar alfabèticament allò que té un ordre propi. sorted(agenda, key=lambda t: t["prioritat"]) posa «alta», «baixa» i «mitjana» en aquest ordre, que no és el que vols. Tradueix a nombres amb un diccionari com ORDRE_PRIORITAT.

Modificar la llista mentre s'ordena o es recorre. Afegir o esborrar elements dins del bucle que la recorre produeix resultats impredictibles i elements saltats. Construeix una llista nova i substitueix-la al final.

Confondre l'element amb la seva posició a l'ordenació per selecció. Si deses minim = valors[j] en comptes de minim = j, després no sabràs on era i l'intercanvi serà impossible.

Oblidar la còpia en mesurar temps. Si mesures dos algorismes sobre la mateixa llista, el segon rep dades ja ordenades i sembla miraculosament ràpid. list(dades) abans de cada mesura.

Consell: ordena un cop, no a cada consulta. Si el llistat es demana deu vegades sense que l'agenda canviï, ordena un cop i desa el resultat. I si necessites mantenir una col·lecció sempre ordenada mentre insereixes, bisect.insort de 06-01 col·loca cada element al seu lloc sense reordenar res.

Consell: si només necessites els millors, no ordenis. Per a «les tres tasques més urgents» d'una llista enorme, heapq.nsmallest(3, agenda, key=clau_ordre) és més barat que ordenar-ho tot i quedar-te amb [:3].

Traça en dues taules l'ordenació de la llista [4, 1, 5, 2] amb inserció (una fila per passada, indicant l'element a la mà i la llista resultant) i amb bombolla amb sentinella (una fila per passada, indicant intercanvis i el valor del sentinella). Indica quantes comparacions fa cadascuna i quantes en faria la bombolla si la llista entrés ja ordenada.

Adapta ordenar_seleccio perquè accepti un paràmetre clau —una funció, com el key de sorted— amb valor per defecte que deixi l'element tal qual, i ordeni comparant clau(element). Després, fes-la servir per ordenar l'agenda per dies i per títol, i comprova amb sorted que el resultat coincideix.

Escriu esta_ordenada(valors, clau=None) que retorni True si la llista ja està ordenada de menor a major segons aquest criteri, recorrent-la una sola vegada i sortint així que trobi un parell desordenat. Després, escriu ordenar_si_cal(agenda), que faci servir l'anterior per no ordenar en va, i informi per pantalla del que ha fet.

Solució 1. Inserció sobre [4, 1, 5, 2]:

Cinc comparacions en total. Bombolla amb sentinella sobre la mateixa llista:

Tres més dos més un: sis comparacions. Si la llista entrés ja ordenada, la primera passada faria tres comparacions, cap intercanvi, i el sentinella tallaria aquí: tres comparacions en total.

Solució 2.

El canvi és mínim —tres aparicions de clau(...) a la comparació— i converteix un algorisme que només ordenava nombres en un que ordena qualsevol cosa: és el patró callback de 04-05 un altre cop. Atenció a l'última línia: la comparació amb sorted dona True si no hi ha empats en els dies; si n'hi ha pot donar False, i no perquè el resultat estigui malament, sinó perquè la nostra selecció no és estable i sorted sí. És la millor manera de veure l'estabilitat amb els teus propis ulls.

Solució 3.

esta_ordenada és una cerca lineal de 06-01 disfressada: busca el primer parell desordenat i surt així que el troba. Comprovar costa un sol recorregut, moltíssim menys que ordenar, de manera que la comprovació prèvia surt rendible sempre que hi hagi una probabilitat raonable que ja estigui ordenada. I fixa't que ordenar_si_cal retorna l'agenda en tots dos camins, ordenada o no: una funció que de vegades retorna alguna cosa i de vegades no és una font inesgotable d'errors, com es va dir a 04-02.

Ordenar és reorganitzar segons un criteri d'ordre, aquesta funció key que diu què es compara de cada element, i amb una propietat que decideix què passa amb els empats: l'estabilitat, que conserva l'ordre previ dels iguals i permet ordenar per diversos criteris encadenant ordenacions. Has implementat i traçat els tres algorismes clàssics: la selecció, que busca el mínim i el col·loca, fa pocs intercanvis però sempre la mateixa feina i no és estable; la inserció, que col·loca cada element al seu lloc dins de la part ja ordenada, és estable i excel·lent amb dades gairebé ordenades; i la bombolla, que intercanvia veïns i amb el sentinella sap aturar-se quan ja no queda res per fer, però continua sent la més lenta. Els tres comparteixen dos bucles imbricats i, amb ells, un sostre: mil elements són un milió d'operacions.

Aquest sostre només es trenca canviant d'estratègia, dividint la llista en trossos com fan mergesort i quicksort. Mentrestant, en producció es fa servir sorted() —que retorna una llista nova— o .sort() —que modifica al lloc i retorna None—, amb reverse, amb key (una lambda o un operator.itemgetter) i, per a diversos criteris alhora, amb una tupla com a clau. Per dins porten Timsort, un híbrid estable d'inserció i barreja que aprofita els trams ja ordenats; i les mesures amb time.perf_counter() han posat números a la diferència: 3.600 vegades més ràpid que la nostra bombolla amb 10.000 elements. TascaFàcil arriba a la v0.13 amb el llistat ordenat per prioritat i dies i amb el pla de demà que la Marta reparteix cada tarda.

Queda una peça pendent, i apareix als dos llocs on ens hem aturat. La cerca binària de 06-01 tenia una versió més elegant que no podíem escriure, i el mergesort d'aquesta lliçó necessita ordenar dues meitats que són, al seu torn, llistes per ordenar. Tots dos demanen el mateix: una funció que es cridi a si mateixa. A Recursivitat veuràs com una funció pot resoldre un problema resolent versions més petites d'ell mateix, quines són les dues peces que mai no poden faltar i per què la recursivitat, mal utilitzada, repeteix feina fins a tornar-se inservible.