Geek asks and answers

Conclusion of two minimum values ​​from four?

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

Edit: I need a fixed implementation for the sake of efficiency, since this is a very important operation that will be performed thousands of times.

+5
source share
7 answers

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

It takes only 5 comparisons and up to 5 swaps. You can simply ignore the results for p2, p3.

, Sort2 .

+5

lowes 2? max O (2N), , , .

+3

? - , ( ). , ( , , ).

, , .

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)

, 5 3 (, 3 ).

+3

4 4 .

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

, , ! .

+3

, .

+2

4 :

  • a1, a2
  • a3, a4
  • a1 >= a4 return (a3, a4)
  • ( , a1 < a4)
  • a3 >= a2 return (a1, a2)
  • ( , a3 < a2)
  • return (a1, a3)

, , :

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

(a2, a3) (a2, a4)

(a3, a4)

+2
source

I think you can sort the array and select the first two elements.

0
source

More articles:


All Articles