正答1
解説
正解は1です。
流れ図は、外側のループでiを1からn－1まで1ずつ増やし、内側のループでjをi＋1からnまで動かします。
内側のループでは、x(j)とx(k)を比較するα印の処理で、これまでの最大値の位置kを更新します。
内側のループが終わると、x(k)とx(i)を交換して、i番目に最大値を置きます。
α印の比較は、内側のループの1回の繰返しにつき1回実行されます。
【計算】
i＝1のとき、jは2からnまでなので、比較はn－1回です。
i＝2のとき、jは3からnまでなので、比較はn－2回です。
i＝n－1のとき、jはnだけなので、比較は1回です。
合計は(n－1)＋(n－2)＋…＋1＝n(n－1)／2回です。
【選択肢別解説】
1：○ 比較回数は1からn－1までの和で、n(n－1)／2回になります。
2：× n(n－1)は正しい回数の2倍です。
jがi＋1から始まるので、すでに整列済みの要素とは比較しません。
3：× n(n＋1)／2は1からnまでの和です。
外側のループはn－1回で終わるので、回数が多すぎます。
4：× n(n＋1)は1からnまでの和の2倍で、ループの回数と合いません。
【ポイント】
選択ソートの比較回数は、データの並び方に関係なく常にn(n－1)／2回です。
計算量はO(n²)で、バブルソートの比較回数と同じ式になります。