プログラミングの基礎(擬似言語のトレース)
次の手続 bubble は、整数型の配列 data を昇順に並べ替えるバブルソートである。swap(data, j, k) は data[j] と data[k] の値を入れ替える手続で、配列の要素番号は1から始まる。プログラム中の【a】に入れる字句はどれか。
○bubble(整数型の配列: data)
整数型: n ← dataの要素数
for (i を n から 2 まで 1 ずつ減らす)
for (j を 1 から 【a】 まで 1 ずつ増やす)
if (data[j] > data[j + 1])
swap(data, j, j + 1)
endif
endfor
endfor- Ai
- Bn − i
- Ci − 1
答えと解説を見る
正解：C. i − 1
外側の i は、その回の走査で最大値を送り込む位置(末尾から n、n − 1、…、2)を表します。内側では data[j] と data[j + 1] を比べるので、j の終値を i − 1 にすると data[i] までの隣どうしを比べ、配列の範囲を超えません。i = n の1回目で最大値が data[n] に移り、次は data[n − 1] までというように、走査する範囲が1つずつ狭まります。【a】を i にすると、1回目に data[n + 1] を参照してしまいます。
- A. i = n のとき j = n で data[n + 1] を参照し、配列の範囲を超えます。
- B. i = n のとき j の終値が0になって何も比べないなど、走査の範囲が逆になり、正しく並びません。{5, 3, 8, 1, 4} は {3, 5, 1, 8, 4} になります。
- C. 正しい。data[i] までの隣どうしを比べ、最大値を data[i] へ送ります。