quick-select.js

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

function partition(arr, start, end) {
  const pivot = arr[end];
  let nextLeftIdx = start;
  for (let i = start; i < end; ++i) {
    if (arr[i] < pivot) {
      swap(arr, nextLeftIdx, i);
      nextLeftIdx++;
    }
  }
  
  swap(arr, nextLeftIdx, end);
  
  return nextLeftIdx;
}

function swap(arr, i, j) {
  const tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

const arr = [9, 4, 1, 6, 7, 3, 8, 2, 5];
quickSelect(arr, 0, arr.length - 1, 4); // 5