flint blog: 「選択アルゴリズム」と「中央値の中央値」

ある小説の登場人物、あるいは、あるアーティストの曲といった集合について考えるとき、「それらの中で最も好きなものはどれですか?」という問いに答えることは (甲乙付け難くて悩むケースもあるかも知れませんが) 比較的簡単です。 しかし、「2番目に好きなものは?」「3番目に好きなものは?」...といった具合に質問を続けていくと、どんどん回答が困難になっていくはず。 最も嫌い (好きでない) ものについては、好きでないものと同じように簡単に答えられるので、最も特定が困難なのは、好きな (あるいは嫌いな) 順に並べたとき、そのシーケンスの中央に位置する要素だと言えるでしょう。 私はこれまで、プログラミングにおいてもこれと同様の問題が存在する、即ち、ある配列 (要素数n )について特定の指標に沿っての並べ替え (ソート) を行ったときに中央あるいはその付近に配置される要素を特定するには、ソートそのものと