scratch@tc: 中央値を求めるアルゴリズム

基本というか、簡単に考えられるのは、 - ソートしたのち、真ん中の要素を選択する という方法だが、全ての要素をソートしないと答えが得られないというのは少し計算量が大きすぎる。 いろいろ調べてみると、クイックソートのアルゴリズムの発展型で、クイックセレクトなるアルゴリズムがあるらしい。 http://d.hatena.ne.jp/agw/20090505/1241602074 http://d.hatena.ne.jp/agw/20090513/1242290109 要するに、中央値が求まるくらいまでクイックソートを計算し、省略できる計算はしないということのようである。 このときに、クイックソートを計算するにあたり、最初に選択するパーティションの値をできるだけ中央値に近い値を選択するのが、アルゴリズムを高速化するコツであるということが書いてある。 http://d.hatena.ne.jp/