最小数比較の3つの数字の中央値を見つける

Question

私はquicksortを実装していました、私はピボットを中央値または3つの数字に設定したいと思いました。 3つの数字は最初の要素、中間の要素、最後の要素です。

おそらく中央値がそれほど大きくないことがありますか。比較の？

median(int a[], int p, int r) 
{ 
    int m = (p+r)/2; 
    if(a[p] < a[m]) 
    { 
     if(a[p] >= a[r]) 
      return a[p]; 
     else if(a[m] < a[r]) 
      return a[m]; 
    } 
    else 
    { 
     if(a[p] < a[r]) 
      return a[p]; 
     else if(a[m] >= a[r]) 
      return a[m]; 
    } 
    return a[r]; 
} 

Answer 1

あなたは1つで行うことはできません。あなたは2つまたは3つのみを使用しているので、すでに比較の最小数があると思います。

Answer 2

中央値を計算するだけでなく、それらを適切な位置に配置することもできます。それからあなたは3つの比較だけでいつでも離れていくことができます。あなたは、コンパイラ組み込み関数を持つ手が少し汚れてもらうことを恐れていない場合

T median(T a[], int low, int high) 
{ 
    int middle = (low + high)/2; 
    if(a[ middle ].compareTo(a[ low ]) < 0) 
     swap(a, low, middle); 
    if(a[ high ].compareTo(a[ low ]) < 0) 
     swap(a, low, high); 
    if(a[ high ].compareTo(a[ middle ]) < 0) 
     swap(a, middle, high); 

    return a[middle]; 
} 

Answer 3

あなたは正確に0枝でそれを行うことができます。

同じ質問をする前に議論された：
Fastest way of finding the middle value of a triple?

けれども、私は中央値を求める際の枝の量を減らし、多くの要素で、クイックソートのナイーブな実装のコンテキストでそれを追加する必要がありますピボットの周りに要素を投げ始めるときに、分岐予測子がいずれの方法でもチョークするので、あまり重要ではありません。より洗練された実装（パーティション操作に枝分かれせず、WAWハザードを回避する）は、これにより大きな利益を得ます。

Answer 4

6つの可能な置換（低い、中央値、高い）の注意深い分析を使用して、中央値要素を3つから分離する巧妙な方法が実際にあります。 Pythonの場合：

半分の時間を2回比較すると、3回（平均2.5）になります。必要なときにメディアン要素を交換するのは1回だけです（時間の2/3）。これを使用して

完全なPythonのクイックソートで：

https://github.com/mckoss/labs/blob/master/qs.py

Answer 5

あなたはすべての順列を書き込むことができます。

1 0 2 
    1 2 0 
    0 1 2 
    2 1 0 
    0 2 1 
    2 0 1 

その後、我々は1の位置を見つけたいです。最初の比較で最初の2行など、同じ位置のグループを分割できる場合は、2つの比較でこれを実行できます。

問題は、最初の2行が利用可能な比較で異なります：a<b、a<c、b<cです。したがって、最悪の場合に3回の比較が必要な順列を完全に識別しなければなりません。

Answer 6

懸念事項が比較だけの場合は、これを使用する必要があります。

int getMedian(int a, int b , int c) { 
    int x = a-b; 
    int y = b-c; 
    int z = a-c; 
    if(x*y > 0) return b; 
    if(x*z > 0) return c; 
    return a; 
} 

Answer 7

int32_t FindMedian(const int n1, const int n2, const int n3) { 
    auto _min = min(n1, min(n2, n3)); 
    auto _max = max(n1, max(n2, n3)); 
    return (n1 + n2 + n3) - _min - _max; 
} 

Answer 8

私は、これは古いスレッドであることを知っているが、私は非常に少ないRAMを持っており、（:)）H/W乗算部を持たないマイクロコントローラ上で、まさにこの問題を解決しなければなりませんでした。最後に、私は次の作品をよく見つけました：

static char medianIndex[] = { 1, 1, 2, 0, 0, 2, 1, 1 }; 

signed short getMedian(const signed short num[]) 
{ 
    return num[medianIndex[(num[0] > num[1]) << 2 | (num[1] > num[2]) << 1 | (num[0] > num[2])]]; 
}