Reputation: 16325

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.

Upvotes: 4

Answers (8)

RARE Kpop Manifesto

Reputation: 2845

Instead of a, b, c, d, I usually like variables that have no letters in them when it comes to sorting :

function sort4(_1_, _2_, _3_, _4_, _) {

    _1_ <= (_ = _2_) || (_2_ = _1_) (_1_ = _)
    _3_ <= (_ = _4_) || (_4_ = _3_) (_3_ = _)

    return   _2_ <= _3_ ? (_1_)_2_   (_3_)_4_  \
          :  _4_ <= _1_ ? (_3_)_4_   (_1_)_2_  \
          : (_1_ <= _3_ ? (_1_)_3_ : (_3_)_1_) \
            (_2_ <= _4_ ? (_2_)_4_ : (_4_)_2_)
}

So here's my polymorphic sort4() function - best case 3 compares worst case 6 compares, but returns the 4 items fully sorted instead of just lower half.

All swaps are done in-function, and by leveraging the ternary -?-:- operator, only half the swaps are actually performed.

Using underscores this way creates a visual buffer between variables, so they never appear clumped together.

A side bonus of this unconventional variable naming system is that it makes the output order almost self-explanatory, since variable names provide rank ordering information without being polluted by alphabetical prefixes (e.g. a0, a1, a2, a3 - the a prefixes increase visual clutter while providing no extra information not already conveyed by the digits themselves)

e.g. if the input were pre-sorted, then the output order is simply
(_1_)_2_ (_3_)_4_

Similarly, if one were to make a sort4_reverse() function in this same styling, then the pre-sorted output order to be

(_4_)_3_ (_2_)_1_

We're rank-ordering here, not attempting to perform an array access, so it's more apt to use 1-4 instead of 0-3

Upvotes: -3

bitmask

Reputation: 34636

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.

Upvotes: 2

Avi Cohen

Reputation: 3414

You can accomplish it with at most 4 comparisons:

compare the first pair of numbers and let the smaller be a1 and the larger be a2
compare the second pair of numbers and let the smaller be a3 and the larger be a4
if a1 >= a4 return (a3, a4)
(now we know that that a1 < a4)
if a3 >= a2 return (a1, a2)
(now we also know that a3 < a2)
return (a1, a3)

To see that this is true, you can check all the combinations of possible returns:

(a1, a2) (a1, a3) (a1, a4)

(a2, a3) (a2, a4)

(a3, a4)

Upvotes: 2

Paul R

Reputation: 213029

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.

Upvotes: 4

hcarver

Reputation: 7214

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).

Upvotes: 2