修了試験 2012-07-22実施分 基本情報技術者試験 問6

解説

正解は1です。 このアルゴリズムは、隣り合う要素を比べて小さい方を前へ移すバブルソート（交換法）です。 行2〜3が初めて終了するのは、i＝1のときの処理が終わった時点です。 i＝1では、jをnから2まで減らしながら、A[j]とA[j－1]を比べます。 A[j]の方が小さければ交換するので、小さい値ほど前へ運ばれます。 最小値は、どこにあっても見つかった位置からA[1]まで運ばれます。 【処理の流れ】 例としてn＝3、A＝(3，1，2)で考えます。 j＝3のとき、A[3]＝2＜A[2]＝1は偽なので、交換しません。 j＝2のとき、A[2]＝1＜A[1]＝3は真なので交換し、A＝(1，3，2)になります。 A[1]には最小値の1が入っています。 【選択肢別解説】 1：○ 後ろから前へ比較と交換を繰り返すと、最小値がA[1]まで運ばれます。 どのような初期配列でも、i＝1の処理が終わればA[1]は必ず最小値になります。 2：× 交換条件はA[j]＜A[j－1]で、小さい値を前へ送る処理です。 A[1]に入るのは最大値ではなく最小値です。 3：× 最小値はA[1]まで運ばれるので、A[n]が最小値になることはありません。 小さい値は後ろではなく前に集まります。 4：× 1回目の走査で最大値がA[n]に来る保証はありません。 上の例では、終了時にA＝(1，3，2)となり、A[3]は最大値ではありません。 【ポイント】 後ろから前へ走査するバブルソートでは、1回の走査ごとに未整列部分の最小値が先頭側に確定します。 走査の向きと交換条件から、どちらの端に何が確定するかを判断しましょう。