find the kth smallest element in an array in typescript

Here is a TypeScript function to find the kth smallest element in an array, using the QuickSelect algorithm:

index.ts
function quickSelect(arr: number[], k: number): number {
  const pivotIndex = Math.floor(Math.random() * arr.length);
  const pivot = arr[pivotIndex];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length; i++) {
    if (i === pivotIndex) continue;
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  if (k <= left.length) {
    return quickSelect(left, k);
  } else if (k === left.length + 1) {
    return pivot;
  } else {
    return quickSelect(right, k - left.length - 1);
  }
}
553 chars
24 lines

The arr parameter is the array to search, and the k parameter is the index of the element to find (starting at 1 for the first smallest).

The function randomly selects a pivot element from the array and partitions the remaining elements into two subarrays: one with elements smaller than the pivot, and one with elements larger than the pivot. It then recursively calls itself on the appropriate subarray until the kth element is found. The partitioning is done in linear time (O(n)), so the overall time complexity of the algorithm is O(n) on average.

To use the function, simply call it with an array and the index of the element you want to find:

index.ts
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const k = 6;
const kthSmallest = quickSelect(arr, k);
console.log(`The ${k}th smallest element is ${kthSmallest}.`);
164 chars
5 lines

This will output:

index.ts
The 6th smallest element is 4.
31 chars
2 lines

gistlibby LogSnag