¿Qué es QuickSelect?

QuickSelect es un algoritmo eficiente para encontrar el nth elemento más pequeño en un arreglo (o cualquier posición k específica). Se basa en el enfoque de "divide y vencerás", similar a Quick Sort, pero evita ordenar completamente el arreglo, enfocándose solo en la posición deseada.

El Código

                
// Este algoritmo implementa QuickSelect para encontrar el nth elemento más pequeño en un arreglo.

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;

  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

function quickSelect(arr, left, right, k) {
  if (left === right) {
    return arr[left];
  }

  const pivotIndex = partition(arr, left, right);

  if (k === pivotIndex) {
    return arr[k];
  } else if (k < pivotIndex) {
    return quickSelect(arr, left, pivotIndex - 1, k);
  } else {
    return quickSelect(arr, pivotIndex + 1, right, k);
  }
}

function findNthSmallestElement(arr, n) {
  if (n < 1 || n > arr.length) {
    throw new Error("n está fuera del rango del array");
  }
  return quickSelect(arr, 0, arr.length - 1, n - 1);
}

// Ejemplo de uso
const arr = [7, 10, 4, 3, 20, 15];
const n = 3;
const nthSmallest = findNthSmallestElement(arr, n);
console.log(`El ${n}º elemento más pequeño es:`, nthSmallest);
                
            

Puntos Clave del Algoritmo

• Entrada: Un arreglo (arr) y un índice n.
• Salida: El nth elemento más pequeño en el arreglo.
• Método:
  • Selecciona un pivote y particiona el arreglo en dos partes: elementos menores o iguales al pivote, y elementos mayores.
  • Determina si el índice deseado está en la misma posición que el pivote.
  • Si no está, aplica el mismo proceso recursivamente en la partición correspondiente.
• Complejidad:
  • Peor caso: O(n²), ocurre si las particiones están desbalanceadas.
  • Promedio: O(n), debido a las divisiones eficientes.
• Ventajas: No necesita ordenar el arreglo completo, lo que ahorra tiempo.
• Desventajas: El rendimiento depende de la selección del pivote.

Ejemplo de Ejecución

Arreglo inicial: [7, 10, 4, 3, 20, 15]

Queremos encontrar el 3er elemento más pequeño.

Proceso de partición:

1. Selecciona el pivote 15. Particiona en [7, 10, 4, 3, 20]. El índice del pivote es 4.
2. El índice deseado 2 está a la izquierda del pivote. Selecciona 10 como pivote en [7, 10, 4, 3].
3. El índice deseado 2 es el pivote 7. Devuelve 7.

Resultado: El 3er elemento más pequeño es 7.

Información Adicional

QuickSelect es una solución eficiente para problemas que requieren encontrar elementos en posiciones específicas, como el kth mayor o menor elemento. Su uso es común en análisis de datos y optimización.