c - 4 つのうち 2 つの最小値を見つけるには?

Question

つまり、4 つの整数があり、それら 4 つのうち最小の 2 つを見つける必要があります。C (または他の言語) で最も効率的な方法は何でしょうか?

編集:これは何千回も実行される非常に重要な操作であるため、効率のために固定実装が必要です。

score 5 · Accepted Answer

ソートネットワークを使用した効率的な実装を次に示します。

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

これには、5 回の比較と最大 5 回のスワップしか必要ありません。p2、p3 の結果は無視できます。

パフォーマンスが重要なアプリケーションのSort2場合、一部のアーキテクチャでは 1 つまたは 2 つの命令で分岐なしで実装できることに注意してください。

score 3 · Accepted Answer

ループを書いて、最低2つの値を追跡するだけですか? 最大 O(2N) にする必要があります。これは、達成可能な最高の複雑さだと思います。

score 3 · Accepted Answer

最も効率的な方法は？余分な手順を避けようとして、これを（疑似コードで）取得しました。これにより、他のより一般的なソリューション (特に、比較操作の推移的な性質を利用しないソリューション) で得られる不要な比較を回避できます。

これは効率だけを考えているだけで、美しいコードを目指しているわけではないことに注意してください。

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 回未満の比較では明らかに方法がありません)。

score 3 · Accepted Answer

正確に 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);
}

結果は最初にセルに座っていますが、これらのセルは必ずしもソートされていないことに注意してください! それらは最小の要素にすぎません。

score 2 · Accepted Answer

あなたは最大4つの比較でそれを達成することができます：

数字の最初のペアを比較し、小さい方を小さくa1、大きい方をa2
数値の2番目のペアを比較し、小さい方を小さくa3、大きい方をa4
a1> = a4の場合return（a3、a4）
（これで、a1 <a4であることがわかります）
a3> = a2の場合return（a1、a2）
（これで、a3 <a2であることもわかります）
戻り値（a1、a3）

これが正しいことを確認するために、可能なリターンのすべての組み合わせを確認できます。

（a1、a2）（a1、a3）（a1、a4）

（a2、a3）（a2、a4）

（a3、a4）

score 2 · Accepted Answer

2

それらから配列を作成し、ソートして最初の 2 つの値を取得します。

于 2012-08-31T11:51:09.863 に答える

score 0 · Accepted Answer

0

配列をソートして、最初の 2 つの要素を選択できると思います。

于 2012-08-31T11:51:17.867 に答える

c - 4 つのうち 2 つの最小値を見つけるには?

7 に答える 7

Related

Reference