ランダム化された選択の反復バージョンは何をしますか？

Question

私は、無作為化・セレクトオンラインの反復バージョンのコードが見つかりました：

RANDOMIZED-SELECT(A,p,r,i) 
    while p < r do 
     q ← RANDOMIZED-PARTITION(A,p,r) 
     k ← q – p +1 

     if i ≤ k then 
      r ← q 
     else 
      p ← q + 1 
      i ← i – k 

    return p 

誰かが最後まで私< = kの場合からのコードの一部が何を私に説明することができれば、私はそれを本当に感謝でしょうか？再帰版とは何が違うのですか？

Answer 1

pおよびrは、番目の要素を検索するAの範囲の左右のインデックスです。最初のパーティション分割の後、2つのパーティションのそれぞれにいくつの要素があるかをチェックします。左側のパーティションにi個以上の要素がある場合は（kと表示されます）、そこで検索を続ける必要があります。その場合は、範囲の右端（r）をパーティション（q）。そうでない場合は、探している要素が正しいパーティションのどこかにあるため、範囲の左端（p）を分割の右側の要素（q + 1）に設定する必要があります。範囲今度は右にシフトしたので、それに合わせてiを調整する必要があります（最初の8番目の要素を探していて、左側のパーティションに3つの要素がある場合は、右側のパーティションの5番目の要素を検索する必要があります）。

インデックスのこの調整は、再帰バージョンでも実行する必要がありますが、通常は再帰呼び出しで行われるため、後者の場合はRANDOMIZED-SELECT(A, q + 1, r, i - k)のようになります。