CLRS 第 3 版のセクション 9.3「最悪の場合の線形時間での選択」では、O のリストの中央値を見つけるための「選択」アルゴリズム (Blum、Floyd、Pratt、Rivest、および Tarjan のために BFPRT アルゴリズムと呼ばれることもあります) について説明しています。 (n) 最悪の場合の時間。ホワイトボードでサンプルを実行しようとしたとき、少し混乱しました。「Select」の呼び出しごとに特定の数の要素を削除できることを理解しています（30％が削除され、70％が再度チェックされる必要があると読んだことがあります）、私が混乱したのは、配列のどの部分を削除できるかでしたつまり、配列が高さ 5、幅 n/5 の行列として視覚化されている場合、では、排除された要素はどの象限にあるのでしょうか? 元々は対角線上に隣接する 2 つの象限だと思っていましたが、中央値の中央値によっては 1 つの象限にすぎないと考えています (手順 5、6、および 7 を参照)。ここで）。
そこで、ウィキペディアに行って、CLRS よりも分析が少ない簡単な説明があるかどうかを確認しました (分析のために CLRS に戻る前にアルゴリズムを理解するため)。私はこれに行き着きました、特に「最終的に、「中央値の中央値」がピボットとして選択されました。」ウィキペディアの説明の音から、「選択」は、クイックソートのピボットを選択する目的で十分な中央値である要素ではなく、真の中央値を見つけません。
では、真の中央値に関して「選択」は何をし、どのように行うのでしょうか? その中で思いつくのが「部分階層」という言葉で、それが理由で「選択」が機能するのだと理解していますが、この部分階層を元にリストから要素を中央値から除外するにはどのような論理が必要なのでしょうか。