calgorithm

Finding two minimum values out of four?


So, I have four integers and I need to find out the lowest two out of those four. What would be the most efficient way of doing so in C (or any other language)?

Edit: I need a fixed implementation, for the sake of efficiency as this is a very critical operation that is going to be performed thousands of times.


Solution

  • Here's an efficient implementation using sorting networks:

    inline void Sort2(int *p0, int *p1)
    {
        if (*p0 > *p1)
        {
            const int temp = *p0;
            *p0 = *p1;
            *p1 = temp;
        }
    }
    
    inline void Sort4(int *p0, int *p1, int *p2, int *p3)
    {
        Sort2(p0, p1);
        Sort2(p2, p3);
        Sort2(p0, p2);  
        Sort2(p1, p3);  
        Sort2(p1, p2);  
    }
    

    This takes only 5 compares and up to 5 swaps. You can just ignore the results for p2, p3.

    Note that for a performance-critical application Sort2 can be implemented without branches in one or two instructions on some architectures.