隣どうしの比較と交換（1巡）（標準）　問題01

標準レベル：基礎　／　このアルゴリズムの解説を読む

練習モードは行番号つきで順に解く形式、本番形式は公開問題と同じ体裁の1問です。

関数 onePass は、配列 data の隣り合う要素を先頭から順に比べ、左が大きければ入れ替える。配列の要素番号は 1 から始まる。

次のプログラムを onePass({7, 2, 3, 9}) で呼び出す。

〔プログラム〕

1	○整数型の配列: onePass(整数型の配列: data)
2	整数型: j, tmp
3	for (j を 1 から dataの要素数－ 1 まで 1 ずつ増やす)
4	if (［　ａ　］)
5	tmp ← data[j]
6	data[j] ← data[j ＋ 1]
7	data[j ＋ 1] ← tmp
8	endif
9	endfor
10	return data

ヒント1：トレース表の枠を見る

この列で表を作り、文を1つ実行するたびに1行足していきます。

#	行	したこと	data	j	tmp

ヒント2：最初の4ステップを見る

続きを同じ要領で書いていきます。太字は、その文で値が変わった変数です。

#	行	したこと	data	j	tmp
1	2	宣言	{7, 2, 3, 9}	未設定	未設定
2	3	繰返しの初期化	{7, 2, 3, 9}	1	未設定
3	3	条件判定（真）	{7, 2, 3, 9}	1	未設定
4	4	条件判定（真）	{7, 2, 3, 9}	1	未設定

設問1

onePass({7, 2, 3, 9}) を呼び出すと戻り値は {2, 3, 7, 9} になる。プログラム中の［　ａ　］に入れる正しい答えはどれか。

解答群ア　data[j] ≠ data[j ＋ 1] イ　j > data[j ＋ 1] ウ　data[j] > data[j ＋ 1] エ　data[j] > data[j － 1]

正解：ウ　data[j] > data[j ＋ 1]

それぞれの選択肢を空欄に入れて、実際に動かした結果は次のとおりです。
「data[j] ≠ data[j ＋ 1]」→ 戻り値は {2, 3, 9, 7}
「j > data[j ＋ 1]」→ 戻り値は {7, 2, 3, 9}
「data[j] > data[j ＋ 1]」→ 戻り値は {2, 3, 7, 9}（正解）
「data[j] > data[j － 1]」→ 途中で止まる（配列の範囲外です（要素番号 0、要素数 4））

設問2

7行目を2回目に実行した直後の、変数 data の値はどれか。

解答群ア　{2, 7, 3, 9} イ　{2, 3, 7, 9} ウ　{3, 7, 9, 2} エ　{7, 2, 3, 9}

正解：イ　{2, 3, 7, 9}

7行目は全部で2回実行されます。
実行した直後の data は、順に {2, 7, 3, 9} → {2, 3, 7, 9} です。
2回目の直後なので、答えは {2, 3, 7, 9} です。

設問3

7行目が実行される回数はどれか。

解答群ア　1 イ　2 ウ　3 エ　4

正解：イ　2

7行目は2回実行されます。トレース表で 7行目の行を数えると確かめられます。

本番形式

問　次のプログラム中の［　ａ　］に入れる正しい答えを，解答群の中から選べ。

関数 onePass は，配列 data の隣り合う要素を先頭から順に比べ，左が大きければ入れ替える。配列の要素番号は 1 から始まる。

関数 onePass を onePass({7, 2, 3, 9}) として呼び出すと，戻り値は {2, 3, 7, 9} となる。

〔プログラム〕

○整数型の配列: onePass(整数型の配列: data)

整数型: j, tmp

for (j を 1 から dataの要素数－ 1 まで 1 ずつ増やす)

if (［　ａ　］)

tmp ← data[j]

data[j] ← data[j ＋ 1]

data[j ＋ 1] ← tmp

endif

endfor

return data

解答群

ア　data[j] > data[1] イ　data[j] > data[j ＋ 1] ウ　data[j ＋ 1] > data[j] エ　j > data[j ＋ 1] オ　data[j] < data[j ＋ 1] カ　data[j] ≠ data[j ＋ 1]

正解：イ　data[j] > data[j ＋ 1]

それぞれの選択肢を空欄に入れて，実際に動かした結果は次のとおりです。
「data[j] > data[1]」→ 戻り値は {7, 2, 3, 9}
「data[j] > data[j ＋ 1]」→ 戻り値は {2, 3, 7, 9}（正解）
「data[j ＋ 1] > data[j]」→ 戻り値は {7, 3, 9, 2}
「j > data[j ＋ 1]」→ 戻り値は {7, 2, 3, 9}
「data[j] < data[j ＋ 1]」→ 戻り値は {7, 3, 9, 2}
「data[j] ≠ data[j ＋ 1]」→ 戻り値は {2, 3, 9, 7}

解説

1巡すると、最も大きい要素が末尾まで運ばれます。それ以外の要素は、途中で入れ替わった分だけ動きます。

行番号つきのプログラム

1	○整数型の配列: onePass(整数型の配列: data)
2	整数型: j, tmp
3	for (j を 1 から dataの要素数－ 1 まで 1 ずつ増やす)
4	if (data[j] > data[j ＋ 1])
5	tmp ← data[j]
6	data[j] ← data[j ＋ 1]
7	data[j ＋ 1] ← tmp
8	endif
9	endfor
10	return data

トレース表（全ステップ）

太字は、その文で値が変わった変数です。設問が指している行は黄色、その回は濃い黄色、変数は青い列で示します。

#	行	したこと	data	j	tmp
1	2	宣言	{7, 2, 3, 9}	未設定	未設定
2	3	繰返しの初期化	{7, 2, 3, 9}	1	未設定
3	3	条件判定（真）	{7, 2, 3, 9}	1	未設定
4	4	条件判定（真）	{7, 2, 3, 9}	1	未設定
5	5	代入	{7, 2, 3, 9}	1	7
6	6	代入	{2, 2, 3, 9}	1	7
7	7	代入	{2, 7, 3, 9}	1	7
8	3	繰返しの更新	{2, 7, 3, 9}	2	7
9	3	条件判定（真）	{2, 7, 3, 9}	2	7
10	4	条件判定（真）	{2, 7, 3, 9}	2	7
11	5	代入	{2, 7, 3, 9}	2	7
12	6	代入	{2, 3, 3, 9}	2	7
13	7	代入	{2, 3, 7, 9}	2	7
14	3	繰返しの更新	{2, 3, 7, 9}	3	7
15	3	条件判定（真）	{2, 3, 7, 9}	3	7
16	4	条件判定（偽）	{2, 3, 7, 9}	3	7
17	3	繰返しの更新	{2, 3, 7, 9}	4	7
18	3	条件判定（偽）	{2, 3, 7, 9}	4	7
19	10	戻る（{2, 3, 7, 9}）	{2, 3, 7, 9}	4	7