選択ソート　問題12

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

関数 sort は、配列 data を昇順に整列して返す。まだ整列していない部分から最小の要素を探し、その部分の先頭と入れ替えることを繰り返す。配列の要素番号は 1 から始まる。

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

〔プログラム〕

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

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

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

#	行	したこと	data	i	j	min	tmp

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

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

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

設問1

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

解答群ア　data[j] < data[min] イ　data[j] > data[min] ウ　data[j] < data[i] エ　data[j] < min

正解：ア　data[j] < data[min]

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

設問2

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

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

正解：ア　{1, 7, 6, 9, 2}

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

設問3

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

解答群ア　1 イ　3 ウ　4 エ　5

正解：ウ　4

7行目が実行されるのは、6行目の条件が真になったときだけです。
6行目の条件は10回評価され、真になるのは4回です。したがって 7行目は4回実行されます。

本番形式

問　次の記述中の［　ａ　］に入れる正しい答えを，解答群の中から選べ。

関数 sort は，配列 data を昇順に整列して返す。まだ整列していない部分から最小の要素を探し，その部分の先頭と入れ替えることを繰り返す。配列の要素番号は 1 から始まる。

関数 sort を sort({7, 1, 6, 9, 2}) として呼び出したとき，プログラム中の α の行を1回目に実行した直後の変数 data の値は［　ａ　］となる。

〔プログラム〕

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

整数型: i, j, min, tmp

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

min ← i

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

if (data[j] < data[min])

min ← j

endif

endfor

tmp ← data[i]

data[i] ← data[min]

data[min] ← tmp　/*** α ***/

endfor

return data

解答群

ア　{1, 7, 6, 9, 2} イ　{1, 6, 7, 9, 2} ウ　{7, 1, 6, 9, 2} エ　{1, 2, 6, 7, 9} オ　{2, 9, 6, 7, 1} カ　{1, 7, 9, 6, 2} キ　{1, 2, 6, 9, 7} ク　{1, 7, 6, 2, 9}

正解：ア　{1, 7, 6, 9, 2}

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

α の行は，下のトレース表（行番号つき）では 12 行目です。

解説

外側の繰返しの i 回目で、i 番目以降の最小の要素を探し、i 番目と入れ替えます。 1回終わるごとに、先頭から i 個が確定します。

行番号つきのプログラム

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

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

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

#	行	したこと	data	i	j	min	tmp
1	2	宣言	{7, 1, 6, 9, 2}	未設定	未設定	未設定	未設定
2	3	繰返しの初期化	{7, 1, 6, 9, 2}	1	未設定	未設定	未設定
3	3	条件判定（真）	{7, 1, 6, 9, 2}	1	未設定	未設定	未設定
4	4	代入	{7, 1, 6, 9, 2}	1	未設定	1	未設定
5	5	繰返しの初期化	{7, 1, 6, 9, 2}	1	2	1	未設定
6	5	条件判定（真）	{7, 1, 6, 9, 2}	1	2	1	未設定
7	6	条件判定（真）	{7, 1, 6, 9, 2}	1	2	1	未設定
8	7	代入	{7, 1, 6, 9, 2}	1	2	2	未設定
9	5	繰返しの更新	{7, 1, 6, 9, 2}	1	3	2	未設定
10	5	条件判定（真）	{7, 1, 6, 9, 2}	1	3	2	未設定
11	6	条件判定（偽）	{7, 1, 6, 9, 2}	1	3	2	未設定
12	5	繰返しの更新	{7, 1, 6, 9, 2}	1	4	2	未設定
13	5	条件判定（真）	{7, 1, 6, 9, 2}	1	4	2	未設定
14	6	条件判定（偽）	{7, 1, 6, 9, 2}	1	4	2	未設定
15	5	繰返しの更新	{7, 1, 6, 9, 2}	1	5	2	未設定
16	5	条件判定（真）	{7, 1, 6, 9, 2}	1	5	2	未設定
17	6	条件判定（偽）	{7, 1, 6, 9, 2}	1	5	2	未設定
18	5	繰返しの更新	{7, 1, 6, 9, 2}	1	6	2	未設定
19	5	条件判定（偽）	{7, 1, 6, 9, 2}	1	6	2	未設定
20	10	代入	{7, 1, 6, 9, 2}	1	6	2	7
21	11	代入	{1, 1, 6, 9, 2}	1	6	2	7
22	12	代入	{1, 7, 6, 9, 2}	1	6	2	7
23	3	繰返しの更新	{1, 7, 6, 9, 2}	2	6	2	7
24	3	条件判定（真）	{1, 7, 6, 9, 2}	2	6	2	7
25	4	代入	{1, 7, 6, 9, 2}	2	6	2	7
26	5	繰返しの初期化	{1, 7, 6, 9, 2}	2	3	2	7
27	5	条件判定（真）	{1, 7, 6, 9, 2}	2	3	2	7
28	6	条件判定（真）	{1, 7, 6, 9, 2}	2	3	2	7
29	7	代入	{1, 7, 6, 9, 2}	2	3	3	7
30	5	繰返しの更新	{1, 7, 6, 9, 2}	2	4	3	7
31	5	条件判定（真）	{1, 7, 6, 9, 2}	2	4	3	7
32	6	条件判定（偽）	{1, 7, 6, 9, 2}	2	4	3	7
33	5	繰返しの更新	{1, 7, 6, 9, 2}	2	5	3	7
34	5	条件判定（真）	{1, 7, 6, 9, 2}	2	5	3	7
35	6	条件判定（真）	{1, 7, 6, 9, 2}	2	5	3	7
36	7	代入	{1, 7, 6, 9, 2}	2	5	5	7
37	5	繰返しの更新	{1, 7, 6, 9, 2}	2	6	5	7
38	5	条件判定（偽）	{1, 7, 6, 9, 2}	2	6	5	7
39	10	代入	{1, 7, 6, 9, 2}	2	6	5	7
40	11	代入	{1, 2, 6, 9, 2}	2	6	5	7
41	12	代入	{1, 2, 6, 9, 7}	2	6	5	7
42	3	繰返しの更新	{1, 2, 6, 9, 7}	3	6	5	7
43	3	条件判定（真）	{1, 2, 6, 9, 7}	3	6	5	7
44	4	代入	{1, 2, 6, 9, 7}	3	6	3	7
45	5	繰返しの初期化	{1, 2, 6, 9, 7}	3	4	3	7
46	5	条件判定（真）	{1, 2, 6, 9, 7}	3	4	3	7
47	6	条件判定（偽）	{1, 2, 6, 9, 7}	3	4	3	7
48	5	繰返しの更新	{1, 2, 6, 9, 7}	3	5	3	7
49	5	条件判定（真）	{1, 2, 6, 9, 7}	3	5	3	7
50	6	条件判定（偽）	{1, 2, 6, 9, 7}	3	5	3	7
51	5	繰返しの更新	{1, 2, 6, 9, 7}	3	6	3	7
52	5	条件判定（偽）	{1, 2, 6, 9, 7}	3	6	3	7
53	10	代入	{1, 2, 6, 9, 7}	3	6	3	6
54	11	代入	{1, 2, 6, 9, 7}	3	6	3	6
55	12	代入	{1, 2, 6, 9, 7}	3	6	3	6
56	3	繰返しの更新	{1, 2, 6, 9, 7}	4	6	3	6
57	3	条件判定（真）	{1, 2, 6, 9, 7}	4	6	3	6
58	4	代入	{1, 2, 6, 9, 7}	4	6	4	6
59	5	繰返しの初期化	{1, 2, 6, 9, 7}	4	5	4	6
60	5	条件判定（真）	{1, 2, 6, 9, 7}	4	5	4	6
61	6	条件判定（真）	{1, 2, 6, 9, 7}	4	5	4	6
62	7	代入	{1, 2, 6, 9, 7}	4	5	5	6
63	5	繰返しの更新	{1, 2, 6, 9, 7}	4	6	5	6
64	5	条件判定（偽）	{1, 2, 6, 9, 7}	4	6	5	6
65	10	代入	{1, 2, 6, 9, 7}	4	6	5	9
66	11	代入	{1, 2, 6, 7, 7}	4	6	5	9
67	12	代入	{1, 2, 6, 7, 9}	4	6	5	9
68	3	繰返しの更新	{1, 2, 6, 7, 9}	5	6	5	9
69	3	条件判定（偽）	{1, 2, 6, 7, 9}	5	6	5	9
70	14	戻る（{1, 2, 6, 7, 9}）	{1, 2, 6, 7, 9}	5	6	5	9

選択ソート 問題12

〔プログラム〕

設問1

設問2

設問3

本番形式

解説

行番号つきのプログラム

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

選択ソート　問題12