9.3 最悪線形時間選択アルゴリズムで以下のようなアルゴリズムがあります
1.入力配列のn 個の要素をそれぞれ5 個の要素からなるLn/5J 個のグループと残りのnmod5
個の要素からなる高々1 個のグループに分割する.
各グループの(高々5 個の)要素を挿入ソートによってソートし,それぞれの中央値を
とることによって, n/5 個のグループのそれぞれの中央値を求める.SELECT を再帰的に用いてステップ2 で見つけた n/5 個の中央値の中央値x を見つける.
(中央値が偶数個の場合は,本書での約束にしたがって,小さい方の中央値をとるものと
する. )変更された版のPARTITION を用いて入力配列を中央値の中央値x をピボットとして分割す
る. k を分割の小さい方(x よりも小さい要素の集合)に属する要素数に1 を足したもの
とする.このとき, x はk 番目に小さい値であり,分割の大きい方にはn-k 個の要素が
属する.i=k ならば, x を返す.そうでなければ, SELECT を再帰的に用いて, i<=k ならば,分割
の小さい方からi 番目に小さい要素を見つけ, i>k ならば,分割の大きい方から(i -k)
番目に小さい要素を見つける.
このステップ3なのですが、本当に全体の中央値が取得できているのでしょうか?
再帰ステップを繰り返すうちに中央値が候補から弾かれてしまうという事はないのでしょうか?