Selection Rank Algorithm

Using selection rank algorithm you can solve problems like find the K smallest or largest elements in an array in O(n) time.

The following selection algorithm can be used if all the elements of the array are unique only.

Selection Rank Algorithm (Javascript)

const rank = (arr, left, right, rankn) => {
  const pivot = arr[random(left, right)];
  const leftEnd = partition(arr, left, right, pivot);
  const leftSize = leftEnd - left + 1;
  if (leftSize === rankn)
    return arr[leftEnd];
  else if (rankn < leftSize)
    return rank(arr, left, leftEnd, rankn);
  else
    return rank(arr, leftEnd + 1, right, rankn - leftSize);
};

const partition = (arr, left, right, pivot) => {
  while (true) {
    while (arr[left] < pivot)
      left++;
    while (arr[right] > pivot)
      right--;
    if (left >= right)
      return right;
    swap(arr, left, right);
  }
};

const random = (min, max) => (Math.floor(Math.random() * (max - min + 1)) + min);

const swap = (arr, left, right) => {
  const temp = arr[left];
  arr[left] = arr[right];
  arr[right] = temp;
};

var arr = [3, 7, 4, 1, 5];
console.log(rank(arr, 0, arr.length - 1, 3));

Output

Demo

You can use this to return the kth ranked element (if the array were sorted) to compare with the elements of the array and all the elements that come before it are k smallest numbers.

for(var i=0; i < arr.length; i++) {
if(arr[i] <= r) {
  console.log(arr[i]);
  }
}

Note
If there are repeated elements in an array, then the above algorithm can be modified and be partitioned into less than, equal to and greater than the pivot element and problem can be addressed.

Related