C++中央値

Question

Ｃ＋＋で中央値を求めるやり方がわかりません。
前に計算で求めるやり方を習ったのですが忘れてしまって…
if文でたらたら書くのはできるのですが。
かっこよく短い式で求めたいです。

Comments

[yuba]

値の集合はどのように与えられる想定ですか？
配列やvector？ それとも、変数a, b, c, d, eのような形？

Answer 1

C++標準ライブラリで提供されるnth_elementアルゴリズムが使えます。

#include <algorithm>
#include <vector>
#include <iostream>

template <typename T>
T median(std::vector<T>& c)
{
    size_t n = c.size() / 2;
    std::nth_element(c.begin(), c.begin() + n, c.end());
    return c[n];
}

int main()
{
    std::vector<int> a = {8,2,4,1,9,6,7,3,5};
    std::cout << median(a) << std::endl;  // 5
}

Comments

[anniepin]

nth_elementは「先頭に、順不同でN個の最高品質な要素を集める」なので、
その後、前半部分に対してmin_elementを使う必要がありそうです。

[yohhoy]

???
see also http://stackoverflow.com/q/1719070/684921

追記：引用部はcpprefjpサイトを参照されたのでしょうか？概要説明をより具体的に改善してみました。
https://github.com/cpprefjp/site/blob/master/reference/algorithm/nth_element.md

[anniepin]

解説追記いただきありがとうございました。
cpprefjpサイトを見ましたが、min_elementについて誤った理解をしていました。
勉強になりました。

Answer 2

ソートする関数を利用することは必須のように思えます．
しかし，ソートしてから中央値を求めるやり方より高速に求めることは可能です．

例えばO(n2)の選択ソートを自作したとき，途中までソートを完了させれば中央値はわかります．
全部を選択ソートでソートしてから中央値を求めるより，約1/4の時間で終わらせることができます．

またO(nlogn)のクイックソートを自作したとき，ピボットより大きいグループと小さいグループのどちらかはソート不要になります．
例えば{3, 1, 4, 6, 2, 7, 5}という元データを考えます．
ピボットを先頭の3にしたとき，{1, 2}, {3}, {4, 6, 7, 5}という風に分割できます．
この時，ピボットの3より小さいグループの要素数は2，等しいグループの要素数は1，大きいグループの要素数は4です．
となると中央値は大きいグループの中に入っていることがわかります．
というより大きいグループの1番小さい要素が中央値だということがわかります．
となるとピボットより小さいグループ内のソートは不要になります．
明らかに骨の折れるプログラミングですが，所要時間はかなり減るはずです．

もしこのような高速な求め方を実装している人がすでにいるとしたら，それを使うべきではありませんか？
私のアイディアよりももっと速いやり方を先人たちは開発しています．
英文ですが，最後の方にコードが有りますので，拝借するのが良いと思います．
Fast median search: an ANSI C implementation
先人は偉大です．

Answer 3

「if文でたらたら」というのがよく分からないのですが、基本的にはデータ列をソートして平均値付近から実測値を取得する処理ですし、ここの緑のチェックが付いている回答のように書くのが妥当です。

これ以上短く書く理由がある場合は、それを書かないと求める回答を得られないように思うのですが…