Monday, October 5, 2009

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
comparisons.
* 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)
{
OPT_SORT(p[0],p[1]);
OPT_SORT(p[2],p[3]);

if ( p[0] < p[2] )
{
OPT_SWAP(p[0],p[2]);
OPT_SWAP(p[1],p[3]);
}

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

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

#undef OPT_SWAP
#undef OPT_SORT



No comments :

Post a Comment