はじめに
基本情報技術者試験の科目 B で、挿入ソートは「空欄補充で狙われやすい形」の代表格です。しかも空欄になるのはたいてい内側の while の 1 行で、そこは眺めているだけでは正誤の区別がつきません。
こういうときに効くのは、正解の理屈を覚えることより、間違いを入れたときに何が起きるかを知っておくことだと思っています。挿入ソートの内側ループは、書き間違えたときの壊れ方が 3 種類にきれいに分かれていて、しかもそのうち 1 つが「エラーも出さずに静かに壊れる」という一番たちの悪いパターンです。
というわけで、書き間違いを 4 パターン用意して、擬似言語のインタプリタに全部実際に通しました。
対象のコード
昇順に整列する挿入ソートです。擬似言語なので配列の添字は 1 始まりです。
整数型の配列: 数値 ← {4, 2, 7, 1}
整数型: 一時 ← 0
整数型: j ← 0
for (i を 2 から 4 まで 1 ずつ増やす)
一時 ← 数値[i]
j ← i - 1
while (j ≧ 1 and 数値[j] > 一時)
数値[j + 1] ← 数値[j]
j ← j - 1
endwhile
数値[j + 1] ← 一時
endfor
print(数値)
出力は {1, 2, 4, 7} です。
構造を 3 行で言うとこうなります。この 3 行が言えれば、細部は毎回その場で組み立て直せます。
| 場所 | 役割 |
|---|---|
| 外側 for |
挿入する要素を 1 個決める（一時 に退避する） |
| 内側 while | その要素が入る場所を空ける（大きい要素を後ろへずらす） |
| while の直後 |
空いた場所に置く（数値[j + 1] ← 一時） |
外側 for が 2 から始まるのは、先頭 1 個だけの列は「すでに整列済み」とみなせるからです。
内側 while がやっているのは「ずらす」だけ
内側の 2 行を分解します。
数値[j + 1] ← 数値[j] ← 1 つ後ろへコピーする
j ← j - 1 ← 比較する相手を 1 つ手前へ動かす
**1 行目が「作業」で、2 行目が「前進」**です。ループというのは基本的にこの 2 つの組で、片方でも欠けると止まらないか、止まっても仕事が終わっていません。
j ← j - 1 は地味なので落としやすいのですが、これは「1 つ手前の要素と比べ直す」という宣言です。ずらしただけで比較相手を動かさなければ、同じ相手をずっと見続けることになります。
なお、コピー先の 数値[j + 1] は直前まで 一時 に入っていた値がいた場所なので、上書きしても値は失われません。最初に 一時 ← 数値[i] で退避しているのはこのためです。この退避があるから、内側ループは「交換」ではなく片方向の「コピー」だけで済んでいます。
書き間違い 4 パターンを実行した結果
内側 while の 2 行目を差し替えて、それぞれ実行しました。結果はこうなります。
| 2 行目に書いたもの | 実行結果 |
|---|---|
j ← j - 1 |
{1, 2, 4, 7}（正しい） |
j ← j + 1 |
配列の範囲外アクセスでエラー |
i ← i - 1 |
無限ループ |
一時 ← 数値[j] |
{4, 4, 7, 7}（エラーなしで壊れた結果が出る） |
順に見ていきます。
j ← j + 1: 添字が伸びていって範囲外に出る
方向が逆です。j が増えると 数値[j + 1] の書き込み先も一緒に伸びていき、要素数 4 の配列に対して 5 番目へ書こうとしたところで落ちます。
比較の条件 数値[j] > 一時 は、j が進むにつれて「さっき自分でコピーした値」を見ることになるので、条件がなかなか偽にならず止まりません。自分が書き潰した値を自分で読み返している状態です。
i ← i - 1: j が動かないので永久に回る
外側のカウンタを触っても、内側 while の条件に出てくるのは j です。j が変わらない以上 数値[j] > 一時 の真偽も変わらず、同じ代入を延々と繰り返します。
「ループ変数を更新した」つもりで別の変数を更新しているというだけの間違いですが、条件式に登場する変数と更新している変数が違う、というのは実務でも普通にやります。while を見たら「この条件に出てくる変数のうち、どれがループ内で変化するか」を先に確認するのが確実です。
一時 ← 数値[j]: 一番たちが悪い
これだけはエラーになりません。最後まで走りきって {4, 4, 7, 7} を出力します。
何が起きたか。一時 は「挿入する値の退避場所」なのに、それを比較相手の値で上書きしてしまっています。すると次の比較 数値[j] > 一時 は 4 > 4 のように必ず偽になるのでループはすぐ抜けますが、そのあとの 数値[j + 1] ← 一時 が、退避したはずの値ではなくコピー元の値を書き込みます。挿入したかった値はどこにも残っていません。
元の {4, 2, 7, 1} にあった 2 と 1 が結果から消えて、代わりに 4 と 7 が 2 個ずつ現れているのはそのためです。
3 つの中でこれが一番怖いのは、症状が出るのが壊した場所ではないからです。無限ループも範囲外アクセスもその場で止まってくれますが、これは静かに最後まで走って、間違った答えを自信満々に出してきます。試験で選択肢に並んでいたら、実行結果を最後まで追わないと切れません。
条件式の順序も答えの一部
もう 1 つ、この形で見落としやすいのが while の条件です。
while (j ≧ 1 and 数値[j] > 一時)
この 2 つは入れ替えてはいけません。実際に入れ替えて実行すると、こうなります。
配列 '数値' の要素は 4 個しかありませんが、添字 0 にアクセスしようとしました
j は内側ループで 1 ずつ減っていき、先頭まで到達すると 0 になります。そのとき j ≧ 1 が先に評価されて偽になるので、数値[j] は評価されずに済んでいます。これが短絡評価（ショートサーキット）で、and の左が偽なら右は見ない、という規則です。
つまり j ≧ 1 は「ループを止めるための条件」であると同時に、数値[0] を読まないためのガードでもあります。順序に意味があるので、条件式を書き写すときに並べ替えないでください。
擬似言語の配列が 1 始まりなので 0 が範囲外になりますが、0 始まりの言語でも同じ構造の while (j >= 0 && a[j] > tmp) で a[-1] を踏まないようにする、という形で必ず出てきます。境界の番兵を条件の左側に置くのは言語を問わない定石です。
動かして確かめる
上の 4 パターンは、読んで納得するより 1 回ステップ実行を眺めたほうが早いです。擬似言語をブラウザで 1 行ずつ実行して、j と 一時 と配列の中身が毎ステップどう変わるかを見られるようにしてあります。
コードを貼り付けて内側の 1 行を書き換えれば、無限ループも範囲外アクセスもその場で再現できます。書いたコードはブラウザの外に出ません。
この挿入ソートを空欄補充の形にした問題も置いてあります。上を読んでから解くと、選択肢を 1 つずつ「これは無限ループ」「これは範囲外」と切っていけるはずです。
挿入ソートの内側ループを埋める練習問題 / 配列の擬似言語レッスン
添字の 1 始まりや for の終了値など、挿入ソート以外のつまずきどころは別記事にまとめています。
基本情報の擬似言語が読みにくいのは「動かせない」から ── ブラウザで1行ずつ実行できるようにした
参考書
出題パターンの網羅は書籍のほうが速いです。擬似言語まわりで実際に読んで良かったものを挙げておきます。
- ［改訂新版］基本情報技術者【科目B】アルゴリズム×擬似言語 トレーニングブック ── 整列アルゴリズムのトレース練習が厚い。この記事のような「手で追う」練習を反復したい人向け
- 基本情報技術者【科目B】ゼロからわかるアルゴリズムと擬似言語 ── プログラミング未経験前提の説明。そもそも while の追い方で止まるならこちら
おわりに
挿入ソートの内側 while は 2 行しかありませんが、その 2 行に「ループの前進」「退避した値の扱い」「短絡評価によるガード」が全部詰まっています。空欄補充で狙われるのは偶然ではなく、2 行で 3 つのことを問えるからなのだと思います。
正解を覚えるのではなく、間違えたときに無限ループになるのか、範囲外で落ちるのか、静かに壊れるのか。そこまで見えていれば選択肢は自然に絞れます。