挿入ソート｜擬似言語のトレース解説と練習問題
関数 sort は、配列 data を昇順に整列して返す。2 番目以降の要素を順に取り出し、それより前の整列済みの部分の正しい位置に挿入する。配列の要素番号は 1 から始まる。
プログラム
| 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 |
何をしているか
2番目の要素から順に取り出し（key）、それより前の整列済みの部分を右から見ていきます。key より大きい要素は右へ1つずらし、空いた所に key を入れます。
トレースのコツ
keyに取り出した時点で、元の場所は「空き」と考えます。ずらすたびに、空きが左へ1つ動きます。- while を抜けたときの
jは、「key 以下の要素の位置」か 0 です。keyを入れるのはj ＋ 1番目です。 - ずらした回数は、
keyより大きい要素が前にいくつあったかと同じです。
よくある間違い
- ずらしている途中の配列（同じ値が2つ見える状態）を、1巡の結果として答える。
keyを入れ終えた時点で確かめます。 jが 0 になったとき、data[0]を見にいくと考える。左の条件「j ≧ 1」が偽なので、右の条件は調べません。- すでに正しい位置にある要素でも、「key を入れる」行は実行されることを見落とす。同じ場所に入れ直すだけです。
例題：sort({8, 7, 5, 3}) を最後まで追う
上のプログラムを sort({8, 7, 5, 3}) で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。
| # | 行 | したこと | data | i | j | key |
|---|---|---|---|---|---|---|
| 1 | 2 | 宣言 | {8, 7, 5, 3} | 未設定 | 未設定 | 未設定 |
| 2 | 3 | 繰返しの初期化 | {8, 7, 5, 3} | 2 | 未設定 | 未設定 |
| 3 | 3 | 条件判定（真） | {8, 7, 5, 3} | 2 | 未設定 | 未設定 |
| 4 | 4 | 代入 | {8, 7, 5, 3} | 2 | 未設定 | 7 |
| 5 | 5 | 代入 | {8, 7, 5, 3} | 2 | 1 | 7 |
| 6 | 6 | 条件判定（真） | {8, 7, 5, 3} | 2 | 1 | 7 |
| 7 | 7 | 代入 | {8, 8, 5, 3} | 2 | 1 | 7 |
| 8 | 8 | 代入 | {8, 8, 5, 3} | 2 | 0 | 7 |
| 9 | 6 | 条件判定（偽） | {8, 8, 5, 3} | 2 | 0 | 7 |
| 10 | 10 | 代入 | {7, 8, 5, 3} | 2 | 0 | 7 |
| 11 | 3 | 繰返しの更新 | {7, 8, 5, 3} | 3 | 0 | 7 |
| 12 | 3 | 条件判定（真） | {7, 8, 5, 3} | 3 | 0 | 7 |
| 13 | 4 | 代入 | {7, 8, 5, 3} | 3 | 0 | 5 |
| 14 | 5 | 代入 | {7, 8, 5, 3} | 3 | 2 | 5 |
| 15 | 6 | 条件判定（真） | {7, 8, 5, 3} | 3 | 2 | 5 |
| 16 | 7 | 代入 | {7, 8, 8, 3} | 3 | 2 | 5 |
| 17 | 8 | 代入 | {7, 8, 8, 3} | 3 | 1 | 5 |
| 18 | 6 | 条件判定（真） | {7, 8, 8, 3} | 3 | 1 | 5 |
| 19 | 7 | 代入 | {7, 7, 8, 3} | 3 | 1 | 5 |
| 20 | 8 | 代入 | {7, 7, 8, 3} | 3 | 0 | 5 |
| 21 | 6 | 条件判定（偽） | {7, 7, 8, 3} | 3 | 0 | 5 |
| 22 | 10 | 代入 | {5, 7, 8, 3} | 3 | 0 | 5 |
| 23 | 3 | 繰返しの更新 | {5, 7, 8, 3} | 4 | 0 | 5 |
| 24 | 3 | 条件判定（真） | {5, 7, 8, 3} | 4 | 0 | 5 |
| 25 | 4 | 代入 | {5, 7, 8, 3} | 4 | 0 | 3 |
| 26 | 5 | 代入 | {5, 7, 8, 3} | 4 | 3 | 3 |
| 27 | 6 | 条件判定（真） | {5, 7, 8, 3} | 4 | 3 | 3 |
| 28 | 7 | 代入 | {5, 7, 8, 8} | 4 | 3 | 3 |
| 29 | 8 | 代入 | {5, 7, 8, 8} | 4 | 2 | 3 |
| 30 | 6 | 条件判定（真） | {5, 7, 8, 8} | 4 | 2 | 3 |
| 31 | 7 | 代入 | {5, 7, 7, 8} | 4 | 2 | 3 |
| 32 | 8 | 代入 | {5, 7, 7, 8} | 4 | 1 | 3 |
| 33 | 6 | 条件判定（真） | {5, 7, 7, 8} | 4 | 1 | 3 |
| 34 | 7 | 代入 | {5, 5, 7, 8} | 4 | 1 | 3 |
| 35 | 8 | 代入 | {5, 5, 7, 8} | 4 | 0 | 3 |
| 36 | 6 | 条件判定（偽） | {5, 5, 7, 8} | 4 | 0 | 3 |
| 37 | 10 | 代入 | {3, 5, 7, 8} | 4 | 0 | 3 |
| 38 | 3 | 繰返しの更新 | {3, 5, 7, 8} | 5 | 0 | 3 |
| 39 | 3 | 条件判定（偽） | {3, 5, 7, 8} | 5 | 0 | 3 |
| 40 | 12 | 戻る（{3, 5, 7, 8}） | {3, 5, 7, 8} | 5 | 0 | 3 |
この例題で問われること
問 sort({8, 7, 5, 3}) を呼び出したときの戻り値はどれか。
答え {3, 5, 7, 8}
- 戻り値になる data は、{8, 7, 5, 3} → {8, 8, 5, 3} → {7, 8, 5, 3} → {7, 8, 8, 3} → {7, 7, 8, 3} → {5, 7, 8, 3} → {5, 7, 8, 8} → {5, 7, 7, 8} → {5, 5, 7, 8} → {3, 5, 7, 8} と変わります。
- 12行目で返す時点の値 {3, 5, 7, 8} が答えです。
問 10行目を2回目に実行した直後の、変数 data の値はどれか。
答え {5, 7, 8, 3}
- 10行目は全部で3回実行されます。
- 実行した直後の data は、順に {7, 8, 5, 3} → {5, 7, 8, 3} → {3, 5, 7, 8} です。
- 2回目の直後なので、答えは {5, 7, 8, 3} です。
問 7行目が実行される回数はどれか。
答え 6
- 7行目が実行されるのは、6行目の条件が真になったときだけです。
- 6行目の条件は9回評価され、真になるのは6回です。したがって 7行目は6回実行されます。
練習問題 標準（5問）
本試験と同じくらいの量。レベル：基礎
- 問題01 sort({6, 8, 5, 9})
- 問題02 sort({9, 8, 1})
- 問題03 sort({6, 8, 3})
- 問題04 sort({6, 8, 1})
- 問題05 sort({2, 6, 8, 3})
もっと解く（追加の10問）
練習問題 じっくり（10問）
長めのトレースで力をつける。レベル：中級
- 問題01 sort({6, 5, 2, 1, 7})
- 問題02 sort({4, 7, 5, 2, 9})
- 問題03 sort({3, 6, 2, 7})
- 問題04 sort({8, 3, 9, 5})
- 問題05 sort({3, 5, 8, 2, 4})
- 問題06 sort({9, 8, 1, 6, 4})
- 問題07 sort({4, 8, 2, 5, 1})
- 問題08 sort({9, 8, 7, 4, 3})
- 問題09 sort({7, 4, 5, 3, 2})
- 問題10 sort({9, 6, 7, 1, 8})
もっと解く（追加の20問）
- 問題11 sort({8, 4, 5, 9, 3})
- 問題12 sort({4, 5, 3, 7, 8})
- 問題13 sort({7, 1, 4, 3})
- 問題14 sort({4, 1, 7, 2})
- 問題15 sort({8, 1, 4, 3, 5})
- 問題16 sort({2, 6, 9, 8, 4})
- 問題17 sort({4, 8, 1, 5})
- 問題18 sort({9, 5, 2, 7, 6})
- 問題19 sort({9, 5, 4, 7, 8})
- 問題20 sort({6, 5, 7, 3})
- 問題21 sort({8, 1, 2, 7, 5})
- 問題22 sort({9, 8, 7, 6})
- 問題23 sort({1, 8, 4, 9, 7})
- 問題24 sort({4, 2, 6, 3, 8})
- 問題25 sort({6, 2, 4, 9, 3})
- 問題26 sort({6, 3, 7, 1})
- 問題27 sort({7, 8, 9, 2})
- 問題28 sort({9, 7, 3, 5})
- 問題29 sort({5, 8, 4, 2})
- 問題30 sort({5, 7, 6, 4, 9})