Median of Medians

Computer Science Level 1

Using the algorithm described for the median-of-medians selection algorithm, determine what the list of medians will be on the following input:

$A = [1,2,3,4,5,1000,8,9,99].$

median_of_medians(A,7)

Hint : In the code, medians is the list of these medians.

Bonus : Feel free to run the code and add some strategic print messages.

[5,1000]

[3,99]

[8,9]

[5]

2 solutions

Bj Korobkin
Nov 27, 2017

The answer could be different depending on one's implementation. This site chooses to select the median by rounding up, whereas others might round down. If we were to select the median by rounding down for cases of arrays with even amounts, the answer would be [3,9]

4/2=2 if the second array has 3 elements. We can solve it as you said. 3/2=1.5 floor(1.5)=1 and ceil(3/2)=2 then I think your solution is not correct. Maybe I missed sth could u please comment?

Ezgi Ozkaya Sevindik - 3 months, 4 weeks ago

Karleigh Moore
May 31, 2016

If we add the line print medians right after we calculate medians on line 5, and run the code, the list of medians will print — the result is [3,99].

This is because the algorithm divides $A$ into lists of five elements each. This means it makes $[1,2,3,4,5]$ and $[1000, 8, 9, 99]$ . The median of the first list is $3$ and the median of the second list is $99$ .

Median of Medians

2 solutions

0 pending reports