• Status: Solved
• Priority: Medium
• Security: Public
• Views: 376

# What is the fastest way to computer median of 3 integers?

I think I've been straining my head too much lately because this should be easy, none the less...

Given:
int getMedian(int a, int b, int c)

How do I determine the median integer? I don't want to do this by putting them in an array and sorting them, its only 3 integers. I think the most efficient way can probably be performed in 2-3 if statements, but I can't seem to figure them out. Please help, its easy points and you'll be helping my overstressed mind, ha.
0
l4zarus
• 4
• 3
• 2
• +3
1 Solution

Commented:
``````int getMedian(int a, int b, int c)
{
if (a <= b && b <= c || c <= b && b <= a)
return b;
if (b <= a && a <= c || c <= a && a <= b)
return a;
if (a <= c && c <= b || b <= c && c <= a)
return c;
}
``````
0

IT ConsultantCommented:
Hmm, that's a tough one.  I was going to suggest sorting the array and returning the middle element but then I noticed you don't want to sort them.  I poked around Google a bit, and seems most people suggest sorting them - but that's an O(n log n) number operations.  If this is a practical matter, sorting 3 integers would likely be sufficient performance-wise:
``````class Program
{
static void Main(string[] args)
{
Console.WriteLine(GetMedian(1, 3, 5, 6));
}

static int GetMedian(params int[] values)
{
Array.Sort(values);
if (values.Length % 2 == 0)
{
int lowMedian = values[(values.Length / 2) - 1];
int highMedian = values[values.Length / 2];
return (lowMedian + highMedian) / 2;
}
else
return values[(values.Length - 1) / 2];

}
}
``````

That would do any number of ints, but if you know it's always three then:
``````static int GetMedian(int a, int b, int c)
{
int[] values = new int[] { a, b, c };
Array.Sort(values);
return values[1];
}
``````

I think if/then/else would probably be more than 2 or 3 statements.
0

IT ConsultantCommented:
>> I think if/then/else would probably be more than 2 or 3 statements

I wrote that before I saw crysallus's comment. ;)
0

Commented:
if( a <= b ){
if( b <= c ){
return b;
}else if( c <= a ){
return a;
}else{
return c;
}
}else{/* a > b */
if( b > c ){
return b;
}else if( c > a ){
return a;
}else{
return c;
}
}

0

Commented:
int getMedian(int a, int b, int c)
{
if (a <= b && b <= c || c <= b && b <= a)
return b;
if ( (a+c <= b) ^ ( a<=c ) )
return a;
/* if (a <= c && c <= b || b <= c && c <= a) */
return c;
}

0

Commented:
Here is an approach that conditionally swaps two values using a trick XOR swap approach
http://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesXOR
``````int getMedian4(int a, int b, int c)
{
if( a > b ) a ^= b,   b ^= a,   a ^= b;
if( b > c ) c ^= b,   b ^= c,   c ^= b;
if( a > b ) a ^= b,   b ^= a,   a ^= b;
return b;
}
``````
OUTPUT:
2 2 2 2 2 2 2 1 1 0x74000000
2 2 2 2 2 2 2 1 1 0x74000000
2 2 2 2 2 2 2 1 1 0x7f000000
2 2 2 2 2 2 2 1 1 0x74000000
There is one assumption in getMedian3 that a + b will not overflow. The overflow explains why one result is different.

``````int getMedian1(int a, int b, int c);
int getMedian2(int a, int b, int c);
int getMedian3(int a, int b, int c);
int getMedian4(int a, int b, int c);

void foo( int (*getMed)(int, int, int) ) {
printf("%d %d %d %d %d %d %d %d %d %#0x\n",
getMed(1,2,3),
getMed(1,3,2),
getMed(2,1,3),
getMed(2,3,1),
getMed(3,1,2),
getMed(3,2,1),
getMed(3,2,2),
getMed(1,1,2),
getMed(1,2,1),
getMed(0x7F000000,2,0x74000000)
);
}

int main() {
foo( getMedian1 );
foo( getMedian2 );
foo( getMedian3 );
foo( getMedian4 );
}

int getMedian1(int a, int b, int c)
{
if (a <= b && b <= c || c <= b && b <= a)
return b;
if (b <= a && a <= c || c <= a && a <= b)
return a;
if (a <= c && c <= b || b <= c && c <= a)
return c;
}

int getMedian2(int a, int b, int c)
{
if( a <= b ){
if( b <= c ){
return b;
}else if( c <= a ){
return a;
}else{
return c;
}
}else{/* a > b */
if( b > c ){
return b;
}else if( c > a ){
return a;
}else{
return c;
}
}
}

int getMedian3(int a, int b, int c)
{
if (a <= b && b <= c || c <= b && b <= a)
return b;
if ( (a+c <= b) ^ ( a<=c ) )
return a;
// if (a <= c && c <= b || b <= c && c <= a) */
return c;
}
``````
0

Commented:
Again using the swap approach, but this time by using a tmp variable, the speed may actually be faster since the tmp variable very likely will be optimized into a register:
``````#define SWAP2int(x,y) { register int tmp = x; x = y; y = tmp; }
int getMedian5(int a, int b, int c)
{
if( a > b ) SWAP2int(a,b); // Note: the trailing ; is superflous, but nice to have, especially for maintenance reasons
if( b > c ) SWAP2int(b,c);
if( a > b ) SWAP2int(a,b);
return b;
}
``````
0

Commented:
For C++ code, the getMedian functions could be made inline so as to try to avoid the overhead of passing in the three int arguments. Here, I've also converted the SWAP to an inline function as well:
``````inline void SWAP2int(int &x, int &y) { register int tmp = x; x = y; y = tmp; }
inline int getMedian5(int a, int b, int c)
{
if( a > b )
SWAP2int(a,b);
if( b > c )
SWAP2int(b,c);
if( a > b )
SWAP2int(a,b);
return b;
}
``````
0

Commented:
or like that:

``````int maximum(int a, int b, int c)
{
return a >= b && a >= c ? a
: b >= c ? b
: c;
}

int minimum(int a, int b, int c)
{
return -maximum(-a, -b, -c);
}

int median(int a, int b, int c)
{
return a+b+c - maximum(a,b,c) - minimum(a,b,c);
}
``````

(no overflow considered).

to make it speedy you could use inline code or macros instead of functions.

Sara
0

Commented:
I can do this in one line:

``````#include <algorithm>

int getMedian(int a, int b, int c)
{
return std::sort(&a, &a+3),b;
}
``````

However, I certainly wouldn't ever use this code in production - it makes too many evil assumptions about the stack and the processor architecture. (And it breaks if the code is inlined.)

The point I am making with this example is that I think that l4zarus has given conflicting requirements. He said, "I don't want to do this by putting them in an array and sorting them." However, as this example shows, making a function call involves copying all of the variables to the stack, which is the same thing as copying them all to an array!
0

Commented:
Jim,
In http:#35146446 by using inline, the 3 args are not pushed onto the stack (as long as the compiler takes the hint).
0

Commented:
@phoffric - yes, absolutely. That's why I warned that it breaks if inlined. Thanks for clarifying that.
0

Commented:
>  (a+c <= b) ^ ( a<=c )
should have been
((a+c)/2 <= b) ^ ( a<=c )
or just
( a <= b) ^ ( a<=c )
sorry.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.