En la lección anterior descubrimos que la búsqueda binaria resuelve en veinte comparaciones lo que a la lineal le cuesta un millón, pero exige un requisito que TareaFácil todavía no cumple: que los datos estén ordenados. También quedó dicho que ordenar cuesta. Es hora de averiguar cuánto y cómo, abriendo la segunda caja negra del curso: qué hace sorted por dentro.

Ordenar es, probablemente, la operación más rentable que aprenderás. No solo porque un listado ordenado se lee mejor: una colección ordenada habilita la búsqueda binaria, permite detectar duplicados de un vistazo, hace triviales los informes por rangos y convierte «los cinco encargos más urgentes» en una rebanada. En esta lección implementarás tres algoritmos clásicos con su trazado paso a paso, entenderás qué significa que una ordenación sea estable y terminarás usando la herramienta de verdad —sorted y .sort()— sabiendo por fin qué ocurre dentro.

1. Qué significa ordenar y por qué compensa
2. El criterio de orden
3. Estabilidad: por qué importa en Estudio Alba
4. Ordenación por selección
5. Ordenación por inserción
6. Ordenación por burbuja y el centinela
7. Los tres algoritmos, comparados
8. Algoritmos por división: mergesort y quicksort
9. Ordenar en Python de verdad
10. Medir la diferencia con time.perf_counter()
11. TareaFácil v0.13: prioridad, días y el plan de mañana
12. Errores comunes y consejos
13. Ejercicios
14. Conclusión

Ordenar es reorganizar los elementos de una colección de manera que cada uno sea «menor o igual» que el siguiente según un criterio. La definición esconde dos decisiones que hay que tomar antes de escribir una sola línea: qué se compara y qué se hace con los empates. La primera es el criterio de orden, la segunda es la estabilidad, y las dos siguientes secciones se ocupan de ellas.

Lo que hace de la ordenación una inversión y no un gasto es todo lo que habilita después:

Por eso ordenar una vez y consultar muchas casi siempre gana a consultar sin ordenar. Es el mismo razonamiento del índice invertido de 06-01: pagar un coste inicial para que todo lo que venga después salga barato.

Los números y los textos tienen un orden natural (3 < 7, "Luis" < "Marta" por el orden de los caracteres que viste en 05-02), pero un diccionario no: nadie sabe si «la tarea del cartel» es mayor o menor que «la del menú». El criterio de orden es la regla que convierte cada elemento en algo comparable.

Ese key es el callback de 04-05: una función que recibe un elemento y devuelve el valor por el que se compara. Todos los algoritmos de esta lección se escriben primero comparando números, porque así se ve el mecanismo, y después se generalizan con key. La idea clave es que el algoritmo de ordenación y el criterio son cosas separadas: el mismo algoritmo ordena por días, por título o por prioridad cambiando solo la función de comparación.

Una ordenación es estable cuando los elementos que empatan conservan el orden que tenían antes. Suena a sutileza académica hasta que se ve un caso real.

Marta ordena la agenda por días estimados, de menos a más, para ver primero lo que se despacha rápido:

Después la reordena por prioridad. Con una ordenación estable, dentro de «alta» se mantiene el orden anterior: primero Logotipo Vidal (2 días) y después Cartel feria (3). El resultado es lo que Marta quería: ordenado por prioridad y, a igualdad de prioridad, por días. Con una ordenación inestable, esas dos tareas podrían salir en cualquier orden y el trabajo de la primera ordenación se perdería.

De ahí la técnica clásica: para ordenar por varios criterios, se ordena por el menos importante primero y por el más importante al final, y la estabilidad conserva lo anterior. En la sección 9 verás la alternativa moderna, que es más clara todavía. Y retén el dato: sorted() y .sort() de Python son estables, siempre, y eso está garantizado por el lenguaje.

La idea es la que usarías con una mano de cartas: buscar la más pequeña de todas, ponerla la primera; buscar la más pequeña de las que quedan, ponerla la segunda, y así sucesivamente.

Tres cosas que entender aquí. El bucle exterior recorre las posiciones que se van fijando; llega hasta n - 1 porque cuando queda un solo elemento ya está colocado por fuerza. El bucle interior es la búsqueda del mínimo del patrón de 03-02, pero guardando la posición y no el valor, porque hay que intercambiar. Y el intercambio a, b = b, a es el desempaquetado de tuplas de 05-04 haciendo su trabajo sin variable auxiliar.

Trazado sobre los días estimados [3, 5, 2, 4, 1]:

Fíjate en la pasada 4: la lista ya estaba ordenada y aun así el algoritmo hizo la pasada completa. La selección no se entera nunca de que ha terminado: siempre hace exactamente el mismo número de comparaciones, esté la lista ordenada o del revés. A cambio, hace muy pocos intercambios: uno por pasada como máximo, lo que la hace interesante cuando mover un elemento es caro.

Y una advertencia importante para la sección 7: la selección clásica no es estable, precisamente por ese intercambio a distancia, que puede saltar un elemento igual por encima de otro.

Es la que usa todo el mundo al ordenar cartas en la mano: se coge la siguiente y se coloca en su sitio entre las que ya están ordenadas, desplazando las mayores hacia la derecha.

La parte delicada es el while, y conviene leerlo con calma. Retrocede desde la posición anterior mientras se cumplan dos condiciones: que no nos hayamos salido por la izquierda (j >= 0) y que el elemento examinado sea mayor que el que llevamos en la mano. El orden de esas dos condiciones no es casual: gracias a la evaluación perezosa del and que viste en 02-02, si j llega a -1 la segunda comparación ni se evalúa, y así no se accede a valores[-1], que en Python sería el último elemento y produciría un error silencioso.

Trazado sobre [3, 5, 2, 4, 1]; la parte ya ordenada va en negrita:

Aquí está la gran virtud de la inserción, y es la razón de que siga viva en el software profesional: con datos casi ordenados es rapidísima. Si cada elemento ya está cerca de su sitio, el while da una o ninguna vuelta y la ordenación entera cuesta poco más que un recorrido. Sobre una lista ya ordenada, la inserción hace una sola comparación por elemento y ningún desplazamiento: es el mejor caso posible. Y es estable, porque el while para en cuanto encuentra un elemento igual y nunca lo salta.

La burbuja compara vecinos e intercambia los que están al revés, pasada tras pasada, hasta que no queda ninguno desordenado. En cada pasada el mayor de los que quedan «flota» hasta el final, de ahí el nombre.

Dos mejoras conviven en este código. El range(n - 1 - pasada) acorta cada pasada, porque tras la primera el último elemento ya es el mayor y no hace falta volver a mirarlo. Y hubo_cambio es el centinela: el patrón bandera de 03-02 aplicado aquí. Si una pasada completa no intercambia nada, la lista está ordenada y el break sale del bucle. Sin centinela, la burbuja haría siempre todas las pasadas aunque la lista llegara ya ordenada.

Trazado sobre [3, 5, 2, 4, 1], mostrando el estado al final de cada pasada:

Con cinco elementos, range(n - 1) da cuatro pasadas y aquí se agotan todas. Pero si la lista de entrada fuera [1, 2, 3, 4, 5], la primera pasada no intercambiaría nada, hubo_cambio seguiría en False y el break terminaría el trabajo con cuatro comparaciones en total. Ese es todo el valor del centinela.

La burbuja es estable —solo intercambia vecinos estrictamente desordenados, nunca iguales— y es, en la práctica, el algoritmo más lento de los tres, porque hace muchísimos intercambios. Se enseña porque su mecanismo se ve de un vistazo, no porque se use.

Los tres tienen en común una cosa que se ve en el código: dos bucles anidados. Recuerda lo que se dijo en 03-03: con dos bucles anidados, doblar los datos cuadruplica el trabajo. Diez elementos son unas cien operaciones; mil elementos, un millón. Ese es su techo, y en Eficiencia y notación Big-O le pondremos nombre formal.

Si tuvieras que quedarte con uno para implementarlo a mano, es la inserción: es estable, es simple y es la mejor con datos casi ordenados, que es la situación más habitual en la vida real (una agenda a la que se le añade una tarea al final ya está casi ordenada).

Los tres algoritmos anteriores comparten un techo del que no se puede bajar con su estrategia. Para superarlo hay que cambiar de idea: en vez de recorrer la lista una y otra vez, partirla en trozos, ordenar cada trozo y combinar los resultados. Es la estrategia llamada divide y vencerás, y de ella salen los dos algoritmos que se usan de verdad. La ordenación por mezcla (mergesort) parte la lista por la mitad, ordena cada mitad y fusiona las dos mitades ordenadas en una sola pasada; es estable y su rendimiento no depende de los datos de entrada. La ordenación rápida (quicksort) elige un elemento como pivote, coloca a la izquierda los menores y a la derecha los mayores, y repite en cada lado; es más rápida en la práctica, pero no es estable y tiene un caso malo.

La diferencia de escala es brutal: donde la burbuja necesita un millón de operaciones para mil elementos, estos necesitan unas diez mil. Ambos se apoyan en que un algoritmo se llama a sí mismo sobre los trozos más pequeños, así que necesitan una herramienta que todavía no tienes. La conocerás en la lección siguiente, y allí implementaremos el mergesort completo con su traza: la idea de dividir se retoma en Recursión.

Todo lo anterior existe para que entiendas el mecanismo. En un programa real se usa lo que trae el lenguaje, y Python trae dos formas de ordenar que conviene no confundir:

operator.itemgetter("dias") construye una función que hace exactamente lo mismo que lambda t: t["dias"], pero está escrita en C y se lee mejor cuando hay varios campos. Y esa última línea es la técnica moderna para ordenar por varios criterios: la clave devuelve una tupla, y Python compara tuplas elemento a elemento —primero el primero, y solo si empatan mira el segundo—, que es justo lo que significa «por prioridad y, dentro de la misma, por días».

Ese diccionario ORDEN_PRIORIDAD, que TareaFácil ya tenía desde la v0.10, resuelve un problema real: alfabéticamente «alta» va antes que «baja» y que «media», lo cual es pura coincidencia y no el orden que queremos. Traducir cada prioridad a un número impone el orden lógico en vez del alfabético. Si además quisieras invertir solo uno de los dos criterios y el otro no, el truco habitual con números es negarlos: (-t["dias"], t["titulo"]) ordena por días de mayor a menor y, en los empates, por título de la A a la Z.

¿Y qué hay dentro de sorted? Un algoritmo llamado Timsort, escrito por Tim Peters para Python en 2002 y adoptado después por Java y Android. Es un híbrido: detecta los tramos que ya están ordenados en los datos reales —que casi siempre los hay—, ordena los tramos cortos con inserción, la misma de la sección 5, y los fusiona con la técnica del mergesort. Es estable y aprovecha el orden preexistente, así que sobre una lista casi ordenada se acerca a una sola pasada.

Discutir sin medir es opinar. time.perf_counter() devuelve un número de segundos de alta precisión; la diferencia entre dos lecturas es el tiempo transcurrido.

La copia con list(datos) es imprescindible: como estos algoritmos ordenan en el sitio, sin ella la segunda medición recibiría una lista ya ordenada y el resultado sería falso. Resultados aproximados en un portátil corriente —los tuyos variarán, pero las proporciones se mantendrán:

Lee la tabla en vertical, que es donde está la lección. Al multiplicar por diez los datos, sorted pasa de 0,0002 a 0,003 segundos —unas quince veces más—, mientras que la burbuja pasa de 0,09 a 11 segundos, más de cien veces más. Esa es la diferencia entre un algoritmo con dos bucles anidados y uno que divide, y por eso ninguna cantidad de trucos de programación salvará a un algoritmo mal elegido.

La moraleja de siempre, esta vez respaldada por números: en producción se usa sorted() o .sort(). Están escritos en C, son estables, aprovechan el orden preexistente y ninguna implementación tuya se les acercará. Lo de arriba se implementa para entender qué hacen por dentro y para saber elegir.

Aplicamos lo aprendido en dos sitios. El listado pasa a ordenarse por dos criterios con una clave de tupla, y añadimos el informe que Marta pide cada tarde: qué hace mañana cada miembro del equipo. El menú pasa a nueve opciones.

Las decisiones de diseño que merece la pena señalar:

• clave_orden es una función con nombre, no una lambda. Se usa en dos sitios distintos y merece un docstring que explique el criterio; es exactamente el límite que marcamos en 04-05 para ascender una lambda a def.
• La clave devuelve una tupla de tres elementos, con el título como tercer criterio de desempate. Así el listado sale siempre igual ante los mismos datos, sin depender del orden de registro. Un listado que cambia de orden sin motivo desconcierta al usuario.
• plan_de_manana combina las dos lecciones del módulo: el índice invertido de 06-01 para agrupar por persona y la ordenación por dos criterios para elegir la tarea más urgente de cada uno. pendientes[0] es la respuesta a «¿por dónde empiezo mañana?» precisamente porque la lista está ordenada.
• Se ordena al mostrar, no al guardar. La agenda vive en el orden en que se registró; el orden es una decisión de presentación. Ordenar la lista real obligaría a reordenarla tras cada cambio y perdería el orden de registro, que es un dato en sí mismo.

Esperar que .sort() devuelva la lista ordenada. lista_ordenada = agenda.sort() deja lista_ordenada valiendo None, y el error aparece más tarde y lejos, cuando algo intenta recorrer ese None. La regla: .sort() modifica, sorted() devuelve.

Ordenar alfabéticamente lo que tiene un orden propio. sorted(agenda, key=lambda t: t["prioridad"]) pone «alta», «baja» y «media» en ese orden, que no es el que quieres. Traduce a números con un diccionario como ORDEN_PRIORIDAD.

Modificar la lista mientras se ordena o se recorre. Añadir o borrar elementos dentro del bucle que la recorre produce resultados impredecibles y elementos saltados. Construye una lista nueva y sustitúyela al final.

Confundir el elemento con su posición en la ordenación por selección. Si guardas minimo = valores[j] en vez de minimo = j, después no sabrás dónde estaba y el intercambio será imposible.

Olvidar la copia al medir tiempos. Si mides dos algoritmos sobre la misma lista, el segundo recibe datos ya ordenados y parece milagrosamente rápido. list(datos) antes de cada medición.

Consejo: ordena una vez, no en cada consulta. Si el listado se pide diez veces sin que la agenda cambie, ordena una vez y guarda el resultado. Y si necesitas mantener una colección siempre ordenada mientras insertas, bisect.insort de 06-01 coloca cada elemento en su sitio sin reordenar nada.

Consejo: si necesitas solo los mejores, no ordenes. Para «las tres tareas más urgentes» de una lista enorme, heapq.nsmallest(3, agenda, key=clave_orden) es más barato que ordenarlo todo y quedarte con [:3].

Traza en dos tablas la ordenación de la lista [4, 1, 5, 2] con inserción (una fila por pasada, indicando el elemento en la mano y la lista resultante) y con burbuja con centinela (una fila por pasada, indicando intercambios y el valor del centinela). Indica cuántas comparaciones hace cada uno y cuántas haría la burbuja si la lista entrara ya ordenada.

Adapta ordenar_seleccion para que acepte un parámetro clave —una función, como el key de sorted— con valor por defecto que deje el elemento tal cual, y ordene comparando clave(elemento). Después, úsala para ordenar la agenda por días y por título, y comprueba con sorted que el resultado coincide.

Escribe esta_ordenada(valores, clave=None) que devuelva True si la lista ya está ordenada de menor a mayor según ese criterio, recorriéndola una sola vez y saliendo en cuanto encuentre un par desordenado. Después, escribe ordenar_si_hace_falta(agenda), que use la anterior para no ordenar en vano, e informe por pantalla de lo que ha hecho.

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

Cinco comparaciones en total. Burbuja con centinela sobre la misma lista:

Tres más dos más uno: seis comparaciones. Si la lista entrara ya ordenada, la primera pasada haría tres comparaciones, ningún intercambio, y el centinela cortaría ahí: tres comparaciones en total.

Solución 2.

El cambio es mínimo —tres apariciones de clave(...) en la comparación— y convierte un algoritmo que solo ordenaba números en uno que ordena cualquier cosa: es el patrón callback de 04-05 otra vez. Ojo a la última línea: la comparación con sorted da True si no hay empates en los días; si los hay puede dar False, y no porque el resultado esté mal, sino porque nuestra selección no es estable y sorted sí. Es la mejor manera de ver la estabilidad con tus propios ojos.

Solución 3.

esta_ordenada es una búsqueda lineal de 06-01 disfrazada: busca el primer par desordenado y sale en cuanto lo encuentra. Comprobar cuesta un solo recorrido, muchísimo menos que ordenar, así que la comprobación previa sale rentable siempre que haya una probabilidad razonable de que ya esté ordenada. Y fíjate en que ordenar_si_hace_falta devuelve la agenda en los dos caminos, ordenada o no: una función que a veces devuelve algo y a veces no es una fuente inagotable de errores, como se dijo en 04-02.

Ordenar es reorganizar según un criterio de orden, esa función key que dice qué se compara de cada elemento, y con una propiedad que decide qué pasa con los empates: la estabilidad, que conserva el orden previo de los iguales y permite ordenar por varios criterios encadenando ordenaciones. Has implementado y trazado los tres algoritmos clásicos: la selección, que busca el mínimo y lo coloca, hace pocos intercambios pero siempre el mismo trabajo y no es estable; la inserción, que coloca cada elemento en su sitio dentro de la parte ya ordenada, es estable y excelente con datos casi ordenados; y la burbuja, que intercambia vecinos y con el centinela sabe parar cuando ya no queda nada por hacer, pero sigue siendo la más lenta. Los tres comparten dos bucles anidados y, con ellos, un techo: mil elementos son un millón de operaciones.

Ese techo solo se rompe cambiando de estrategia, dividiendo la lista en trozos como hacen mergesort y quicksort. Mientras tanto, en producción se usa sorted() —que devuelve una lista nueva— o .sort() —que modifica en el sitio y devuelve None—, con reverse, con key (una lambda o un operator.itemgetter) y, para varios criterios a la vez, con una tupla como clave. Por dentro llevan Timsort, un híbrido estable de inserción y mezcla que aprovecha los tramos ya ordenados; y las mediciones con time.perf_counter() han puesto números a la diferencia: 3.600 veces más rápido que nuestra burbuja con 10.000 elementos. TareaFácil llega a la v0.13 con el listado ordenado por prioridad y días y con el plan de mañana que Marta reparte cada tarde.

Queda una pieza pendiente, y aparece en los dos sitios donde nos hemos detenido. La búsqueda binaria de 06-01 tenía una versión más elegante que no podíamos escribir, y el mergesort de esta lección necesita ordenar dos mitades que son, a su vez, listas por ordenar. Ambos piden lo mismo: una función que se llame a sí misma. En Recursión verás cómo una función puede resolver un problema resolviendo versiones más pequeñas de sí mismo, cuáles son las dos piezas que jamás pueden faltar y por qué la recursión, mal usada, repite trabajo hasta volverse inservible.