Hi, I have a general question....
Hi, I have a general question. Does the median of medians algo really work for finding median of an unsorted big array? E.g. take 1 2 5, 3 4 6, 7 8 9: medians are 2, 4, 8. Median of medians is 4 but overall median is 5.
Another example,
we have 45 distinct numbers divided to 9 group with 5 elements.
48 43 38 33 28 23 18 13 8
49 44 39 34 29 24 19 14 9
50 45 40 35 30 25 20 15 10
51 46 41 36 31 26 21 16 53
52 47 42 37 32 27 22 17 54
The first step is sorting every group (in this case they are already sorted)
Second step recursively, find the "true" median of the medians (50 45 40 35 30 25 20 15 10) i.e. the set will be divided into 2 groups:
50 25
45 20
40 15
35 10
30
sorting this 2 groups
30 10
35 15
40 20
45 25
50
the medians is 40 and 15 (in case the numbers are even we took left median) so the returned value is 15 however "true" median of medians (50 45 40 35 30 25 20 15 10) is 30.
Please explain what am I missing? I have read at many places that median of medians algo doesnt work. If it does can you explain above and also give a good reference to read for the algo?
Hi, at each step when we divide list into group of five and consider medians of all groups and take median( let's say m' ) then m' is approximate median and we need to find exact mean..
- Anonymous May 26, 2012