Question

2. (10) Given a ”black-box” worst-case linear-time median subroutine, give a simple, linear-time algorithm that solves the selection problem for any given k, where 1 ≤ k ≤ n. Once again, an algorithm should be presented first, followed by its analysis.

Answer 1

Let's Start with the objective, we want to find the "kth smallest" element in a array.

We have a function which can in linear time find the median. Now the algorithm goes as follows.

Step 1: Break the array into groups of 5 elements (a odd number) and get the median of each of these items i.e. total N/5 medians and put in a separate array

Step 2: Find the median of the array of all medians, that will be med_of_medians let's say.

Step 3: If we have N/10 medians smaller then med_of medians then we have N/10 * 3 elements smaller then the med_medians ( in worse case)

Step 4:

Case1- if the subset of items, smaller then . med_of_medians have more then "k" do the same . operations as Step 1-3 on them.

Case 2- If those numbers are less then "k" numbers then

. delete those numbers (let's say m numbers) and

make k=k-m. And do 1-3 for the remaining

Case 3- If there are exactly K number then the biggest

. number in that set of numbers is the required item.

Explaination -

We divide the array into "N/5" part and can do with 7/9/11 anything for the same.

And then make a median of all these median called med_of_ median.

Now this med of median, will be greater then N/10 items in this case and so we'll have all the numbers smaller then the Medians who themselves are smaller then med_median so we got in this case the smallest N/10x(3) if we include the median numbers in the array, and if we want Smallest K element

Then there is only 3 possibly

K in larger then this number so we delete this and find another group of smallest number and make k=k-m

Else k is smaller on which we try to find a smaller group of smallest number by same process we found this one

Third and the base case we got exactly K items in that case the biggest on this group is the kth item ( and we don't need to sort for that also) it's the median right before the med_if_median to its left.

Hope it helps, if any doubts put in comments