Merge sort (04-03) nos dio la garantía Θ(n log n)... pagando O(n) de memoria. Quick sort ataca la misma pregunta con la misma estrategia madre — divide y vencerás (03-01) — pero invirtiendo dónde vive el esfuerzo: en merge sort dividir es un corte tonto y todo el trabajo está en combinar; en quick sort todo el trabajo está en dividir (la partición alrededor de un pivote) y combinar es literalmente no hacer nada. Esa inversión le regala lo que merge sort no tenía — ordena in-place, sin memoria auxiliar lineal — a cambio del riesgo que venimos anunciando desde 02-03: un caso promedio excelente O(n log n) conviviendo con un peor caso O(n²) que hay que saber domar. En esta lección construiremos la partición de Lomuto paso a paso, la trazaremos sobre las llegadas de RutaBus, saldaremos la promesa del análisis de casos y cerraremos con la tabla comparativa de los tres ordenamientos del curso.

1. La idea invertida: el trabajo se hace al dividir
2. La partición de Lomuto, paso a paso
3. Traza de la partición sobre el panel de RutaBus
4. Implementación recursiva completa
5. Análisis de casos: la promesa de 02-03, cobrada
6. Domar el peor caso: pivote aleatorio y mediana de tres
7. Estabilidad, espacio y la tabla final de los tres ordenamientos

El plan de quick sort para ordenar un tramo de la lista:

1. Dividir (aquí está todo el trabajo): elige un elemento como pivote y reorganiza el tramo para que quede [menores o iguales que el pivote] + [pivote] + [mayores]. Esta reorganización se llama partición y deja al pivote en su posición final definitiva.
2. Conquistar: ordena recursivamente el bloque de la izquierda y el de la derecha.
3. Combinar: nada. Cero. Si la izquierda queda ordenada, el pivote está en su sitio y la derecha queda ordenada, la lista ya está ordenada — los bloques no se tocan entre sí.

Compáralo con merge sort, su hermano especular:

La última fila es la fuente de toda la gloria y toda la miseria de quick sort. Merge sort corta por el centro por construcción; quick sort corta por donde caiga el pivote. Si el pivote resulta ser mediano, mitades perfectas; si resulta ser el mínimo o el máximo, una "mitad" vacía y otra con casi todo — y ahí empieza el drama del apartado 5.

Hay varios esquemas de partición; el de Lomuto es el más fácil de razonar. Trabaja sobre el tramo lista[izq..der], toma como pivote el último elemento y mantiene una frontera i que separa lo ya clasificado como "≤ pivote" de lo demás:

El invariante del bucle (nuestra herramienta de 04-01) es una foto en tres zonas: en todo momento, lista[izq..i] contiene elementos ≤ pivote, lista[i+1..j−1] contiene elementos > pivote, y de j en adelante está lo pendiente. Cada vuelta examina lista[j]:

• Si es > pivote: no hay que hacer nada — ya está pegado a la zona de mayores.
• Si es ≤ pivote: se intercambia con el primer elemento de la zona de mayores (lista[i+1]), con lo que ambas zonas crecen una posición manteniendo el invariante.

Al acabar el bucle, el intercambio final planta el pivote entre las dos zonas: todo lo de su izquierda es ≤ y todo lo de su derecha es >. El pivote ya no se moverá nunca más.

Particionemos el panel completo de llegadas de la L1 (tramo 0..4, pivote = "18:31", el último):

La función devuelve 2: el pivote "18:31" ha quedado en el índice 2, su posición final en la lista ordenada — puedes comprobarlo: es la mediana de las cinco horas. A su izquierda, {18:07, 18:12} (desordenados entre sí, da igual: ya son "los correctos"); a su derecha, {18:42, 18:59}. Cada mitad se resolverá con una llamada recursiva, y en este ejemplo ambas son tramos de 2 que una partición más deja listos.

Coste de una partición: el bucle recorre el tramo una vez — O(n) en el tamaño del tramo, con intercambios dentro de la propia lista.

Detalles:

• Trabaja sobre la propia lista con índices izq/der, sin crear sublistas — a diferencia de los cortes con copia de merge_sort. Por eso es in-place.
• Las llamadas recursivas excluyen p: el pivote ya está colocado para siempre. Incluirlo (quick_sort(lista, izq, p)) provoca recursión infinita en cuanto un tramo no encoge.
• El caso base izq >= der cubre tramos de 1 elemento y también los vacíos (izq > der), que aparecen cuando el pivote cae en un extremo.

En 02-03 anunciamos quick sort como "el ejemplo célebre" de la brecha promedio/peor caso. Cobremos la promesa. El coste total es la suma de todas las particiones, y cuánto suman depende de dónde caen los pivotes:

Mejor caso — Θ(n log n): pivotes medianos. Si cada pivote parte su tramo en dos mitades ≈ iguales, el árbol de llamadas es el de merge sort: log₂ n niveles, y las particiones de cada nivel suman O(n) en conjunto (recorren tramos disjuntos que cubren la lista). Total: la recurrencia T(n) = 2·T(n/2) + O(n) que resolvimos en 04-03 → Θ(n log n).

Peor caso — Θ(n²): pivotes extremos. Si cada pivote resulta ser el máximo (o el mínimo) de su tramo, la partición deja un bloque de n−1 y otro vacío. La recurrencia degenera en T(n) = T(n−1) + O(n): particiones de n, n−1, n−2, ... — la suma aritmética n(n−1)/2 de 02-01 → Θ(n²). Y aquí la ironía cruel: con el pivote de Lomuto (el último elemento), esta catástrofe la provoca... una lista ya ordenada (o invertida). Cada pivote es el máximo de su tramo, y el algoritmo "rápido" se arrastra a n²: exactamente la entrada donde la humilde inserción (04-02) corría en Θ(n). Además la recursión se apila n niveles: con nuestro panel de 10.000 llegadas ya ordenadas, Python revienta el límite de pila (RecursionError, recuerda 02-02) antes siquiera de terminar de ir lento.

Caso promedio — Θ(n log n): la realidad estadística. Con entradas en orden aleatorio (distribución que hay que declarar, 02-03), el pivote rara vez es extremo. No hace falta que sea la mediana: basta que caiga "por el centro" razonablemente a menudo. Incluso un pivote que solo garantice un reparto 10 %–90 % mantiene la profundidad logarítmica (log con otra base — constante que la notación absorbe, 01-03). El análisis formal da ≈ 1,39·n·log₂ n comparaciones esperadas: Θ(n log n) con una constante pequeña. Esa constante pequeña, más el trabajo in-place sin copias (localidad y sin coste de memoria), es lo que hace a quick sort ganar a merge sort en la práctica casi siempre... salvo el día que no.

Esto es 02-03 aplicado: si tus entradas son aleatorias y el volumen manda, el promedio te representa; si un usuario (o un atacante — tabla de "entradas hostiles" de 02-03) puede enviarte la entrada patológica, el peor caso es tu contrato. Un endpoint de RutaBus que ordene con este quick sort lo que envíe el cliente es un ataque de denegación de servicio esperando a ocurrir: basta enviar listas ya ordenadas.

El peor caso no se puede eliminar, pero sí volverlo improbable o impracticable:

Pivote aleatorio. Antes de particionar, intercambia el último elemento con uno elegido al azar:

Esto convierte quick sort en un algoritmo aleatorizado (01-02): el coste ya no depende de la entrada sino de los dados internos. Ninguna entrada es patológica por sí misma — ni la ordenada, ni la del atacante, que ya no puede predecir los pivotes —; el peor caso sigue existiendo (podrían salir n pivotes extremos seguidos) pero su probabilidad se desploma exponencialmente. El coste esperado es Θ(n log n) para toda entrada.

Mediana de tres. Alternativa determinista y barata: usar como pivote la mediana entre el primero, el central y el último elemento del tramo. Neutraliza en seco los casos "ya ordenada / invertida" (la mediana de tres de una lista ordenada es el elemento central: partición perfecta) y mejora las constantes en la práctica, aunque un adversario que conozca la regla aún puede construir entradas malas — por eso las bibliotecas serias combinan trucos o cambian de algoritmo si detectan que la recursión se hunde demasiado (los llamados introsort).

No es estable. Los intercambios de la partición saltan por encima de tramos enteros y pueden invertir empates. Con el panel de tuplas de 04-02, [("18:30", "L2"), ("18:05", "L1"), ("18:30", "L1")] y pivote ("18:30", "L1"): la partición coloca el pivote delante del ("18:30", "L2") que originalmente lo precedía — empate invertido. Si necesitas ordenar por hora conservando el orden por línea, quick sort no es tu herramienta (merge sort o Timsort sí).

Espacio: in-place, con matiz. La partición no usa memoria auxiliar — a diferencia del O(n) de merge sort (02-02), aquí no hay listas nuevas. El único gasto es la pila de recursión: O(log n) marcos cuando las particiones son equilibradas, pero O(n) en el peor caso — otra razón para domar los pivotes.

La tabla que resume tres lecciones de ordenación:

Ninguna columna domina a las demás: es un menú de trade-offs, no un podio. Las bibliotecas reales lo confirman componiendo: Timsort (Python) = merge + inserción; los introsort de C++ = quick + heap + inserción.

• Incluir el pivote en las llamadas recursivas (quick_sort(lista, izq, p)): si un tramo no encoge, recursión infinita. El pivote está colocado: se excluye siempre (p − 1 y p + 1).
• Olvidar que la lista ya ordenada es el peor caso de Lomuto. Es antiintuitivo (¡la entrada "fácil"!) y muy frecuente en producción, porque los datos reales llegan a menudo casi ordenados. Si usas pivote fijo, tu benchmark con datos aleatorios mentirá sobre tu producción. Pivote aleatorio o mediana de tres, siempre.
• Muchos duplicados degradan a Lomuto: si el panel tiene miles de llegadas con la misma hora, todos los "≤ pivote" caen al mismo lado y las particiones salen desequilibradas aunque el pivote sea razonable. La solución clásica es la partición en tres zonas (<, =, >), que agrupa los iguales al pivote y no los vuelve a tocar.
• Asumir estabilidad: quick sort ordena bien, así que el error no da síntomas hasta que un empate importa (y entonces es un bug "aleatorio" difícil de reproducir). Ante claves con empates relevantes, merge/Timsort.
• Consejo: en Python real, sorted()/list.sort() (Timsort) ganan a cualquier quick sort casero — implementarlo aquí es para entender el mecanismo y sus trade-offs, que reaparecen tal cual en las bibliotecas de C, C++, Java o Rust que sí lo usan.

Traza la partición de Lomuto (tabla como la del apartado 3) sobre ["18:20", "18:55", "18:04", "18:47", "18:33"] (pivote "18:33"). Indica la posición devuelta y qué dos subtramos se ordenarán recursivamente.

Sin ejecutar código: ¿cuántas comparaciones hace este quick sort (Lomuto, pivote último) sobre el panel ya ordenado ["18:01", "18:02", "18:03", "18:04", "18:05"]? Enumera el pivote de cada llamada y generaliza la cuenta a n. ¿Qué algoritmo de este módulo habría hecho solo n−1 comparaciones con esta entrada?

La app de RutaBus necesita las 10 llegadas más tempranas de un listado de n = 100.000, y a alguien le duele ordenarlo entero. Basándote en la partición: escribe k_mas_tempranas(lista, k) que use la idea de quick sort pero recursando solo por el lado donde está la respuesta (este algoritmo se llama quickselect). Razona por qué su coste promedio es O(n) y no O(n log n). Pista: es el argumento de "contar mitades" de 04-01, pero sumando en vez de contando.

Solución 1

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

Devuelve 2. Subtramos recursivos: [18:20, 18:04] (índices 0–1) y [18:47, 18:55] (índices 3–4). Nótese el intercambio "consigo mismo" de j = 0: inofensivo y normal en Lomuto.

Solución 2

Con la lista ordenada, cada pivote (el último) es el máximo de su tramo: la partición compara todo el tramo, deja el pivote donde estaba y recursa sobre un tramo con un elemento menos. Pivotes sucesivos: 18:05, 18:04, 18:03, 18:02. Comparaciones: 4 + 3 + 2 + 1 = 10. En general: (n−1) + (n−2) + ... + 1 = n(n−1)/2 — la suma aritmética, Θ(n²). La inserción (04-02) habría hecho n−1 = 4 comparaciones: su mejor caso es exactamente el peor de este quick sort.

Solución 3

Tras quickselect, las k−1 posiciones anteriores contienen (sin orden) los elementos menores: lista[:k] son exactamente las k más tempranas. Coste promedio: cada partición cuesta el tamaño del tramo, pero al recursar solo por un lado los tramos esperados se reducen a la mitad: n + n/2 + n/4 + ... ≤ 2n → O(n). Comparado con "contar mitades" de 04-01: allí los niveles se contaban (log n); aquí sus costes se suman (serie geométrica → 2n). Ordenar entero costaría n log n ≈ 1,7 millones de operaciones; quickselect, ≈ 200.000.

Quick sort es el espejo de merge sort: mismo padre (divide y vencerás), esfuerzo opuesto — la partición de Lomuto coloca el pivote en su posición definitiva en O(n) y deja dos subproblemas independientes, sin nada que combinar. Hemos cobrado la promesa de 02-03: promedio Θ(n log n) con constante pequeña que lo hace el más rápido en la práctica, peor caso Θ(n²) que — ironía — dispara la entrada ya ordenada con pivote ingenuo, y las dos vacunas: pivote aleatorio (un algoritmo aleatorizado de los de 01-02, coste esperado n log n para toda entrada) y mediana de tres. No es estable, pero sí in-place — la ventaja espacial que merge sort no tenía —, y la tabla final de inserción/merge/quick muestra que elegir ordenamiento es elegir trade-offs, no campeones. Con las listas dominadas, cambiamos de estructura: la red de paradas de RutaBus que modelamos como grafo en 03-04 nos espera con la pregunta más útil de toda la app — ¿cuál es el camino más corto entre dos paradas? — y con el algoritmo que en 03-02 anunciamos como "el greedy que sí es óptimo": Dijkstra.