Quicksort

De qué trata este capítulo

Quicksort es el gran rival del merge sort: también es divide y vencerás, también es O(n log n) en promedio, pero parte el problema al revés. En lugar de dividir a ciegas por la mitad y mezclar los resultados ordenados, escoge un pivote y particiona — reacomoda todo para que lo menor quede a la izquierda del pivote y lo mayor a la derecha — y luego se llama recursivamente en cada lado. El pivote cae en su posición final y no hace falta ningún merge, así que todo el trabajo ocurre in place, de bajada. Eso hace que quicksort normalmente sea el sort por comparación más rápido en la práctica. También lo hace peligroso: un mal pivote convierte O(n log n) en O(n²), y este capítulo te muestra exactamente eso pasando.

Un poco de historia

Quicksort tiene una de las mejores historias de origen en la computación. Tony Hoare lo inventó en 1959, cuando era un estudiante de intercambio de 25 años en Moscú trabajando en un proyecto de traducción automática. Necesitaba ordenar las palabras de una oración para buscarlas en un diccionario, se dio cuenta de que particionar alrededor de un pivote lo lograría, y al principio no pudo demostrarles a sus colegas que la idea recursiva iba a funcionar. Lo publicó en 1961 y desde entonces ha sido el sort por default para arrays: es el qsort de C, la base de los sorts inestables de C++ y Rust, y la razón por la que "quicksort" es el sort que la mayoría de los programadores nombra primero. Hoare después ganó el premio Turing, y quicksort es el logro que más se asocia a su nombre. Su lección duradera también es una advertencia: el algoritmo es elegante y rápido, y tiene un peor caso que ha mordido sistemas reales, y por eso la estrategia del pivote es un capítulo en sí misma.

La intuición

La operación clave es la partición. Escoge un elemento como pivote. Ahora recorre el resto y acomódalos de manera que todo lo menor que el pivote termine a su izquierda y todo lo mayor a su derecha. Cuando terminas, el pivote está en su posición final ordenada — nada volverá a moverlo — y te quedan dos regiones más chicas sin ordenar, una de cada lado. Ordena esas dos regiones de la misma forma y el array completo queda ordenado. No hay paso de merge, porque la partición ya puso todo del lado correcto del pivote.

Ahí está la elegancia: el array se ordena in place, con los pivotes cayendo en su lugar definitivo uno por uno. Pero fíjate en qué se apoya todo esto: en que el pivote parta el array en dos pedazos balanceados. Si el pivote es la mediana, cada lado mide la mitad y obtienes log n niveles, igual que merge sort. Si el pivote siempre es el elemento más chico o el más grande, un lado queda vacío y el otro tiene todo menos el pivote, así que obtienes n niveles de trabajo O(n) — o sea, cuadrático. El pivote lo es todo.

Complejidad: cómo escala

En promedio — sobre pivotes aleatorios o input aleatorio — las particiones de quicksort quedan lo bastante balanceadas como para correr en $O(n \log n)$, con una constante chica que muchas veces le gana a merge sort porque es in place y amigable con el cache. Su espacio es apenas el stack de recursión, $O(\log n)$, ya que ordena dentro del mismo array. Pero el peor caso es $O(n^2)$: si cada pivote es el elemento más chico o más grande que queda, cada partición solo quita el pivote, así que haces n particiones de trabajo O(n). Con el pivote de último elemento que usa esta implementación, el peor caso es input ya ordenado — el input más común que existe en el mundo real. La gráfica de abajo ordena datos aleatorios, donde quicksort va a la par del sort de la librería:

Pero dale al mismo algoritmo input ordenado y se cae por un barranco. Con 4000 elementos, nuestro quicksort tardó como 2 ms con datos aleatorios y 311 ms con datos ya ordenados — 141 veces más lento para el mismo tamaño, puramente porque el pivote fue el peor posible cada vez:

En qué es bueno y en qué no

Quicksort es el sort por comparación de propósito general más rápido en la práctica, y la razón son las constantes, no la asintótica. Ordena in place, así que no paga el impuesto de memoria O(n) del merge sort; particiona con swaps sencillos que le encantan al cache del CPU; y su ciclo interno es apretado. Cuando estás ordenando un array de números y no necesitas estabilidad ni garantías de peor caso, quicksort (con buen pivote) es al que hay que ganarle.

Sus debilidades son la otra cara de la moneda. El peor caso O(n²) es real y, con un pivote ingenuo, lo dispara input ordenado o ordenado al revés — un riesgo genuino de denegación de servicio si un atacante controla los datos. No es estable, así que elementos iguales pueden quedar reordenados. Y necesita acceso aleatorio, así que no sirve para listas ligadas (donde merge sort brilla). El peor caso es manejable — aleatoriza el pivote o cae de vuelta a heapsort — pero es algo real contra lo que tienes que defenderte activamente, a diferencia de la garantía de merge sort.

Los datos, o los inputs

El duelo ordena enteros aleatorios contra el sort de la librería. Una segunda gráfica le da al mismo quicksort input aleatorio contra input ya ordenado, para exponer directamente el peor caso O(n²). Y la animación particiona diez elementos, registrando cada comparación y cada swap para que veas al pivote barrer el array y caer en su lugar.

Constrúyelo, una función a la vez

La recursión particiona y luego ordena cada lado — recursando en el lado más chico y haciendo loop sobre el más grande para mantener el stack bajito incluso cuando un pivote sale malo:

def quicksort(a, probe=None):
    """O(n log n) average, O(n^2) worst: partition around a pivot, recurse on each
    side. In place — the rearranging happens in the array itself, no merge."""
    a = list(a)
    _qsort(a, 0, len(a) - 1, probe)
    return a


def _qsort(a, lo, hi, probe):
    # Recurse into the SMALLER partition and loop on the larger. This bounds the
    # recursion depth to O(log n) even when the partitions are unbalanced, so a
    # bad pivot costs time but never a stack overflow.
    while lo < hi:
        p = _partition(a, lo, hi, probe)
        if p - lo < hi - p:
            _qsort(a, lo, p - 1, probe)
            lo = p + 1
        else:
            _qsort(a, p + 1, hi, probe)
            hi = p - 1

La partición es el corazón de todo. Toma el último elemento como pivote, recorre con una frontera i que marca el final de la región "menor que el pivote", sube cada elemento más chico hasta la frontera con un swap, y al final mete el pivote en la frontera — su lugar definitivo:

def _partition(a, lo, hi, probe=None):
    """Lomuto partition. Take the last element as the pivot and sweep from lo to hi,
    keeping a boundary i such that everything left of it is smaller than the pivot.
    Each element smaller than the pivot is swapped up to the boundary; finally the
    pivot is swapped into the boundary, landing in its permanent sorted position."""
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if probe is not None:
            probe.append({"arr": list(a), "pivot": hi, "i": i, "j": j, "lo": lo, "hi": hi, "placed": False})
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]       # drop the pivot into its final place
    if probe is not None:
        probe.append({"arr": list(a), "pivot": i, "i": i, "j": i, "lo": lo, "hi": hi, "placed": True})
    return i

Míralo funcionar

Aquí está quicksort particionando diez barras. Morado es el pivote (el último elemento de la región actual); amarillo es la barra que se está comparando contra él; las barras azules resultaron más chicas y se movieron a la zona creciente de "menor que el pivote" a la izquierda; las grises todavía no se procesan; las oscuras están fuera de la partición actual. Ve paso a paso: el cursor amarillo barre de izquierda a derecha, el azul junta a los chicos, y cuando el barrido termina el pivote hace swap a su lugar y se pone verde — fijo en su posición final ordenada. Después las dos regiones a cada lado de él se particionan de la misma forma:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña desde cero es nuestro quicksort con partición de Lomuto. La pestaña de librería es list.sort — Timsort en el caso de CPython, aunque el qsort de C y los sorts inestables de C++/Rust son introsort: quicksort que vigila su profundidad de recursión y se cambia a heapsort si un mal pivote lo hace bajar demasiado, consiguiendo la velocidad de quicksort con la garantía de peor caso del merge sort.

"""Quicksort — the other O(n log n) sort, and the one most standard libraries use
for arrays of primitives. Like merge sort it's divide-and-conquer, but it splits
differently: pick a pivot, partition the array so everything smaller is on its left
and everything larger on its right, then recurse into each side. The pivot lands in
its final sorted position, and no merge is needed — the work happens on the way down,
in place, which is why quicksort is usually faster than merge sort in practice.

The catch is the pivot. A good split gives O(n log n); a consistently bad one gives
O(n²). This implementation uses the last element as the pivot (simple, and it lets us
demonstrate the worst case), and recurses into the smaller side first to keep the
stack depth O(log n).
"""


# region: quicksort
def quicksort(a, probe=None):
    """O(n log n) average, O(n^2) worst: partition around a pivot, recurse on each
    side. In place — the rearranging happens in the array itself, no merge."""
    a = list(a)
    _qsort(a, 0, len(a) - 1, probe)
    return a


def _qsort(a, lo, hi, probe):
    # Recurse into the SMALLER partition and loop on the larger. This bounds the
    # recursion depth to O(log n) even when the partitions are unbalanced, so a
    # bad pivot costs time but never a stack overflow.
    while lo < hi:
        p = _partition(a, lo, hi, probe)
        if p - lo < hi - p:
            _qsort(a, lo, p - 1, probe)
            lo = p + 1
        else:
            _qsort(a, p + 1, hi, probe)
            hi = p - 1
# endregion


# region: partition
def _partition(a, lo, hi, probe=None):
    """Lomuto partition. Take the last element as the pivot and sweep from lo to hi,
    keeping a boundary i such that everything left of it is smaller than the pivot.
    Each element smaller than the pivot is swapped up to the boundary; finally the
    pivot is swapped into the boundary, landing in its permanent sorted position."""
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if probe is not None:
            probe.append({"arr": list(a), "pivot": hi, "i": i, "j": j, "lo": lo, "hi": hi, "placed": False})
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]       # drop the pivot into its final place
    if probe is not None:
        probe.append({"arr": list(a), "pivot": i, "i": i, "j": i, "lo": lo, "hi": hi, "placed": True})
    return i
# endregion

"""`list.sort` / `sorted` is Timsort (a merge sort), not quicksort — CPython chose a
stable merge sort. But quicksort is what many other languages use for arrays of
primitives: C's `qsort`, and C++/Rust's unstable sort, are introsort — quicksort with
a heapsort fallback to dodge the O(n²) worst case. So the honest counterpart is the
built-in in-place sort, and the point of the face-off is that our quicksort matches
its O(n log n) on random data and blows up on the input that makes quicksort quadratic.
"""


# region: sort_builtin
def sort_builtin(a):
    """In-place sort via list.sort (Timsort): O(n log n) worst case, stable, in C."""
    a = list(a)
    a.sort()
    return a
# endregion

Desde cero vs librería

Con datos aleatorios nuestro quicksort ordenó 80000 enteros en unos 61 ms contra los 7.4 ms del sort de la librería — como 8 veces más lento, la conocida constante de Python contra C. Fíjate que le ganó a nuestro merge sort del capítulo pasado (86 ms) en la misma tarea, que es el punto práctico: la partición in place de quicksort tiene una constante más chica que el asigna-y-mezcla del merge sort, así que entre los sorts O(n log n) suele ser el más rápido, y por eso es el default para ordenar arrays en la mayoría de los lenguajes. Pero la gráfica del peor caso es la lección que sobrevive al benchmark: el mismísimo código que es rápido con datos aleatorios es 141 veces más lento con datos ordenados, porque un pivote fijo se topó con su adversario. La librería nunca tiene este problema — Timsort no tiene mal caso, e introsort le pone tope a la profundidad de quicksort — y esa es la razón de fondo para irte con lo que ya viene integrado.

Dónde te lo vas a encontrar de verdad

Quicksort, en su forma endurecida de introsort, es el sort detrás de qsort en C, std::sort en C++, y el sort inestable de Rust y muchos otros lenguajes — donde sea que ordenes un array de primitivos y no necesites estabilidad. Su paso de partición es útil por su cuenta: es el núcleo de quickselect (el siguiente capítulo), que encuentra el k-ésimo elemento más chico en O(n) sin ordenar del todo, y particionar aparece en las divisiones de tres vías para datos con muchos duplicados (el problema de la "bandera nacional holandesa"). Incluso donde la librería usa merge sort, entender quicksort es cómo entiendes por qué ordenar es O(n log n) y dónde están sus filos.

Puntos clave

Quicksort particiona alrededor de un pivote — menores a la izquierda, mayores a la derecha, pivote a su lugar — y recursa, ordenando in place en tiempo promedio $O(n \log n)$ con una constante chica que normalmente lo vuelve el sort por comparación más rápido. Su costo es el pivote: uno malo da $O(n^2)$, y con un pivote fijo ingenuo el detonante es un input ordenado cualquiera, así que tienes que aleatorizar el pivote o usar un sort de librería que lo haga. Es el contrapeso del merge sort — más rápido e in place, pero con un peor caso que merge sort no tiene.

Falta un sort más para completar el trío de comparación. Heapsort, el que sigue, es el que consigue $O(n \log n)$ garantizado, como merge sort, pero in place, como quicksort — lo mejor de ambos en el papel — usando una estructura de datos que todavía no construimos: el heap binario. También es el respaldo al que introsort se cambia cuando quicksort se porta mal, así que cierra el círculo del peor caso de este capítulo.