JavaScript QuickSelect Algrothm with the help of Meidan of Medians

Abhishek Kumar Gupta
2 min readOct 29, 2023

--

In computer science, the median of medians is an approximate median selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, most commonly quickselect, that selects the kth smallest element of an initially unsorted array. Median of medians finds an approximate median in linear time. For more information please see: Median of medians.

function median_algorithm(nums, k) {
const chunkSize = 5;
let chunks = [];
let medians = [];
for(let i=0; i < nums.length; i += chunkSize) {
// We have to split the list into chunks of 5 items and sort each array
let chunck = nums.slice(i, i+chunkSize).sort((a, b) => a > b ? 1: -1);
// the median is the middle item in the sorted order
const median = chunck[parseInt(chunck.length / 2 , 10)]
chunks.push(chunck);
medians.push(median);
}
// The median of all medians is the pivot Value
const pivotValue = medians[parseInt(medians.length / 2 , 10)]
// Partion Phase (Now Partition the original array into two different array
const leftArray = nums.filter(num => num < pivotValue);
const rightArray = nums.filter(num => num > pivotValue);
// selection Phase
if(k < leftArray.length) {
// We have to consider the left array because we are looking for
// smaller items
return median_algorithm(leftArray, k)
} else if (k > leftArray.length) {
// We have to consider the right array because we are looking for
// larger items
return median_algorithm(rightArray, k - leftArray.length - 1)
} else {
return pivotValue;
}

}
function select(nums, k) {
return median_algorithm(nums, k-1);
}



x = [1, -5, 0, 10, 15, 20, 3, -1, 21, 22, 23, 24, 25, 26, 27, 28, 29]
console.log(select(x, 3))

--

--

Abhishek Kumar Gupta
Abhishek Kumar Gupta

Written by Abhishek Kumar Gupta

Web and Native Mobile App Developer.

No responses yet