Quickselect

Encuentra el k-ésimo más pequeño en O(n) — sin ordenar. El partition de quicksort, recurriendo en UN solo lado.

Un cambio respecto a quicksort

• Particiona alrededor de un pivote → el pivote cae en el rango p
• p == k → listo. k < p → recurre a la izquierda. k > p → recurre a la derecha.
• Ignora el lado que no puede contener el rango k
• n + n/2 + n/4 + … = 2n → O(n) promedio

Míralo cerrarse sobre el rango k

Rosa = rango objetivo. Oscuro = regiones descartadas. Cada partition tira un lado completo.

Selección O(n) vs ordenamiento O(n log n)

Quickselect ~empata con el sort en C (handicap de Python). heapq para la mediana: 6× peor — k equivocada.

Ajusta la herramienta a k

• k chica (top-10) → heapq.nsmallest (O(n log k))
• Mediana / rango arbitrario → quickselect (O(n))
• Muchos rangos / orden completo → mejor ordena
• Aleatoriza el pivote (peor caso O(n²), igual que quicksort)

Para llevar

Calcula solo el orden suficiente para colocar un elemento. Mediana de medianas garantiza el peor caso lineal. Siguiente bloque: árboles.