分割されたセット S の要素数が k 番目に小さい数とどのように関係しているかを理解するのに苦労しています。次の疑似コードがあるとします。
Select (k,S)
if |S|=1 then return a in S
Choose random a in S
Let S1,S2,S3 be sets of elements in S (<,=,> to a)
If |S1|>=k then return Select(k,S1)
Else if |S1| + |S2| >= k then return a
Else return Select(k-|S1|-|S2|, S3)
私が知っていることから、k 番目に小さい要素を見つけるために、ピボットを選択し、ピボットの周りの数字を並べ替え、小さい数字はすべて左に、大きい数字はすべてピボットの右に配置します。次に、k 番目に小さい数を見つけたい場合は、それをピボットの位置と比較します。ピボットの位置が k より大きい場合は、ピボットの左側を調べ、ピボットの位置が k より小さい場合は、 、私は右に見て、そこから再帰します。
しかし、上記の疑似コードでは、上記のピボットと k の比較がどこで行われているのかわかりません。つまり、|S1| ではなく a >= k と比較すべきではないでしょうか。>= k、a がピボットなので?
この k との比較では、セット内の要素の数はどのように作用するのでしょうか?