Note: Please don't interpret this as "homework question." This is just a thing I curious to know :)
The median of five is sometimes used as an exercise in algorithm design and is known to be computable using only 6 comparisons.
What is the best way to implement this "median of five using 6 comparisons" in C# ? All of my attempts seem to result in awkward code :( I need nice and readable code while still using only 6 comparisons.
public double medianOfFive(double a, double b, double c, double d, double e){
//
// return median
//
return c;
}
Note: I think I should provide the "algorithm" here too:
I found myself not able to explain the algorithm clearly as Azereal did in his forum post. So I will reference his post here. From http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085
Well I was posed this problem in one of my assignments and I turned to this forum for help but no help was here. I eventually found out how to do it.
Start a mergesort with the first 4 elements and order each pair (2 comparisons)
Compare the two lower ones of each pair and eliminate the lowest one from the possibilities (3 comparisons)
Add in the 5th number set aside to the number without a pair and compare the two (4 comparisons)
Compare the two lowest of the two new pairs and eliminate the lower one (5 comparisons)
Compare the one by itself and the lower of the last pair and the lower number is the median
The possible median is within the parentesis
(54321)
5:4 3:2 2 comparisons
(4<5 2<3 1)
4:2 3 comparisons
2(4<5 3 1)
1:3 4 comparisons
2(4<5 1<3)
4:1 5 comparisons
1,2(4<5 3)
4:3 6 comparisons
1,2(3)4,5
Three is the median
EDIT: As your request and to prevent myself from getting more downvotes, this are C++ code I wrote to find median of five. Don't mind it's awkwardness:
double StageGenerator::MedianOfFive(double n1, double n2, double n3, double n4, double n5){
double *a = &n1, *b = &n2, *c = &n3, *d = &n4, *e = &n5;
double *tmp;
// makes a < b and b < d
if(*b < *a){
tmp = a; a = b; b = tmp;
}
if(*d < *c){
tmp = c; c = d; d = tmp;
}
// eleminate the lowest
if(*c < *a){
tmp = b; b = d; d = tmp;
c = a;
}
// gets e in
a = e;
// makes a < b and b < d
if(*b < *a){
tmp = a; a = b; b = tmp;
}
// eliminate another lowest
// remaing: a,b,d
if(*a < *c){
tmp = b; b = d; d = tmp;
a = c;
}
if(*d < *a)
return *d;
else
return *a;
}
It should be more compact, isn't it ?
EDIT:
As @pablito pointed out in his answer. The built-in List.Sort() cannot fulfill this requirement since it uses up to 13 comparisons :]