Skip to content

Instantly share code, notes, and snippets.

@woonketwong woonketwong/selectionRank
Last active Dec 31, 2015

Embed
What would you like to do?
Selection Rank is a well known algorithm in computer science to find the ith smallest (or largest) element in an array in linear time. If the elements are unique, you can find the ith smallest or largest element in expected O(n) time. The code below implements finding the ith smallest element in javascript.
var selectionRank = function(array, rank){
// randomly select a pivot
var pivotIndex = Math.floor( (Math.random() * array.length) );
var pivot = array[pivotIndex];
// left array stores the smallest <rank> elements in the array
var leftArr = [];
var rightArr = [];
// partition into left and right arrays
for (var i = 0; i < array.length; i++){
if (array[i] <= pivot){
leftArr.push(array[i]);
} else {
rightArr.push(array[i]);
}
}
// re-apply algorithm based on the array states
if (leftArr.length === rank){
// if there are exactly <rank> elements in the left array
return leftArr;
} else if ( leftArr.length > rank){
// if the left array size is larger than <rank>, repeat the algorithm
return selectionRank(leftArr, rank);
} else {
// if the left array is smaller than <rank>, repeat the algorithm
// by passing in the right array,
// and a new rank, i.e <rank> - leftArr.length
// the result returned is concatenated to the left array
var tempResult = selectionRank(rightArr, (rank-leftArr.length));
tempResult.forEach(function(element, index, collection){
leftArr.push(element);
})
return leftArr;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.