中央値乱択アルゴリズム

O(n)のはず。
結構昔に作ったものだけど、ブログにメモとして載せとく。
確か、アルゴリズムデザインって本を参照したはず。

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

int select(vector<int> S, int k) {
  int n = S.size();
  int i = rand() % n; // n/2;
  vector<int> R, T;
  for (int j = 0; j < n; j++) {
    if (S[j] < S[i]) R.push_back(S[j]);
    else if (S[j] > S[i]) T.push_back(S[j]);
  }
  if (R.size() > k) return select(R, k);
  else if (n-T.size() <= k) return select(T, k-n+T.size());
  else return S[i];
}

int main() {
  srand(time(NULL));
  int a[] = {2,1,3,0,4,3,1};
  vector<int> S;
  for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++) {
    S.push_back(a[i]);
  }
  for (int i = 0; i < S.size(); i++) {
    cout << i+1 << "th value : " << select(S, i) << endl;
  }
  cout << "median : " << select(S, S.size()/2) << endl;
  return 0;
}

中央値というか、n番目の数値を乱択で求めるアルゴリズムだけど。
ま、でも、アルゴリズム本のクイックソート扱った後の練習問題でよく、「O(n)の中央値選択アルゴリズムを示せ」とか書いてあるから、それの答えってことで。