Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

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

Posted on 2011-03-15
13
Medium Priority
?
373 Views
Last Modified: 2012-05-11
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
Comment
Question by:l4zarus
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
  • 2
  • +3
13 Comments
 
LVL 8

Accepted Solution

by:
crysallus earned 500 total points
ID: 35143677
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;
}

Open in new window

0
 
LVL 33

Expert Comment

by:Todd Gerbert
ID: 35143720
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));
		Console.ReadKey();
	}

	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];

	}
}

Open in new window


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];
}

Open in new window


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

Expert Comment

by:Todd Gerbert
ID: 35143726
>> I think if/then/else would probably be more than 2 or 3 statements

I wrote that before I saw crysallus's comment. ;)
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 84

Expert Comment

by:ozo
ID: 35144107
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
 
LVL 84

Expert Comment

by:ozo
ID: 35144143
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
 
LVL 32

Expert Comment

by:phoffric
ID: 35146359
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;
}

Open in new window

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;
}

Open in new window

0
 
LVL 32

Expert Comment

by:phoffric
ID: 35146404
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;
}

Open in new window

0
 
LVL 32

Expert Comment

by:phoffric
ID: 35146446
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;
}

Open in new window

0
 
LVL 35

Expert Comment

by:sarabande
ID: 35146952
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);
}

Open in new window


(no overflow considered).

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

Sara
0
 
LVL 7

Expert Comment

by:JimBeveridge
ID: 35149486
I can do this in one line:

#include <algorithm>

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

Open in new window


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
 
LVL 32

Expert Comment

by:phoffric
ID: 35149593
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
 
LVL 7

Expert Comment

by:JimBeveridge
ID: 35149849
@phoffric - yes, absolutely. That's why I warned that it breaks if inlined. Thanks for clarifying that.
0
 
LVL 84

Expert Comment

by:ozo
ID: 35150863
>  (a+c <= b) ^ ( a<=c )
should have been
 ((a+c)/2 <= b) ^ ( a<=c )
or just
( a <= b) ^ ( a<=c )
sorry.
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article introduced a TextBox that supports transparent background.   Introduction TextBox is the most widely used control component in GUI design. Most GUI controls do not support transparent background and more or less do not have the…
Entity Framework is a powerful tool to help you interact with the DataBase but still doesn't help much when we have a Stored Procedure that returns more than one resultset. The solution takes some of out-of-the-box thinking; read on!
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

670 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question