基本情報技術者試験科目A免除修了試験 20110626 実施分問7

流れ図に従って，選択ソートによって値を大きい順に整列するとき，α印の処理（比較）が実行される回数を表す式はどれか。

流れ図（上から順）: 開始 → ループ始端「交換 i:1,1,n－1」 → 処理「i→k」 → ループ始端「最大値 j:i＋1,1,n」 → 判定「x(j):x(k)」（α印の矢印がこの判定を指す）。「≦」の場合はループ端「最大値」へ戻る。「＞」の場合は処理「j→k」を経てループ端へ。 → ループ終端「最大値」 → 処理「x(k)→w，x(i)→x(k)，w→x(i)」 → ループ終端「交換」 → 終了 (注) ループ端の繰返し指定は，変数名：初期値，増分，終値を示す。

答えを選ぶ

出典：基本情報技術者試験科目A免除修了試験 20110626 実施分問7（問題文は IPA の公開問題。解説は当サイト作成）

解説に誤りを見つけたら、解説の誤りを報告してください。

答えと解説を見る

正解：ア

覚える知識

選択ソートの比較回数

選択ソートの比較回数は、データ数nに対しn(n-1)/2回で、データの並びに依存しない。

この問題で必要なこと

i=1〜n-1でjがi+1〜nを回るため、比較回数は(n-1)+(n-2)+…+1=n(n-1)/2である。

ひっかけ

ループ範囲を誤ってn(n+1)/2やn(n-1)と数えることを誘う。