Quickselect y estadísticos de orden

Lo que cubre este capítulo

A veces no necesitas todo el orden completo: necesitas un solo elemento de ese orden. La mediana, el percentil 95, el décimo más grande, el umbral para el top-k. Ordenar te da la respuesta, pero hace muchísimo más trabajo del que la pregunta pedía. Quickselect encuentra el k-ésimo elemento más pequeño en tiempo O(n) promedio sin ordenar: toma el partition de quicksort y recurre solo en el único lado que puede contener la respuesta. Es el cierre elegante del bloque de recursión y ordenamiento: la misma maquinaria de quicksort, haciendo menos trabajo para responder una pregunta más acotada.

Un poco de historia

Quickselect es el otro algoritmo de Tony Hoare de 1961. Después de inventar quicksort, se dio cuenta de que el mismo paso de partition podía encontrar un estadístico de orden sin ordenar todo, y lo publicó ese mismo año con el nombre de FIND. O sea que quickselect y quicksort son gemelos, nacieron juntos. La versión de Hoare es O(n) en promedio pero O(n²) en el peor caso, porque hereda el problema del mal pivote de quicksort. Ese cabo suelto se amarró en 1973, cuando Manuel Blum, Robert Floyd, Vaughan Pratt, Ron Rivest y Robert Tarjan — una alineación impresionante, cuatro de ellos futuros ganadores del premio Turing — publicaron el algoritmo de mediana de medianas, el primer método de selección con un peor caso O(n) garantizado. Es un resultado histórico: puedes encontrar la mediana en tiempo lineal, incluso en el peor caso, algo que por un buen rato se dudó que fuera posible. El algoritmo práctico sigue siendo el quickselect de Hoare (mediana de medianas tiene una constante enorme); BFPRT es el capítulo de teoría.

La intuición

Arranca exactamente como quicksort: eliges un pivote y particionas, de modo que todo lo menor queda a la izquierda del pivote y todo lo mayor a la derecha. Ahora el pivote está en su posición final ordenada — llámale rango p, o sea que es el p-ésimo más pequeño. Aquí está toda la idea: tú querías el rango k. Si p es igual a k, el pivote es tu respuesta y terminaste. Si k es menor que p, la respuesta está en algún lugar de la parte izquierda, así que recurres ahí y te olvidas por completo de la parte derecha, porque nada de lo que hay ahí puede ser el k-ésimo más pequeño. Si k es mayor, recurres a la derecha e ignoras la izquierda.

Ese único cambio respecto a quicksort — recurrir en un lado en vez de los dos — es lo que baja el costo de O(n log n) a O(n). Quicksort tiene que ordenar ambas mitades porque necesita el orden completo; quickselect solo necesita un elemento, así que tira la mitad del array en cada paso y nunca voltea a verla. Particionas n elementos, luego como n/2, luego n/4, y esa suma es 2n: lineal.

Complejidad: cómo escala

En promedio, con pivotes suficientemente balanceados, quickselect es $O(n)$: los tamaños de las particiones se encogen geométricamente, y $n + n/2 + n/4 + \cdots = 2n$. Trabaja in place, con $O(1)$ de espacio extra. Igual que quicksort, carga con la maldición del pivote — un pivote consistentemente pésimo te deja en $O(n^2)$ — y aplica el mismo remedio: aleatoriza el pivote para volver eso astronómicamente improbable, o usa mediana de medianas para garantizar el peor caso lineal. La gráfica busca la mediana de arrays de tamaño creciente, comparando quickselect contra ordenar y contra un heap:

En qué es bueno y en qué no

Quickselect es la herramienta correcta cada vez que necesitas un estadístico de orden y no el orden completo: la mediana de un dataset, un percentil para un reporte de latencia, el puntaje de corte de los 100 mejores aspirantes, el k-ésimo vecino más cercano. En todos esos casos, ordenar calcula un ordenamiento entero que vas a tirar a la basura para leer un solo valor; quickselect calcula lo justo para colocar ese valor. Es in place y, en promedio, lineal — asintóticamente lo mejor que puedes hacer, porque como mínimo tienes que mirar cada elemento una vez.

Sus límites son un espejo de los de quicksort. El peor caso O(n²) es real si no aleatorizas el pivote o lo eliges con cabeza. Reacomoda el array (un efecto secundario, si necesitabas el orden original). Y encuentra un solo rango de forma eficiente: si de verdad necesitas muchos estadísticos de orden o toda la secuencia ordenada, mejor ordena una vez y ya. Hay además una sutileza de distribución que el enfrentamiento deja ver: un heap de top-k (heapq.nsmallest) es O(n log k), lo cual es excelente para k chico (el top diez de un millón) pero horrible para k cerca de n/2 (la mediana), donde log k es casi log n. Quickselect es la herramienta a la que le da igual dónde caiga k.

Los datos, o las entradas

El enfrentamiento busca la mediana (el rango más difícil, justo a la mitad) de arrays aleatorios de tamaño creciente, comparando quickselect contra ordenar y contra un heap de top-k. La animación corre quickselect sobre doce elementos buscando el rango 6, y registra cada partition para que veas cómo descarta regiones completas camino a la respuesta.

Constrúyelo, una función a la vez

El ciclo de selección: particionar y luego reducirse al lado donde vive el rango k, ignorando el otro lado por completo:

def quickselect(a, k, probe=None):
    """Return the k-th smallest element (0-indexed) in O(n) average time. Partition
    around a pivot; the pivot lands at some rank p. If p == k, the pivot is the
    answer. If k is smaller, recurse left; if larger, recurse right — and never
    touch the other side, which is where the speedup comes from."""
    a = list(a)
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        p = _partition(a, lo, hi, probe, k)
        if p == k:
            return a[p]
        if p < k:
            lo = p + 1          # the k-th smallest is to the right of the pivot
        else:
            hi = p - 1          # ... or to the left
    raise IndexError("k out of range")


def median(a):
    """The median via quickselect — O(n) average, no full sort. For an even count,
    average the two middle order statistics (two selects, still linear)."""
    n = len(a)
    if n % 2 == 1:
        return quickselect(a, n // 2)
    return (quickselect(a, n // 2 - 1) + quickselect(a, n // 2)) / 2

Reutiliza el partition de quicksort sin cambiarle nada — el mismo barrido de Lomuto que deja el pivote en su rango final:

def _partition(a, lo, hi, probe=None, k=None):
    """Lomuto partition (same as quicksort): last element is the pivot; sweep,
    keeping a boundary i for the 'less than pivot' region; drop the pivot in at the
    end, where it reaches its final sorted rank."""
    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, "k": k, "placed": False})
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    if probe is not None:
        probe.append({"arr": list(a), "pivot": i, "i": i, "j": i, "lo": lo, "hi": hi, "k": k, "placed": True})
    return i

Míralo funcionar

Aquí está quickselect sobre doce barras, cazando el rango 6 — la barra rosa marca la posición objetivo. Morado es el pivote, amarillo la barra que se está comparando, azul la región "menor que el pivote", verde un pivote que aterrizó en su rango final, y las barras oscuras están asentadas: regiones que quickselect descartó porque están del lado equivocado de la respuesta. Avanza paso a paso y observa cómo la región oscura crece desde ambos extremos — cada partition tira un lado entero que no puede contener el rango 6, así que la búsqueda se enfoca rapidísimo y toca muchísimos menos elementos de los que tocaría un ordenamiento completo:

El código completo

Ambas versiones en un solo lugar, puedes alternar entre ellas. La pestaña desde cero es quickselect reutilizando el partition de quicksort. La pestaña de librería trae las tres formas integradas de seleccionar: sorted()[k] (O(n log n)), heapq.nsmallest (O(n log k)) y statistics.median, cada una correcta para una forma distinta del problema.

"""Quickselect — find the k-th smallest element (the median, a percentile, the
top-k threshold) in O(n) average time WITHOUT sorting the whole array.

It's quicksort's partition put to a cleverer use. Quicksort recurses into BOTH sides
of the pivot; quickselect recurses into only the ONE side that contains the rank
you're after, because the other side can't hold the answer. Skipping that half turns
quicksort's O(n log n) into O(n): you do a partition over n, then n/2, then n/4, and
that geometric series sums to 2n.
"""


# region: quickselect
def quickselect(a, k, probe=None):
    """Return the k-th smallest element (0-indexed) in O(n) average time. Partition
    around a pivot; the pivot lands at some rank p. If p == k, the pivot is the
    answer. If k is smaller, recurse left; if larger, recurse right — and never
    touch the other side, which is where the speedup comes from."""
    a = list(a)
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        p = _partition(a, lo, hi, probe, k)
        if p == k:
            return a[p]
        if p < k:
            lo = p + 1          # the k-th smallest is to the right of the pivot
        else:
            hi = p - 1          # ... or to the left
    raise IndexError("k out of range")


def median(a):
    """The median via quickselect — O(n) average, no full sort. For an even count,
    average the two middle order statistics (two selects, still linear)."""
    n = len(a)
    if n % 2 == 1:
        return quickselect(a, n // 2)
    return (quickselect(a, n // 2 - 1) + quickselect(a, n // 2)) / 2
# endregion


# region: partition
def _partition(a, lo, hi, probe=None, k=None):
    """Lomuto partition (same as quicksort): last element is the pivot; sweep,
    keeping a boundary i for the 'less than pivot' region; drop the pivot in at the
    end, where it reaches its final sorted rank."""
    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, "k": k, "placed": False})
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    if probe is not None:
        probe.append({"arr": list(a), "pivot": i, "i": i, "j": i, "lo": lo, "hi": hi, "k": k, "placed": True})
    return i
# endregion

"""There's no `quickselect` in the standard library, but three built-ins do selection,
each with a different cost:

  - `sorted(a)[k]` — sort everything, then index. O(n log n): correct, simple, and the
    obvious thing — but it does far more work than needed for one element.
  - `heapq.nsmallest(k+1, a)[k]` — a heap-based partial sort. O(n log k), great when k
    is small (top-10 of a million), worse when k is near n/2 (the median).
  - `statistics.median(a)` — sorts internally, O(n log n).

So the face-off is quickselect's O(n) against sort-then-index's O(n log n): finding one
order statistic without paying to arrange all the others.
"""
import heapq
import statistics


# region: lib
def kth_smallest_sorted(a, k):
    """O(n log n): sort the whole array, then take index k."""
    return sorted(a)[k]


def kth_smallest_heapq(a, k):
    """O(n log k): a partial sort via a heap — cheap for small k, not for the median."""
    return heapq.nsmallest(k + 1, a)[k]


def median_lib(a):
    """statistics.median — sorts internally, O(n log n)."""
    return statistics.median(a)
# endregion

Desde cero vs librería

Este enfrentamiento tiene el resultado más interesante de todo el bloque. Al buscar la mediana de 400000 elementos, nuestro quickselect tardó unos 43 ms y sorted()[k] unos 49 ms — quickselect apenas adelante, prácticamente un empate. Eso es notable cuando recuerdas que quickselect es O(n) y ordenar es O(n log n): el algoritmo con mejor complejidad apenas está saliendo tablas, porque es Python interpretado corriendo contra un sort optimizado en C. La ventaja de O(n) es real — es exactamente lo que le permite a nuestro código en Python siquiera mantener el paso con C — y en un lenguaje compilado quickselect ganaría de calle. La línea de heapq.nsmallest cuenta la otra mitad de la historia: con 274 ms es seis veces más lento que cualquiera de los otros dos, porque encontrar la mediana con un heap de top-k significa k = n/2, y O(n log k) con una k enorme no es más que un ordenamiento lento. La lección es la misma que se repite en todo el bloque — Big-O pone el techo, la constante y la k específica deciden la carrera — y lo práctico es elegir la herramienta de selección según dónde cae k.

Dónde te lo vas a encontrar de verdad

Quickselect corre en todos lados donde se necesita un percentil o un umbral sin ordenar todo. Es numpy.partition y std::nth_element, las funciones que las librerías de datos y científicas ofrecen justo para esto. Los sistemas de monitoreo calculan latencias p50/p95/p99 con él. Machine learning lo usa para k-nearest-neighbors (encontrar los k más cercanos sin ordenar todas las distancias) y para selección de features por percentil. Las bases de datos lo usan para consultas aproximadas de mediana y cuantiles. Cada vez que te cachen ordenando un array nada más para sacar un elemento de en medio, quickselect es la herramienta que hace solo el trabajo que la pregunta pide.

Puntos clave

Quickselect encuentra el k-ésimo elemento más pequeño en tiempo $O(n)$ promedio particionando como quicksort y recurriendo solo en el lado que contiene el rango k: el único cambio respecto a quicksort que convierte O(n log n) en O(n). Es la herramienta para medianas, percentiles y umbrales de top-k: un estadístico de orden sin acomodar el resto. Comparte el riesgo del pivote con quicksort (aleatorízalo) y, en la variante de mediana de medianas, alcanza tiempo lineal garantizado, un hito teórico.

Con eso cerramos el bloque de recursión y ordenamiento, y con él este tramo del libro: desde la recursión y los seis ordenamientos hasta búsqueda y selección, ya tienes el kit de herramientas para acomodar y encontrar en estructuras lineales. El siguiente bloque cambia por completo la forma de los datos. Los árboles renuncian al acomodo plano del array por uno ramificado y, a cambio, hacen que inserción, borrado y búsqueda ordenada sean todas $O(\log n)$ al mismo tiempo — la combinación balanceada que ninguna estructura hasta ahora había logrado. El árbol binario de búsqueda es donde empieza todo.