選択アルゴリズム

k番目の値を求める。(クエリが複数ある場合は以下の方法では効率が悪い。(e.g. POJ 2104 k-th Number))

アルゴリズム

• ソート

マージソート等の効率のよいソートの計算量はO(nlogn)であるから、O(logn)で求めることができる。
実装略

• パーティションベースの選択アルゴリズム

選択アルゴリズム - Wikipediaを見ると良い。クイックソートに似た方法で、値を求める。pivotをランダムに選ぶことで期待計算量をO(n)にすることができる。最悪計算量をO(n)にできることも知られている。

C++での実装(kは正しい値であると仮定している)

int parti(vector<int>& t, int l, int r, int ix){
	int p = t[ix];
	swap(t[ix], t[r]);
	int sx = l;
	for(int i = l; i < r; i++){
		if(t[i] <= p){
			swap(t[sx++], t[i]);
		}
	}
	swap(t[r], t[sx]);
	return sx;
}

int select(vector<int>& t, int k, int l, int r){ //[l,r] の範囲で求める。
	while(true){
		int ix = (l+r)/2;
		int inx = parti(t, l, r, ix);
		if(k == inx) return t[k];
		else if(k < inx) r = inx-1;
		else l = inx+1;
	}
}

比較

n = 1000000(1e+6)と、n = 64000000(64e+6)と、n = 512000000(512e+6)で計算時間を比較した(検証に用いた数列は標準ライブラリの線形合同法を用いた)。以下は、実行前後のclock()の差である。

n	ソート	パーティションベースの選択アルゴリズム
1000000	391	47
64000000	31483	2907
512000000	283406	15110

n = 1000000, 64000000の比較では、ソートの計算時間は約80.5倍、パーティションベースの選択アルゴリズムの計算時間は61.9倍となった。
n = 64000000, 512000000の比較では、それぞれ、9倍、5倍になった。