| Edit this page | Report an issue |
forループの中で、どのような操作を行うのかを考える。
if(p > a[i]) then b := b + 1 とあることから、forループ終了後の b はピボット p よりも小さい要素の個数を表す。これと、ループの次の行に swap(a,l,b) があることから、forループ終了直後の配列の状態は、
[ Pivot (p) ] [ pより小さいの要素の配列 ] [ p以上の要素の配列 ]
| Pivot (p) | pより小さいの要素の配列 | p以上の要素の配列 |
|---|---|---|
| (長さb) |
となる必要がある。
この条件を満たすような swap(a,A,B) を考えると、A = b, B = i が得られる。
自分で例を作ってアルゴリズムを理解しようとすると、分かりにくい例を選んでしまって時間がかかる場合がある。問題文で入力例が与えられている場合は、必ずその例で考えるようにすること。
各10点、50点満点
コメントはGithubレポジトリにIssueとして投稿されます。