Finding two minimum values out of four?

Question

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.

Answer 1

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.

Answer 2

Just write a loop and keep track of the lowes 2 values ? Should be at max O(2N) which is i think the best achievable complexity.

Answer 3

The most efficient way? Trying to avoid any extra steps, I got this (in pseudo-code). This will avoid any unnecessary comparisons that you'll get with other more general solutions (specifically ones that don't advantage of the transitive nature of comparison operations).

Bear in mind that this is only thinking about efficiency, not at all aiming for beautiful code.

if a<=b:
  if b<=c:
    # c too big, which of b and d is smaller?
    if b<=d:
      return (a,b)
    else:
      return (a,d)
  else if b<=d:
    # a and c both < b, and b < d
    return (a,c)
  else:
    # b is > a, c and d. Down to just those three.
    if a<=c:
      if c<=d:
        # a < c < d
        return (a,c)
      else:
        # a and d both < c
        return (a,d)
    else if d<=a:
      # Both c and d < a
      return (c,d)
    else:
      # c < a < d
      return (a,c)
else:
  # b < a
  if a<=c:
    # c too big, which of a and d is smaller?
    if a<=d:
      return (a,b)
    else:
      return (b,d)
  else if a<=d:
    # b and c both < a, and a < d
    return (b,c)
  else:
    # a is > b, c and d. Down to just those three.
    if b<=c:
      if c<=d:
        # b < c < d
        return (b,c)
      else:
        # b and d both < c
        return (b,d)
    else if d<=b:
      # Both c and d < b
      return (c,d)
    else:
      # c < b < d
      return (b,c)

I think this has a worst case of 5 comparisons and a best case of 3 (obviously there's no way of doing it in less than 3 comparison).

Answer 4

You can get away with exactly 4 comparisons and maximally 4 swaps.

inline void swap(int* i, int* j) {
  static int buffer;
  buffer = *j;
  *j = *i;
  *i = buffer;
}

inline void sort2(int* a, int* s) {
  if (*s < a[1])
    swap(s,a+1);
  if (*s < a[0]) // it is NOT sufficient to say "else if" here
    swap(s,a);
}

inline void sort4(int* a) {
  sort2(a,a+2);
  sort2(a,a+3);
}

The result will be sitting the the first to cells, but note that these cells are not necessarily sorted! They're just the smallest elements.

Answer 5

I would make an array out of them, sort and take the first two values.