アルゴリ後半戦

勉強

後半戦ー。
mzpのやってないk番目のアルゴリズムを文章に書き直してみる。

集合 S の k 番目に小さい要素を求める

  1. |S|==1 ならば S の要素を返す。(再帰終了)
  2. Sを5個ずつのグループに分ける。(端数も1グループ)
  3. 各グループの中央値を取り、この集合をMとする。
  4. 集合 M の (|M|+1)/2 番目に小さい要素(要は中央値)を求め、これをxとする。(再帰潜り１)
  5. x より小さい要素の集合を A とする。
  6. x より大きい要素の集合を B とする。
  7. |A|==k-1 ならば、 x が k 番目の要素なので、それを返す。
  8. |A|>=k ならば、k 番目の要素は A の中にあるので、 A の k 番目に小さい要素を求め、それを返す(再帰終了)
  9. それ以外ならば、 k 番目の要素は B の中にあるので、B の k-|A|-1番目の要素を求め、それを返す(再帰終了)

このアルゴリズムの分かりづらいところは、中央値を求めるのにも自分自身のアルゴリズムを使用している点だ。この辺を踏まえてコードを書いてみる。
Sはsubstring的な、全体要素とその範囲を覚えているクラスと思いねぇ。

S::element select_kth_element(S s, int k){
  if(S.size()==1) return S[0];
  S M(); // 空集合。
  int i;
  for(i=0; i<s.size()-5; i+=5){
    S m(s,i+0,i+4); // s[i]からs[i+4]までの部分集合。
    M.insert( select_kth_element(m,3) ); //中央値をMに追加。5つ要素の3番目だから。
  }
  //端数処理。
  S m(s,i,s.size()-1);
  M.insert( select_kth_element(m,s.(size()-i)/2) ); //

  S:element x = select_kth_element(M, (M.size()+1)/2 ); // xはMの中央値。
  S A,B;
  for(int i=0; i<s.size(); i++){
    if(s[i]<x) A.insert(s[i]);
    if(s[i]>x) B.insert(s[i]);
  }
  if(A.size()==k-1) return x;
  if(A.size()>=k) return select_kth_element(A,k);
  else            return select_kth_element(B,k-1-A.size());
}

うわー、まんどくせ……。