Kata de algoritmos: vecinos más cercanos sin ordenar todo

El kata de esta semana pedía lo de siempre: dado un array de 10.000 coordenadas en dos dimensiones, devolver los k puntos más cercanos al origen. La trampa está en el verbo. Ordenar todo el array por distancia y cortar los primeros k funciona, pero es tirar trabajo a la basura cuando k es pequeño. Y cuando k es grande, ordenar entero deja de ser tan mala idea. La pregunta real no es cuál algoritmo es mejor, sino dónde está el punto de cruce.

Implementé dos candidatos. El primero, quickselect: particionar el array alrededor de un pivote hasta que la posición k-ésima quede fija, y quedarse con lo que hay a la izquierda. El segundo, un heap parcial de tamaño k que recorre el array una sola vez y va expulsando el vecino más lejano cuando se llena. Ambos evitan el orden completo, pero lo hacen por caminos distintos y con costes de caché que no aparecen en la notación asintótica.

Los dos fragmentos, sin adornos

Quickselect en su forma mínima, con partición de Lomuto y un pivote aleatorio para no caer en el peor caso con datos ya ordenados:

function quickselect(arr, k, lo = 0, hi = arr.length - 1) {
  while (lo < hi) {
    const p = partition(arr, lo, hi);
    if (p === k) return;
    p < k ? lo = p + 1 : hi = p - 1;
  }
}

El heap parcial, en cambio, mantiene una cola de prioridad acotada. Cada punto entra, y si el heap ya tiene k elementos, se compara contra la raíz y se sustituye solo cuando mejora:

for (const p of puntos) {
  const d = p.x * p.x + p.y * p.y;
  if (heap.size < k) heap.push(d);
  else if (d < heap.peek()) { heap.pop(); heap.push(d); }
}

Qué dicen los tiempos en Node 20

Medí ambos con performance.now() sobre el mismo array de 10.000 puntos, repitiendo cada medición veinte veces y quedándome con la mediana. Con k=10, quickselect gana por un margen amplio: apenas toca una fracción del array. Con k=1000, la ventaja se estrecha. Y alrededor de k=200 el heap parcial empieza a empatar, no porque su complejidad mejore, sino porque el patrón de acceso a memoria del heap cabe mejor en la caché del procesador que las particiones repetidas de quickselect.

Ese detalle es el que suele quedarse fuera de los apuntes. La complejidad asintótica describe el crecimiento, no el comportamiento real sobre un array concreto en una máquina concreta. Si el array cabe en L2 y el heap es pequeño, la constante importa más que el exponente.

El orden de los ejes también pesa

Un detalle que descubrí tarde: guardar los puntos como [x, y, x, y, ...] en un solo array tipado es más rápido que un array de objetos con dos propiedades. La razón es aburrida y real: menos saltos de puntero, mejor localidad. Cambiar esa estructura movió las mediciones un quince por ciento sin tocar el algoritmo. Si vas a repetir el kata, prueba las dos formas antes de decidir cuál publicas.