Finding the Kth Smallest Element in Linear Time with Quickselect in JavaScript

When analyzing client-side performance metrics, interactive dashboard distributions, or user scoreboards, developers frequently need order statistics such as the 50th percentile median or the top ten values. A common pattern is to invoke array.slice().sort((a, b) => a - b)[k]. While simple, full array sorting executes in $O(n \log n)$ time, introducing unnecessary computational overhead when only a single boundary value is needed.

The Quickselect algorithm provides an optimal alternative. By adapting the partitioning routine from Quicksort, Quickselect isolates the $k$-th smallest element by only recursing or looping into the partition containing the target index. Discarding the irrelevant partition on each iteration yields an expected linear time complexity of $O(n)$, drastically reducing CPU work on large datasets.

Example #

import { quickselect } from './quickselect.js';

// Network latency measurements in milliseconds
const latencies = [142, 38, 895, 210, 56, 74, 312, 18, 490];

// Find the 0-indexed median (5th smallest element, index 4)
const medianLatency = quickselect([...latencies], 4);
console.log(`Median latency: ${medianLatency}ms`); // 142ms

// Find the minimum value (k = 0) without a full sort
const fastestResponse = quickselect([...latencies], 0);
console.log(`Fastest response: ${fastestResponse}ms`); // 18ms

Implementation #

/**
 * Swaps two elements in an array in place.
 * @param {Array<number>} arr
 * @param {number} i
 * @param {number} j
 */
function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

/**
 * Partitions a subarray around a pivot chosen using median-of-three.
 * All elements smaller than the pivot are moved to its left, and larger to its right.
 * @param {Array<number>} arr
 * @param {number} left
 * @param {number} right
 * @returns {number} The final index position of the pivot.
 */
function partition(arr, left, right) {
  // Choose pivot using median-of-three to mitigate worst-case sorted scenarios
  const mid = (left + right) >> 1;
  if (arr[mid] < arr[left]) swap(arr, left, mid);
  if (arr[right] < arr[left]) swap(arr, left, right);
  if (arr[right] < arr[mid]) swap(arr, mid, right);

  const pivotValue = arr[mid];
  // Place pivot at right - 1 boundary
  swap(arr, mid, right - 1);
  let i = left;
  let j = right - 1;

  while (true) {
    while (arr[++i] < pivotValue);
    while (arr[--j] > pivotValue);
    if (i >= j) break;
    swap(arr, i, j);
  }

  // Restore pivot to its partitioned position
  swap(arr, i, right - 1);
  return i;
}

/**
 * Finds the kth smallest element (0-indexed) in an array in expected O(n) time.
 * Mutates the input array slice during partitioning.
 *
 * @param {Array<number>} arr - Array of numerical values.
 * @param {number} k - Zero-based target rank (0 <= k < arr.length).
 * @returns {number} The kth smallest value.
 */
export function quickselect(arr, k) {
  if (k < 0 || k >= arr.length) {
    throw new RangeError('Target rank k must fall within array bounds');
  }

  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    // For small partitions, insertion sort is faster than recursive pivots
    if (right - left < 10) {
      for (let i = left + 1; i <= right; i++) {
        const val = arr[i];
        let j = i - 1;
        while (j >= left && arr[j] > val) {
          arr[j + 1] = arr[j];
          j--;
        }
        arr[j + 1] = val;
      }
      return arr[k];
    }

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

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

  return arr[left];
}

Main Point: Use Quickselect instead of full array sorting to compute medians and order statistics in expected linear time without allocating auxiliary memory.

Credits #

Photo by Federico Di Dio on Unsplash

← Home