kth_largest_element.js

function swap(array, i, j) {
  const temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

function kLargest(array, k) {
  const partition = (start, end) => {
    let i = start + 1;
    let j = end - 1;

    while (true) {
      while (i < j && array[i] < array[start]) {
        ++i;
      }

      while (i <= j && array[j] >= array[start]) {
        --j;
      }

      if (i > j) {
        break;
      }

      swap(array, i, j)
      ++i;
      --j;
    }

    swap(array, start, j);
    return j
  }

  let start = 0;
  let end = array.length;
  let pivot = null;

  do {
    if (pivot !== null) {
      if (array.length - k > pivot) {
        start = pivot + 1;
      } else {
        end = pivot - 1;
      }
    }
    pivot = partition(start, end);
  } while (pivot != array.length - k)

  return array[pivot];
}

if (require.main == module) {
  console.log(kLargest([3,2,3,1,2,4,5,5,6], 4), '==', 4)
}