"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:In discussing this problem I looked up some of the possible solutions, and discovered a "median of medians" algorithm that intrigued me.
It's basis is to divide the dataset into groups of 5 and calculate the median of each group, so my first thought was: why 5? Since the next logical set for a median would be 11, I wonder if this is a throwback to the days when machines only had 8 registers available? If anybody has any other ideas, I'd love to know. And is there any advantage of using 5 over 7 as the base?
Winston Gutkowski wrote:However, that aside, it got me thinking; because it's a problem that (oddly enough) I've never had to deal with:
What is the most efficient way of determining the median of specifically a group of 5 values?
I've been mulling it over for a few hours and think I'm pretty close to the best (mine involves at most 6 comparisons); but I'm interested in other suggestions, because I've been known to miss the obvious. I'm also finding it darn difficult to prove to myself that my solution works empirically.
Winston
~ Mansukh
Mansukhdeep Thind wrote:And you are attempting to do that in the least possible time. Am I correct?
What is the objective of doing so much work just to find a "median of medians" which would only serve to be the "pivot" for the partition algorithm later?
Mansukhdeep Thind wrote:what I am asking is what does this algorithm achieve over and above the one that I implemented in my code?
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
The reason is that by choosing blocks of 3, we might lose the guarantee of having an O(n) time algorithm.
For blocks of 5, the time complexity is
T(n) = T(n/5) + T(7n/10) + O(n)
For blocks of 3, it comes out to be
T(n) = T(n/3) + T(2n/3) + O(n)
Check this out: http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf
What is the most efficient way of determining the median of specifically a group of 5 values?
Paul Mrozik wrote:You are, in fact, asking about the most efficient way to sort five elements, right? As the median will always be the third value in a sorted set of 5.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here