find the kth smallest element in an array in javascript

To find the kth smallest element in an array, one approach is to sort the array and then return the kth element. However, this approach has a time complexity of O(n log n) which might not be efficient for large arrays.

A better approach is to use a partition algorithm like Quickselect which has an average case time complexity of O(n). The idea behind Quickselect is similar to QuickSort, where we partition the array around a pivot element.

Here's an implementation of Quickselect in JavaScript that finds the kth smallest element in an array:

index.tsx
function quickSelect(arr, k) {
  if (arr.length === 1) return arr[0];

  // Choose a random pivot element
  const pivot = arr[Math.floor(Math.random() * arr.length)];

  // Partition the array around the pivot
  const left = [];
  const right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else if (arr[i] > pivot) {
      right.push(arr[i]);
    }
  }

  if (k <= left.length) {
    // The kth smallest element is in the left partition
    return quickSelect(left, k);
  } else if (k === left.length + 1) {
    // The pivot is the kth smallest element
    return pivot;
  } else {
    // The kth smallest element is in the right partition
    return quickSelect(right, k - left.length - 1);
  }
}

const arr = [3, 1, 4, 2, 5];
const k = 3;
const kthSmallest = quickSelect(arr, k);
console.log(`${k}th smallest element is ${kthSmallest}`);
897 chars
34 lines

The quickSelect() function takes an array arr and an integer k as input, and returns the kth smallest element. We first check the base case where the length of the array is 1. Then, we choose a random pivot element from the array and partition it into two subarrays - one containing elements smaller than the pivot and one containing elements greater than the pivot. We then recursively call quickSelect() on the left or right subarray depending on the value of k.

In the example above, the output will be 3rd smallest element is 3.