選択ソート｜擬似言語のトレース解説と練習問題

レベル：基礎　／　タグ：for・二重ループ・配列・交換・整列

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

プログラム

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

何をしているか

まだ整列していない部分から最小の要素を探し、その部分の先頭と入れ替えます。これを先頭から順に繰り返すと、前から1つずつ位置が決まっていきます。

トレースのコツ

外側の繰返し1回を「1巡」として区切ります。1巡の中では、min の変化だけを追えば十分です。
min は最小の値ではなく、最小の要素の位置です。比べるのは data[j] と data[min] です。
1巡の終わりに、配列を書き直します。入替えは1巡につき1回だけです。

よくある間違い

min を値だと思って、data[j] < min と読んでしまう。
最小が先頭にあった巡でも、入替えの3行は実行されることを忘れる。自分自身と入れ替えるので、配列は変わりません。
内側の繰返しの始まりを 1 と思い込む。i ＋ 1 から始まるので、巡が進むほど比べる回数は減ります。

例題：sort({8, 7, 3, 2, 5}) を最後まで追う

上のプログラムを sort({8, 7, 3, 2, 5}) で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。

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

この例題で問われること

問　sort({8, 7, 3, 2, 5}) を呼び出したときの戻り値はどれか。

答え　{2, 3, 5, 7, 8}

戻り値になる data は、{8, 7, 3, 2, 5} → {2, 7, 3, 2, 5} → {2, 7, 3, 8, 5} → {2, 3, 3, 8, 5} → {2, 3, 7, 8, 5} → {2, 3, 5, 8, 5} → {2, 3, 5, 8, 7} → {2, 3, 5, 7, 7} → {2, 3, 5, 7, 8} と変わります。
14行目で返す時点の値 {2, 3, 5, 7, 8} が答えです。

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

答え　{2, 3, 5, 7, 8}

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

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

答え　6

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

練習問題標準（5問）

本試験と同じくらいの量。レベル：基礎

問題01　moveMin({7, 1, 9, 3})
問題02　moveMin({8, 6, 2, 9, 5})
問題03　moveMin({4, 1, 9, 2, 7})
問題04　moveMin({9, 7, 3, 6, 4})
問題05　moveMin({3, 1, 6, 9, 2})

もっと解く（追加の10問）

問題06　moveMin({4, 5, 1, 6, 2})
問題07　moveMin({6, 4, 9, 5})
問題08　moveMin({6, 3, 7, 5, 9})
問題09　moveMin({8, 1, 2, 5, 4})
問題10　moveMin({7, 6, 2, 8, 5})
問題11　moveMin({5, 1, 8, 2, 6})
問題12　moveMin({9, 4, 8, 7})
問題13　moveMin({8, 1, 6, 3, 2})
問題14　moveMin({9, 8, 3, 5, 4})
問題15　moveMin({3, 9, 1, 8, 7})

練習問題じっくり（10問）

長めのトレースで力をつける。レベル：中級

問題01　sort({3, 6, 4, 1, 2})
問題02　sort({9, 1, 8, 3})
問題03　sort({8, 4, 5, 7, 6})
問題04　sort({7, 6, 9, 5, 4})
問題05　sort({8, 4, 6, 9})
問題06　sort({5, 7, 1, 4, 3})
問題07　sort({7, 4, 9, 5, 8})
問題08　sort({6, 4, 8, 5, 2})
問題09　sort({5, 2, 7, 3, 4})
問題10　sort({9, 2, 5, 6, 7})

もっと解く（追加の20問）

問題11　sort({6, 1, 2, 9, 8})
問題12　sort({7, 1, 6, 9, 2})
問題13　sort({3, 8, 2, 5, 1})
問題14　sort({8, 2, 1, 3, 9})
問題15　sort({5, 9, 4, 2, 3})
問題16　sort({8, 3, 5, 6})
問題17　sort({6, 7, 2, 5, 8})
問題18　sort({9, 4, 5, 6})
問題19　sort({9, 1, 3, 4, 2})
問題20　sort({9, 2, 5, 3, 8})
問題21　sort({8, 2, 6, 5})
問題22　sort({9, 2, 4, 3})
問題23　sort({8, 2, 7, 9, 3})
問題24　sort({3, 1, 8, 7, 2})
問題25　sort({9, 3, 1, 7})
問題26　sort({8, 6, 9, 4, 1})
問題27　sort({7, 9, 1, 6})
問題28　sort({7, 1, 2, 3, 9})
問題29　sort({6, 8, 7, 2, 4})
問題30　sort({2, 5, 1, 6, 4})