基本情報技術者試験の「科目B」で受験生を悩ませるのが、挿入ソートの変数の動き（トレース）です！
「要素をどこに差し込めばいいのか頭の中で追えなくなる…」
「while文やfor文の中で要素を右にずらす（シフトする）動きがイメージできない…」
そんな悩みを持つ未経験・文系受験生のために、当サイトでは変数の値や配列の動きがひと目でわかるビジュアルシミュレーターを用意しました！
まずは実際に動かしながら、挿入ソートのアルゴリズムとプログラムの連動感を体感してみましょう。
1. 【動く図解】ステップ進むボタンでトレースを擬似体験してみよう
下の「進む ➔」ボタンを押すと、実行中のコード行がハイライトされ、要素の取り出し・比較・右シフト・挿入がリアルタイムに変化します。
配列 num の変化
2. 挿入ソートとは？仕組みをシンプルに理解する
挿入ソート（Insertion Sort）は、「整列済みの列に対して、新しい要素を適切な位置に割り込ませて（挿入して）いく」という整列アルゴリズムです。
手札のトランプを左から小さい順に並べ替える際、新しいカードを1枚ずつ引いて「どこに挟むか」を探して差し込む動作とまったく同じイメージです。
挿入ソートの基本ルール（昇順の場合）
- 先頭の要素（
num[0]）は最初から整列済みとみなす。 - 未整列エリアの先頭要素を取り出し、一時退避変数 tmp に保存する。
- 整列済みエリアを右から左に向かって順番に tmp と比較する。
- tmp より大きい値は1つずつ右へずらし（シフトし）、正しい差し込み場所を開ける。
- 空いた位置（
num[j + 1]）に tmp を差し込む。
3. 科目Bで超頻出！「右シフト（上書き）」と「挿入位置 (j+1)」の罠
挿入ソートのプログラムで受験生が最も混乱するのが、while文の中での要素移動と、ループ終了後の `j + 1` への代入です。
Line 4: while (j >= 0 && num[j] > tmp)（自分より大きい値が続く限り、左へと比較を続ける）Line 5: num[j + 1] = num[j]（自分より大きい値を1マス右へずらして上書きする）Line 6: j = j - 1（比較対象を左の要素へ移動する）Line 7: num[j + 1] = tmp（ずらす処理が止まった位置の「1つ右」に値を挿入する）
j = j - 1 によって比較インデックスが1つ行き過ぎてから while ループを抜けるため、最後に差し込む位置が num[j] ではなく num[j + 1] になる点が穴埋め問題の最頻出ポイントです。
シミュレーターで Line 4➔5➔6➔7 と進む際の、変数 j の減算と配列が右にずれていく感覚を繰り返し確認しておきましょう。
4. 試験本番（紙とペン）で挿入ソートを解くコツ
紙の上で挿入ソートをトレースする際は、以下のステップで「壁（境界）」を意識するのがコツです。
- 整列済み領域と未整列領域の間に縦線（|）を引く（例: [5 | 3, 8, 2]）
- 縦線のすぐ右の数値を丸で囲み、tmp として余白にメモする
- 縦線の左側の数値を右から順に見比べる
- tmp より大きい数値の下に「→」を書いて1つ右にずらし、空いたスキマに tmp を書き込む
- 縦線（|）を1マス右へ移動させて次のループへ進む
縦線を引きながら「整列エリアが左から広がっていく様子」を可視化することで、イージーミスを激減させることができます。
5. 挿入ソートに関するよくある質問（FAQ）
Q. 挿入ソートの計算量はどれくらいですか？
A. 平均・最悪の計算量は O(n^2) です。ただし、「最初からほぼ整列されているデータ」に対しては O(n) という非常に高速なパフォーマンスを発揮する特徴があります。
Q. 「降順（大きい順）」にしたい場合はどこを変えればいいですか？
A. while (j >= 0 && num[j] > tmp) の比較条件を num[j] < tmp に変更することで、小さい値を右へシフトさせる降順ソートになります。
まとめ：挿入ソートは「ずらして差し込む」流れを掴もう
挿入ソート攻略のポイントは、「tmp に避難させる ➔ 大きいものを右にずらす ➔ あいた場所に tmp を戻す」という一連のアルゴリズムパターンを体で覚えることです。
シミュレーターを何度も操作して手札を並べ替える感覚を身につけ、基本情報科目Bのトレース問題を確実に得点源へと変えていきましょう！
コメント