Why does this quickselect sometimes return the wrong kth value?

programming web dev
1

Hey everyone, I’m wiring up a leaderboard helper and trying to avoid a full sort because the list can get pretty big, but my quickselect version occasionally returns the wrong item after a few swaps and that makes me nervous about using it in production.

function quickselect(arr, k, left = 0, right = arr.length - 1) {
  if (left === right) return arr[left];

  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]];

  if (k === i) return arr[i];
  if (k < i) return quickselect(arr, k, left, i - 1);
  return quickselect(arr, k, i + 1, right);
}

console.log(quickselect([9, 1, 4, 7, 3, 8, 2], 3));

What am I getting wrong in the partition logic here, especially when I want speed without quietly returning a bad rank?

Hari

2

Your partition code is okay. The bug is just that k is being treated as a zero-based index.

So quickselect([9, 1, 4, 7, 3, 8, 2], 3) asks for index 3, which is the 4th smallest value, not the 3rd. If you mean “3rd smallest,” pass k - 1.


js
console.log(quickselect([9, 1, 4, 7, 3, 8, 2], 2)); // 3rd smallest -> 4
console.log(quickselect([9, 1, 4, 7, 3, 8, 2], 3)); // 4th smallest -> 7

If this is for leaderboard ranks, I’d rename the param to targetIndex or subtract 1 at the call site so nobody trips on it later.

Quelly