| 基本情報技術者試験 |
2002年度 ＝ 平成14年度・春期 |
午前 |
問13 |
次の流れ図は、最大値選択法によって値を大きい順に整列するものである。＊印の処理（比較）が実行される回数を表す式はどれか。
ア n － 1
|
n（n － 1）
イ ──────
2
|
n（n ＋ 1）
ウ ──────
2
|
エ n2
|
イ
本アルゴリズムは、＜交換＞ループの中に＜最大値＞ループが入っている２重のループ構造となっています。問われている＊印の処理は、内側の＜最大値＞ループが繰り返されるたびに1回ずつ実行されます。
＜交換＞ループでは、i の値が1からn - 1まで増えていきますので、内側の＜最大値＞ループが実行される回数は次のようになります。
- i = 1のとき … n - 1回
- i = 2のとき … n - 2回
- （中略）
- i = n - 2のとき … 2回
- i = n - 1のとき … 1回
したがって、合計回数は次のようになります。
1 + 2 + … + (n - 2) + (n - 1) = n (n - 1) / 2
