Median of 5 numbers in 6 comparisons

Back in 2003 while studying for the Algorithms portion of the PhD Qualifying Examination in Computer Science at Georgia State, I ran across an algorithm so useful it cried out for implementation.

So, dredged from the archives of usenet, the code is below.  It’s vanilla C w/ preprocessor macros but should easily port to any other language.

// Change the type of pixelValue to suit your needs.
typedef int pixelValue ;

#define OPT_SORT(a,b) { if ((a)<(b)) OPT_SWAP((a),(b)); }
#define OPT_SWAP(a,b) { pixelValue temp=(a);(a)=(b);(b)=temp; }

* Function : opt_med5()
* In : A pointer to an array containing 5 pixel values
* Out : The median pixel value of the input array
* Job : Fast computation of the median of 5 pixel values in 6
* Notice : The input array is modified: partly sorted so that the
* middle element is the median.
* No bound checking to gain time, it is up to the caller
* to make sure arrays are allocated.
pixelValue opt_med5(pixelValue *p)

if ( p[0] < p[2] )

OPT_SORT(p[1], p[4]);

if ( p[1] > p[2] )
if ( p[2] > p[4] ) return p[2];
else return p[4];
if ( p[1] > p[3] ) return p[1];
else return p[3];

#undef OPT_SWAP
#undef OPT_SORT

No comments:

Post a Comment