科目Bの挿入ソート問題の解き方｜要素をずらして差し込む手順を追う

挿入ソートの while の中で、配列の中身がずれていくのを追い切れない。

科目Bの整列の問題で、data[j + 1] ← data[j] のような行が出てきた途端に、配列の中身が分からなくなったことはありませんか？

交換するだけのソートなら追えるのに、要素がずらされて上書きされていくと、どの値が消えてどの値が残ったのか自信がなくなる。そう感じている人は多いのではないでしょうか。

大丈夫です。挿入ソートで起きていることは、1枚のカードを手に取って、正しい位置まで並びをずらしてから差し込む、という動きだけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。並び順が決まっている一覧に、新しいデータを1件ずつ正しい位置へ入れていく処理は、実務でも何度も書いてきました。

そうした処理の不具合は、ほとんどがずらす範囲の端で起きます。一つ多くずらしたり、一つ手前に差し込んだりするだけで、データが1件消えてしまうからです。

この記事では、挿入ソートの問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中でこうした問題がどんな位置にあるのかを先に知りたい人は、親記事から読むと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

挿入ソートの問題は何を聞いているのか¶

最初に、問題文が何を求めているのかを整理しておきましょう。挿入ソートが中心になる問題は、聞かれ方によっていくつかの型に分かれます。

よく見かける型を表にまとめました。

どの型でも、根っこにある問いは同じです。取り出した値は、どこまでずらされて、どの位置に差し込まれるのか。

問題文を読んだら、まずどの型なのかを決めましょう。型が決まれば、トレースをどこまで細かく書くべきかも自然に決まります。

交換するソートとの違い¶

整列の問題でよく見るのは、隣どうしを比べて入れ替える交換ソートや、最小値を探して先頭と入れ替える選択ソートです。こうした入れ替え型の追い方は、こちらの記事で整理しています。

【関連記事】科目Bのソート問題を解くコツ｜交換される値を追ってみよう

挿入ソートが違うのは、入れ替えではなく、ずらしてから差し込む点です。主な違いを表にしました。

挿入ソートの左側は、それまでに見た値だけで並んだ状態です。あとから小さい値が来れば、左側の値もさらに右へずらされます。

まず目を付ける場所¶

問われ方が分かったら、次はコードのどこから読むかを決めます。挿入ソートの問題では、目を付ける場所が3つあります。

ひとつ目は取り出した値を入れておく変数、ふたつ目は while の条件、みっつ目はループを抜けたあとに差し込む位置です。この順番で見ていくと、1回分の動きがはっきりします。

取り出した値を変数に逃がしている行¶

最初に見るのは、key ← data[i] のように、配列の値を別の変数に入れている行です。この行があるのは、あとで data[i] の位置が上書きされるからです。

ずらす処理が始まると、data[i] には左隣の値が書き込まれます。先に逃がしておかないと、取り出した値そのものが消えてしまいます。

while の条件は2つの役目を持つ¶

次に見るのは、while の条件です。挿入ソートでは、たいてい2つの条件が and でつながっています。

ひとつは、j が配列の範囲の中にあるかどうか。もうひとつは、左側の値が取り出した値より大きいかどうかです。

前者は配列の外を見に行かないための見張り、後者はずらすかどうかの判断です。どちらが偽になってもループは終わり、その時点の j の1つ右が差し込む位置になります。

要素をずらす処理そのものの読み方に不安がある場合は、先にこちらの記事で確かめておくと安心です。

【関連記事】擬似言語の配列への挿入と削除がわからない人へ｜要素をずらす処理の読み方を解説

例題：6つの数を小さい順に並べる¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次の手続は、整数の配列 data を小さい順に並べ替えます。配列の要素番号は1から始まるものとします。

○insertionSort(整数型の配列: 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

外側の for は、2番目から最後までの値を1つずつ取り出します。1番目から始めないのは、値が1つだけなら、それだけで並んでいると考えられるからです。

内側の while は、取り出した key より大きい値を、右へ1つずつずらします。ずらし終わったら、空いた位置に key を差し込みます。

差し込む位置が j + 1 になる理由¶

while を抜けたとき、j は key 以下の値が見つかった位置か、0 を指しています。key はその値の右隣に入るべきなので、差し込む位置は j + 1 です。

ここは空欄補充で最も狙われやすい行です。j ではなく j + 1 であることを、このあとのトレースで実際に確かめてみましょう。

トレース表で要素のずれを追う¶

頭の中だけで追おうとすると、上書きされた値と残った値をすぐに取り違えます。そこで、外側のループ1回につき1行を使うトレース表を書きます。

data の初期値を {5, 2, 4, 6, 1, 3} として、外側のループが1回終わるごとの状態を表にしました。

i が 4 のときは、左隣の 5 が 6 より小さいので、1回もずらさずにそのまま元の位置へ戻ります。ずらす回数が0回の行があるのも、挿入ソートの特徴です。

ずらした回数を足すと 1 + 1 + 0 + 4 + 3 で 9 回です。回数を聞かれる問題では、この列をそのまま合計すれば答えになります。

表の書き方そのものに慣れていない場合は、こちらの記事で基本の形を確かめてから例題に戻ってみてください。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

1回分を細かく追う¶

外側の1行だけでは、while の中で何が起きたかが見えません。いちばんずらす回数が多い i が 5 の回を、while の1周ごとに分解してみます。

途中で同じ値が2つ並ぶ状態が何度も現れます。これは失敗ではなく、ずらしている途中の正しい姿です。

j が 0 になったところで while を抜け、data[1] に key の 1 を書き込みます。ここで初めて、重なっていた 2 の片方が 1 に置き換わり、{1, 2, 4, 5, 6, 3} になります。

key をあらかじめ逃がしていなければ、最初の代入で data[5] の 1 は 6 に上書きされて消えていました。逃がす行の大切さが、表にするとよく分かります。

間違いやすい選択肢の見分け方¶

挿入ソートの問題では、添字の小さなずれを狙った選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

よくある誤りを表にまとめました。

この中でも、特によく狙われるのが差し込む位置と比較の向きです。順番に見ていきましょう。

差し込む位置を j にした選択肢¶

data[j + 1] ← key の部分を空欄にし、data[j] ← key を選択肢に混ぜる形はよく見られます。j に差し込むと、key 以下だった値を上書きしてしまいます。

迷ったときは、i が 2 の1回目だけを試してください。j が 0 で抜けるので、data[0] に書き込むことになり、配列の外を指してしまうとすぐに気付けます。

＞ と ≥ の違いは同じ値で試す¶

比較を data[j] ≥ key に変えても、数の並び自体は同じように小さい順になります。違いが出るのは、同じ値が複数あるときです。

≥ にすると、同じ値の上もずらして前に出るので、同じ値どうしの元の順番が入れ替わります。並べ替えても同じ値の順番が保たれる性質は安定性と呼ばれ、＞ のままなら挿入ソートは安定です。

名前の順で並んだ会員を点数順に並べ直すような問題で、この性質が問われることがあります。選択肢に ＞ と ≥ が並んでいたら、同じ値を2つ含む小さな配列で試すのが確実です。

速くなる並び、遅くなる並び¶

性質を問う問題では、最初の並び方で処理量がどう変わるかを聞かれます。すでに小さい順に並んでいれば、while は1回もずらさずに抜けるので、処理はとても速く終わります。

反対に、大きい順に並んでいると、毎回すべての値をずらすことになります。要素数が n なら、ずらす回数は 1 から n − 1 までの合計になり、n が増えるにつれて急激に多くなります。

この違いは、ループの形から処理量を見積もる考え方とつながっています。外側と内側のループの関係で迷う場合は、こちらの記事も参考にしてください。

【関連記事】科目Bの計算量問題の解き方｜ループの形からオーダーを判断する

Giji Academy のシミュレーターで動かす¶

紙のトレース表で要素のずれをつかんだら、最後は実際に動かして確かめましょう。挿入ソートは、途中で同じ値が並ぶ瞬間があるので、動かして見る効果がとても大きい題材です。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数や配列の中身が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの代入で予想とずれたのかがすぐに分かります。

試すときは、この記事の例題を少しずつ変えてみるのがおすすめです。最初から小さい順に並んだ配列や、大きい順に並んだ配列を入れたり、＞ を ≥ に書き換えたりして、ずらす回数がどう変わるかを予想してから動かしてみてください。

予想と結果が一致すれば、その読み方は身についています。ずれた場合は、どの周で j の値を読み違えたのかを探すことが、いちばんの練習になります。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、値が右へずれて空いた位置に差し込まれる様子を確かめてみてください。

まとめ¶

科目Bの挿入ソートの問題は、動きを1つずつ分解すれば決して難しくありません。取り出した値を逃がし、大きい値を右へずらし、空いた j + 1 の位置へ差し込む、という3つの動きを表に書けば必ず解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、この記事のように要素が6つほどの短い配列で十分です。ずらしている途中で同じ値が2つ並ぶ姿に慣れてしまえば、挿入ソートの問題は落ち着いて追えるようになります。

並んだデータに新しい1件を正しい位置へ入れる考え方は、科目Bだけでなく、実務で一覧を扱うときにもそのまま役立つ力です。次に while の中で要素がずれていく問題に出会ったら、まずは取り出した値を逃がす行を探すところから始めてみてください。