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

function getPartitiionIndex(arr, i, j) {
  const pivot = arr[Math.floor((i + j) / 2)];
  while (i <= j) {
    while (arr[i] < pivot) {
      // left is in correct position
      i++;
    }
    while (arr[j] > pivot) {
      // right is in correct position
      j--;
    }
    if (i <= j) {
      swap(arr, i, j);
      i++;
      j--;
    }
  }
  return i;
}

function quickSelect(arr, left, right, k) {
  if (left === right) {
    return arr[left];
  }

  const pivot = getPartitiionIndex(arr, left, right);

  if (pivot === k) {
    return arr[pivot];
  }
 
  if (pivot > k) {
    return quickSelect(arr, k, left, pivot - 1);
  } else {
    return quickSelect(arr, k, pivot + 1, right);
  }
}