は、5つの要素

Question

次の質問の中央値は中央値を見つけるために必要とされているどのように多くの最小の比較サイズ5 の未ソート配列を考えると、最近のMicrosoftのインタビュー

に頼まれた知見？彼はそれをサイズnのために拡張しました。私に係る5つの要素のための

溶液を6

1) use 3 comparisons to arrange elements in array such that a[1]<a[2] , a[4]<a[5] and a[1]<a[4] 
a) compare a[1] and a[2] and swap if necessary 
b) compare a[4] and a[5] and swap if necessary 
c) compare a[1] and a[4].if a[4] is smaller than a[1] , then swap a[1] wid a[4] and a[2] wid a[5] 
2)if a[3]>a[2].if a[2]<a[4] median value = min(a[3],a[4]) else median value=min(a[2],a[5]) 
3)if a[3]<a[2].if a[3]>a[4] median value = min(a[3],a[5]) else median value=min(a[2],a[4]) 

が、これはn個の要素に拡張することが可能です。 O（n）のn個の要素の中でどのようにメディアンを求めることができないのであれば、

Answer 1

選択アルゴリズムはリストを5つの要素のグループに分割します。 （要素の上左が今では無視されている）、そして、5の各グループに対して、中央値は、（ - 6つの比較分5つの値をレジスタにロードし、比較することができるならば、潜在的に非常に高速に行うことができる操作）が算出されます。次に、Selectをn/5要素のこのサブリストで再帰的に呼び出すことで、真の中央値を見つけることができます。