挿入ソート　問題13

じっくりレベル：中級　／　このアルゴリズムの解説を読む

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

関数 sort は、配列 data を昇順に整列して返す。2 番目以降の要素を順に取り出し、それより前の整列済みの部分の正しい位置に挿入する。配列の要素番号は 1 から始まる。

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

〔プログラム〕

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

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

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

#	行	したこと	data	i	j	key

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

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

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

設問1

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

解答群ア　data[j] > key イ　data[j] > data[i] ウ　data[j ＋ 1] > key エ　j > key

正解：ア　data[j] > key

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

設問2

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

解答群ア　{7, 1, 4, 3} イ　{1, 4, 7, 3} ウ　{1, 3, 4, 7} エ　{1, 7, 4, 3}

正解：エ　{1, 7, 4, 3}

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

設問3

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

解答群ア　3 イ　4 ウ　5 エ　7

正解：イ　4

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

本番形式

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

関数 sort は，配列 data を昇順に整列して返す。2 番目以降の要素を順に取り出し，それより前の整列済みの部分の正しい位置に挿入する。配列の要素番号は 1 から始まる。

関数 sort を sort({7, 1, 4, 3}) として呼び出したとき，プログラム中の α の行は［　ａ　］回実行される。

〔プログラム〕

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

整数型: i, j, key

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

key ← data[i]

j ← i － 1

while (j ≧ 1 and data[j] > key)

data[j ＋ 1] ← data[j]　/*** α ***/

j ← j － 1

endwhile

data[j ＋ 1] ← key

endfor

return data

解答群

正解：エ　4

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

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

解説

取り出した要素 key より大きい要素を、右へ1つずつずらして場所を空け、空いた所に key を入れます。ずらす回数は、key より大きい要素が前にいくつあるかで決まります。

行番号つきのプログラム

1	○整数型の配列: sort(整数型の配列: data)
2	整数型: i, j, key
3	for (i を 2 から dataの要素数まで 1 ずつ増やす)
4	key ← data[i]
5	j ← i － 1
6	while (j ≧ 1 and data[j] > key)
7	data[j ＋ 1] ← data[j]
8	j ← j － 1
9	endwhile
10	data[j ＋ 1] ← key
11	endfor
12	return data

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

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

#	行	したこと	data	i	j	key
1	2	宣言	{7, 1, 4, 3}	未設定	未設定	未設定
2	3	繰返しの初期化	{7, 1, 4, 3}	2	未設定	未設定
3	3	条件判定（真）	{7, 1, 4, 3}	2	未設定	未設定
4	4	代入	{7, 1, 4, 3}	2	未設定	1
5	5	代入	{7, 1, 4, 3}	2	1	1
6	6	条件判定（真）	{7, 1, 4, 3}	2	1	1
7	7	代入	{7, 7, 4, 3}	2	1	1
8	8	代入	{7, 7, 4, 3}	2	0	1
9	6	条件判定（偽）	{7, 7, 4, 3}	2	0	1
10	10	代入	{1, 7, 4, 3}	2	0	1
11	3	繰返しの更新	{1, 7, 4, 3}	3	0	1
12	3	条件判定（真）	{1, 7, 4, 3}	3	0	1
13	4	代入	{1, 7, 4, 3}	3	0	4
14	5	代入	{1, 7, 4, 3}	3	2	4
15	6	条件判定（真）	{1, 7, 4, 3}	3	2	4
16	7	代入	{1, 7, 7, 3}	3	2	4
17	8	代入	{1, 7, 7, 3}	3	1	4
18	6	条件判定（偽）	{1, 7, 7, 3}	3	1	4
19	10	代入	{1, 4, 7, 3}	3	1	4
20	3	繰返しの更新	{1, 4, 7, 3}	4	1	4
21	3	条件判定（真）	{1, 4, 7, 3}	4	1	4
22	4	代入	{1, 4, 7, 3}	4	1	3
23	5	代入	{1, 4, 7, 3}	4	3	3
24	6	条件判定（真）	{1, 4, 7, 3}	4	3	3
25	7	代入	{1, 4, 7, 7}	4	3	3
26	8	代入	{1, 4, 7, 7}	4	2	3
27	6	条件判定（真）	{1, 4, 7, 7}	4	2	3
28	7	代入	{1, 4, 4, 7}	4	2	3
29	8	代入	{1, 4, 4, 7}	4	1	3
30	6	条件判定（偽）	{1, 4, 4, 7}	4	1	3
31	10	代入	{1, 3, 4, 7}	4	1	3
32	3	繰返しの更新	{1, 3, 4, 7}	5	1	3
33	3	条件判定（偽）	{1, 3, 4, 7}	5	1	3
34	12	戻る（{1, 3, 4, 7}）	{1, 3, 4, 7}	5	1	3