[ACCEPTED]-How do I calculate the "median of five" in C#?-median
I found this post interesting and as an 2 exercise I created this which ONLY does 1 6 comparisons and NOTHING else:
static double MedianOfFive(double a, double b, double c, double d, double e)
{
return b < a ? d < c ? b < d ? a < e ? a < d ? e < d ? e : d
: c < a ? c : a
: e < d ? a < d ? a : d
: c < e ? c : e
: c < e ? b < c ? a < c ? a : c
: e < b ? e : b
: b < e ? a < e ? a : e
: c < b ? c : b
: b < c ? a < e ? a < c ? e < c ? e : c
: d < a ? d : a
: e < c ? a < c ? a : c
: d < e ? d : e
: d < e ? b < d ? a < d ? a : d
: e < b ? e : b
: b < e ? a < e ? a : e
: d < b ? d : b
: d < c ? a < d ? b < e ? b < d ? e < d ? e : d
: c < b ? c : b
: e < d ? b < d ? b : d
: c < e ? c : e
: c < e ? a < c ? b < c ? b : c
: e < a ? e : a
: a < e ? b < e ? b : e
: c < a ? c : a
: a < c ? b < e ? b < c ? e < c ? e : c
: d < b ? d : b
: e < c ? b < c ? b : c
: d < e ? d : e
: d < e ? a < d ? b < d ? b : d
: e < a ? e : a
: a < e ? b < e ? b : e
: d < a ? d : a;
}
This is basically just factoring out the 1 swapping and sorting code from your C++ example:
private static void Swap(ref double a, ref double b) {
double t = a;
a = b;
b = t;
}
private static void Sort(ref double a, ref double b) {
if (a > b) {
double t = a;
a = b;
b = t;
}
}
private static double MedianOfFive(double a, double b, double c, double d, double e){
// makes a < b and c < d
Sort(ref a, ref b);
Sort(ref c, ref d);
// eleminate the lowest
if (c < a) {
Swap(ref b, ref d);
c = a;
}
// gets e in
a = e;
// makes a < b
Sort(ref a, ref b);
// eliminate another lowest
// remaing: a,b,d
if (a < c) {
Swap(ref b, ref d);
a = c;
}
return Math.Min(d, a);
}
Thanks. I know your posts are quite old, but 12 it was useful for my issue.
I needed a way 11 to compute the median of 5 SSE/AVX registers 10 (4 floats / 8 floats at once, or 2 doubles/4 9 doubles at once):
without any conditional 8 jumps
only with min/max instructions
If the 7 min/max functions are programmed for scalar 6 registers with conditional jumps, my code 5 is not optimal in term of comparisons. But 4 if the min/max functions are coded with 3 corresponding CPU instructions, my code 2 is very effective because no conditional 1 jump is done by the CPU when executing.
template<class V>
inline V median(const V &a, const V &b, const V &c)
{
return max(min(a,b),min(c,max(a,b)));
}
template<class V>
inline V median(const V &a, const V &b, const V &c, const V &d, const V &e)
{
V f=max(min(a,b),min(c,d)); // discards lowest from first 4
V g=min(max(a,b),max(c,d)); // discards biggest from first 4
return median(e,f,g);
}
An interesting thread here:
Quote from thread:
Put 10 the numbers in an array.
Use three comparisons 9 and shuffle around the numbers so that a[1] < a[2], a[4] < a[5], and 8 a[1] < a[4].
If a[3] > a[2], then the 7 problem is fairly easy. If a[2] < a[4], the 6 median value is the smaller of a[3] and 5 a[4]. If not, the median value is the smaller 4 of a[2] and a[5].
So a[3] < a[2]. If a[3] > a[4], then 3 the solution is the smaller of a[3] and 2 a[5]. Otherwise, the solution is the smaller 1 of a[2] and a[4].
This is pretty ugly and could use some refactoring, but 2 it explicitly walks through all the comparisons 1 and swaps so you can see what's going on.
public double medianOfFive(double a, double b, double c, double d, double e){
double median;
// sort a and b
if(a > b) // comparison # 1
{
double temp = a;
a = b;
b = temp;
}
// sort c and d
if(c > d) // comparison # 2
{
double temp = c;
c = d;
d = temp;
}
// replace the lower of a and c with e
// because the lowest of the first four cannot be the median
if(a < c) // comparison # 3
{
a = e;
// re-sort a and b
if(a > b) // comparison # 4
{
double temp = a;
a = b;
b = temp;
}
}
else
{
c = e;
// re-sort c and d
if(c > d) // comparison # 4
{
double temp = c;
c = d;
d = temp;
}
}
// eliminate a or c, because the lowest
// of the remaining four can't be the median either
if(a < c) // comparison #5
{
if(b < c) // comparison #6
{
median = c;
}
else
{
median = b;
}
}
else
{
if(d < a) // comparison #6
{
median = a;
}
else
{
median = d;
}
}
return median;
}
Just to check how many comparisons:
class MyComparable : IComparable
{
public static int NumberOfComparisons = 0;
public int NumPart { get; set; }
#region IComparable Members
public int CompareTo(object obj)
{
NumberOfComparisons++; //I know, not thread safe but just for the sample
MyComparable mc = obj as MyComparable;
if (mc == null)
return -1;
else
return NumPart.CompareTo(mc.NumPart);
}
#endregion
}
class Program
{
static void Main(string[] args)
{
List<MyComparable> list = new List<MyComparable>();
list.Add(new MyComparable() { NumPart = 5 });
list.Add(new MyComparable() { NumPart = 4 });
list.Add(new MyComparable() { NumPart = 3 });
list.Add(new MyComparable() { NumPart = 2 });
list.Add(new MyComparable() { NumPart = 1 });
list.Sort();
Console.WriteLine(MyComparable.NumberOfComparisons);
}
}
the result 1 is 13.
For completeness, the question is a specific 2 case of a sorting network, which Knuth (Art of Computer Programming, vol 3) covers in great detail. The 1 classic paper by K.E. Batcher on the subject is brief and worth reading.
This should do it
private Double medianofFive(double[] input)
{
Double temp;
if (input[0] > input[1])//#1 - sort First and Second
{
temp = input[0];
input[0] = input[1];
input[1] = temp;
}
if (input[2] > input[3])//#2 sort Third and Fourth
{
temp = input[2];
input[2] = input[3];
input[3] = temp;
}
// replace the smaller of first and third with 5th, then sort
int smallerIndex = input[0] < input[2] ? 0 : 2;//#3
input[smallerIndex] = input[4];
//sort the new pair
if(input[smallerIndex]>input[smallerIndex+1])//#4
{
temp = input[smallerIndex];
input[smallerIndex] = input[smallerIndex+1];
input[smallerIndex+1] = temp;
}
//compare the two smaller numbers
// then compare the smaller of the two's partner with larger of the two
// the smaller of THOSE two is the median
if (input[2] > input[0])
//#5
{
temp = input[2] > input[1] ? input[1] : input[2];//#6
}
else
{
temp = input[0] > input[3] ? input[3] : input[0];//#6
}
return temp;
}
0
Here's a bit of a variant on the other answers, which 52 provides on average from 3.33% to 66.67% improvement 51 over 6 comparisons, and fully partitions 50 the 5 elements around their median as a 49 bonus at no extra cost.
It's possible to 48 find the median of 5 distinct elements in 47 an average of 5.8 comparisons (averaged 46 over all permutations) by using median-of-3 45 and quickselect, using median-of-3 to select 44 the pivot from a sample of 3 of the 5 elements. Median-of-3 43 partitions those three elements, which need 42 not be recompared to the pivot when partitioning 41 the remaining 2 elements. So far that's 40 4-5 comparisons to partition the 5 elements 39 around one of the three middle elements 38 (the median-of-3 cannot be either the minimum 37 or maximum of 5). Up to 3 more comparisons 36 may be necessary to partition the 5 elements 35 around their median (which strictly speaking 34 is more work than merely finding the median), for 33 a total ranging from 4 to 7 comparisons, with 32 (as mentioned) an average of 5.8 over all 31 possible permutations of 5 distinct elements 30 (fewer comparisons if the elements are not 29 distinct). Note that this differs from 28 the usual always-6-comparisons solutions, in 27 that a few cases of distinct inputs may 26 require as many as 7 comparisons, but on 25 the other hand, most permutations of distinct 24 inputs require no more than 6, and often 23 fewer; moreover it is fairly easy to code 22 to save comparisons for non-distinct inputs 21 (only 2 comparisons are required if all 20 inputs are equal; the code to save comparisons 19 when inputs are not distinct using the usual 18 6-comparison method becomes rather convoluted 17 (try it!), and without that it still takes 16 6 comparisons even when all inputs are equal).
Order 15 statistics other than the median can be 14 found this way: the 2nd smallest or 2nd 13 largest can be found in on average slightly 12 more (5.81666... comparisons), and of course 11 it's possible to find the minimum or maximum 10 with only 4 comparisons.
Based on that, and 9 by request, here's a heavily commented function 8 to return a pointer to the median of 5 elements, using 7 a variadic comparison function. It's written 6 in C, but it should work just as well in 5 the quadrathorpe-y deviant or in sea ploose 4 ploose. Note that this returns a pointer 3 to the median-valued element only; it does 2 not partition the elements (in fact it doesn't 1 move any elements).
/* a virtual swap, preserving both pointers for later use */
#define VSWAP(ma,mb,mt) mt=ma,ma=mb,mb=mt
/* a virtual swap only preserving the first pointer */
#define VSWAP2(ma,mb,munused) ma=mb
/* virtual rotation to the left; reverse the first 3 args for right rotation */
#define ROTATE(ma,mb,mc,mt) (mt)=(ma),(ma)=(mb),(mb)=(mc),(mc)=(mt)
/* median of 5 elements, no data movement, minimum (average 5.8) comparisons */
/* This implementation minimizes the number of comparisons made (min. 2) when
elements compare equal.
*/
/* As no elements are moved, the elements are of course not partitioned around
the element pointed to by the returned pointer (this differs from selection
of the median via quickselect).
*/
/* Results are biased toward the middle: pc, then pb or pd, last pa or pe. */
/* The implementation is based on a simulation of quickselect using partition3
to select a pivot from the middle three elements, with partitioning by
skipping over the 3 partitioned elements. For distinct inputs, it uses on
average 5.8 comparisons (averaged over all permutations of 5 distinct
elements); fewer for inputs with equal elements. That's an improvement of
about 3% over the usual 6-comparison implementation of median-of-5.
*/
void *fmed5(void *pa, void *pb, void *pc, void *pd, void *pe,
int(*compar)(const void *,const void *))
{
void *t;
int c, d;
/* First compare the 3 middle elements to determine their relative
ordering; pb will point to the minimum, pc to the median, and pd to
the maximum of the three.
*/
/* Ternary median-of-3, biased toward middle element if possible, else
first element. Average 8/3 comparisons for 3 elements (distinct values)
= 0.889 comparisons/element
*/
c=compar(pb,pc); /* 1 */
if (0<c) { /* *pb,*pc out-of-order: *pb>*pc */
/* Before doing anything about pb,pc, compare *pc,*pd. */
d=compar(pc,pd); /* 2a */
if (0>d) { /* *pc<*pd: strictly in order */
/* But *pb might be either larger than or smaller than (or equal
to) *pd, so they may (i.e. unless it's known from the earlier
comparison of original *pc and *pd that *pb is larger than
both) have to be compared, Possibilities:
*pc<*pb<=*pd (virtual swap of pb,pc corrects relationship)
*pc<*pd<*pb (virtual rotation to the left corrects it)
*/
c=compar(pb,pd); /* 3a (if needed) */
if (0<c) { /* *pc < *pd < *pb */
ROTATE(pb,pc,pd,t);
} else { /* *pc < *pb <= *pd */
VSWAP(pb,pc,t);
}
} else { /* *pd==*pc<*pb or reversed ordering: *pd<*pc<*pb */
VSWAP(pb,pd,t); /* one (virtual) swap takes care of it */
} /* *pc:*pd comparisons results if-else */
/* Note that if pc,pd compare equal, pc remains as the chosen
median (biased toward the middle element).
*/
} else if (0==c) { /* *pb,*pc compare equal */
/* Either pb or pc can be taken as the median; bias here is towards
pc, which is already in the middle position. But pd might be
the minimum of the three or the maximum (or it may also be equal
to both pb and pc).
*/
d=compar(pb,pd); /* 2b */
if (0<d) { /* pb,pd are out-of-order */
VSWAP(pb,pd,t);
}
} else { /* *pb,*pc in strict order: *pb < *pc; how about *pc,*pd? */
d=compar(pc,pd); /* 2c */
if (0<d) { /* *pc,*pd are strictly out-of-order: *pd < *pc */
/* But *pb might be either larger than or smaller than (or equal
to) *pd, so they may (i.e. unless it's known from the earlier
comparison of original *pc and *pd that *pb is larger than
both) have to be compared, Possibilities:
*pb<=*pd<*pc (virtual swap of pc,pd corrects relationship)
*pd<*pb<*pc (virtual rotation to the right corrects it)
*/
c=compar(pb,pd); /* 3b (if needed) */
if (0<c) { /* *pd < *pb < *pc */
ROTATE(pd,pc,pb,t);
} else { /* *pc < *pb <= *pd */
VSWAP(pc,pd,t);
}
} /* *pc:*pd comparisons results if-else */
/* Note that if pc,pd compare equal, pc remains as the chosen
median (biased toward the middle element).
*/
} /* *pb:*pc comparisons results if-else chain */
/* Now pb points to the minimum of pb,pc,pd; pc to the median, and pd
to the maximum.
*/
/* Special case: if all three middle elements compare equal (0==c==d),
any one can be returned as the median of 5, as it's impossible for
either of the other two elements to be the median (unless of course
one or both of them also compares equal to pb,pc,pd, in which case
returning any of pb,pc,pd is still correct). Nothing more needs to
be done in that case.
*/
if ((0!=c)||(0!=d)) { /* Not all three of pb,pc,pd compare equal */
int e;
/* Compare pa and pe to pc. */
e=compar(pa,pc); /* 3c or 4a (iff needed) */
/* If three (or more) of the four elements so far compared are
equal, any of those equal-comparing elements can be chhosen as
the median of 5. If all five elements were arranged in order,
one of the three equal-comparing elements would necessarily be
in the middle (at most both of the remaining elements might be
either larger or smaller than the equal elements). So if pa
compares equal to pc and pc also compared equal to pb or to pd,
nothing more need be done; pc can be considered as the median of
five.
*/
if ((0!=e)||(0!=c)||(0!=d)) { /* no three elements compare equal */
int f;
f=compar(pe,pc); /* 4b or 5a (iff needed) */
/* Check again for three equal comparisons to avoid doing any
unnecessary additional work.
*/
if (
(0!=f) /* also not equal; still not three */
||
( /* 0==f && */
((0!=c)&&(0!=d)) /* at most e and f; not three */
||
((0!=c)&&(0!=e)) /* at most d and f; not three */
||
((0!=d)&&(0!=e)) /* at most c and f; not three */
)
) {
/* Possibilites are that:
one of *pa,*pe is less than (or equal to) *pc and one
is greater than (or equal to) *pc; *pc is the median
of five.
*pa and *pe are both less than *pc; the median of five
is then the maximum of *pa,*pb,*pe (*pc and *pd are
at least as large as those three). The ordering of
those 3 elements has not been established, and it
will take two additional comparisons to do so.
*pa and *pe are both greater than *pc; the median of
five is the minimum of *pa,*pd,*pe (neither *pb nor
*pc can be larger than any of those three).
*/
if ((0<e)&&(0<f)) { /* *pa,*pe both > *pc; median of five is
the minimum of *pa,*pe,*pd
*/
/* Bias towards *pd (originally closest of these three
to the middle. Neither *pa nor *pe has yet been
compared to *pd.
*/
e=compar(pa,pe); /* 5b or 6a (iff needed) */
if (0<e) { /* *pe is smaller */
f=compar(pd,pe); /* 6b or 7a (iff needed) */
if (0<f) { /* *pe is smaller */
VSWAP2(pc,pe,t);
} else { /* *pd is smaller or *pd==*pe */
VSWAP2(pc,pd,t);
}
} else { /* *pa==*pe or *pa is smaller */
f=compar(pd,pa); /* 6c or 7b (iff needed) */
if (0<f) { /* *pa is smaller */
VSWAP2(pc,pa,t);
} else { /* *pd is smaller or *pd==*pa */
VSWAP2(pc,pd,t);
}
}
} else if ((0>e)&&(0>f)) { /* *pa,*pe both < *pc; median of
five is the maximum of *pa,*pb,*pe
*/
/* Bias towards *pb (originally closest of these three
to the middle. Neither *pa nor *pe has yet been
compared to *pb.
*/
e=compar(pa,pe); /* 5c or 6d (iff needed) */
if (0<e) { /* *pa is larger */
f=compar(pa,pb); /* 6e or 7c (iff needed) */
if (0<f) { /* *pa is larger */
VSWAP2(pc,pa,t);
} else { /* *pb is larger or *pa==*pb */
VSWAP2(pc,pb,t);
}
} else { /* *pe is larger or *pa==*pe */
f=compar(pe,pb); /* 6f or 7d (iff needed) */
if (0<f) { /* *pe is larger */
VSWAP2(pc,pe,t);
} else { /* *pb is larger or *pe==*pb */
VSWAP2(pc,pb,t);
}
} /* *pa:*pe results if-else */
} /* median of five: minimum or maximum of three if-else */
} /* not three equal elements among five */
} /* not three equal elements among four */
} /* not three equal elements among three */
return pc;
}
Coding isn't really my thing, but here's the algorithm I would use expressed in natural language. Let's denote these five numbers by a, b, c, d, and 12 e.
Compare a and b, c and d. WLOG let a < b, c < d. (2 11 comparisons so far)
Compare a and c. WLOG let 10 a < c. (3)
Compare b and e. (4) Note that 9 b is used instead of d (and they cannot be 8 swapped) because b is the "counterpart" of 7 the smaller of a and c.
Case 1: let b < e.
____Compare 6 b and c — the greater value is the median. (5)
Case 5 2: let b > e.
____Compare a and e. (5)
____Case 4 2.1: let a < e.
________Compare c and e — the 3 greater value is the median. (6)
____Case 2 2.2: let a > e.
________Compare b and c — the 1 smaller value is the median. (6)
(Formatting is ugly ik >.<)
More Related questions
We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.