挿入ソート｜手札を並べるのと同じ【基本情報技術者試験科目B】

3つめの整列です。トランプの手札を並べるとき、人が自然にやっているやり方がそのままアルゴリズムになっています。

第2部　定番処理の型　全27回

A1-1トレース表の書き方 A1-2繰返しのトレース A1-3配列のトレース A2-1配列を全部見る A2-2最大・最小を見つける A2-3探す（線形探索）A2-4入れる・消す A2-52つの配列を突き合わせる A3-12次元配列の走査 A3-22次元配列の集計 A4-1文字列を1文字ずつ A4-2文字列照合 A5-1交換して並べるA5-2挿入ソートA6分割して並べるA7-12分探索A7-2ハッシュ表探索A8-1再帰とはA8-2再帰のトレースA9スタックとキューA10-1リストを読むA10-2リストの挿入と削除A11木構造A12木の巡回A13グラフA14AI・データを題材にしたプログラムA15ファイル処理

Table of contents

左の何枚かだけが、すでに小さい順
差し込む場所は、うしろから空ける
止まる条件は、2つある
3つの整列のちがい
つまずきポイントまとめ
次に読む

左の何枚かだけが、すでに小さい順

配った札を左から並べていく場面です。新しい1枚を、すでに並んでいるところへ差し込みます。

実物で見ます。{5, 3, 8, 1} を並べ替える途中は、こうなっています。

どこまでが「並んでいる」か

{5, 3, 8, 1}はじめ。1枚だけなら、それだけで小さい順

{3, 5, 8, 1}3 を差し込んだ。左2枚が小さい順

{3, 5, 8, 1}8 はそのまま。左3枚が小さい順

{1, 3, 5, 8}1 を差し込んだ。全部が小さい順

下線のところが「小さい順に並んでいる範囲」です。1周ごとに1つずつ右へ伸びます。その右は、まだ手つかずのまま置いてあるだけ。

左の何枚かだけが、すでに小さい順

地色のところが「小さい順に並んでいる範囲」。1周ごとに1つずつ右へ伸びる

はじめ

1枚だけなら、それだけで小さい順

3 を差し込んだ

左2枚が小さい順

8 はそのまま

左3枚が小さい順

1 を差し込んだ

全部が小さい順

ただし位置は動く。並んでいるのは、その範囲の中での順序だけ

「並んでいる」＝「確定」ではない

前回のバブルと選択は、確定した場所からもう動きません。挿入は違います。

上の3行目 {3, 5, 8, 1} を見てください。3 も 5 も 8 も、最終的な位置ではありません。次に 1 が来ると全員が1つ右へずれます。

並んでいるのはその範囲の中での順序だけ。位置は動きます。

差し込む場所は、うしろから空ける

差し込むには、場所を空けなければいけません。やり方は A2-4 の挿入とまったく同じです。

差し込む場所は、うしろから空ける

整数型の配列: a ← {5, 3, 8, 1} の4周目。tmp に取り出してから、右へ送る

① tmp ← a[i]　4枚目の 1 を取り出す

tmp1

取り出したので、a[4] はもう上書きしてよい

② j ＝ 3：a[4] ← a[3]　8 は 1 より大きいので右へ送る

tmp1

③ j ＝ 2：a[3] ← a[2]　5 も大きいので送る

tmp1

④ j ＝ 1：a[2] ← a[1]　3 も大きいので送る

tmp1

⑤ j が 0 になって止まる → a[j ＋ 1] ← tmp

tmp1

送れなくなったところ（a[1]）へ、取り出した 1 を置く

送る向きはうしろから。前からだと同じ値で埋まる（A2-4 と同じ理由）

取り出した札を tmp に持っておき、それより大きい札を、右へ1つずつ送ります。送れなくなったところが、差し込む場所です。

止まる条件は、2つある

「送り続ける」といっても、どこかで止めなければいけません。止まる理由は2つあります。

止まる理由は、2つある

while (j ＞ 0 and a[j] ＞ tmp) ── かっこの中の2つが、そのまま2つの理由

その1 ── 小さい札に出会った（a[j] ＞ tmp が成り立たない）

tmp8

tmp が 8 のとき、左隣の 5 は 8 より大きくない。送る必要が無いので、ここで止まる

その2 ── 先頭まで来た（j ＞ 0 が成り立たない）

tmp1

tmp が 1 のときは全部より小さいので、j が 0 になるまで送り続けて止まる

j ＞ 0 を先に書く。逆にすると、存在しない a[0] を見に行く

整数型の配列: a ← {5, 3, 8, 1}
整数型: i, j, tmp

for (i を 2 から aの要素数 まで 1 ずつ増やす)
  tmp ← a[i]
  j ← i － 1
  while (j ＞ 0 and a[j] ＞ tmp)
    a[j ＋ 1] ← a[j]
    j ← j － 1
  endwhile
  a[j ＋ 1] ← tmp
endfor

上から読む

```
整数型の配列: a ← {5, 3, 8, 1}
整数型: i, j, tmp
```
材料。並べ替える配列 a、番号を入れておく i と j、そして取り出した札を持っておく tmp です。
```
for (i を 2 から aの要素数 まで 1 ずつ増やす)
  tmp ← a[i]
```
1枚取り出す。2枚目から順に、その札を tmp へ取り出します。取り出したので、a[i] の場所は上書きしてかまいません。
```
  j ← i － 1
```
左隣から見る。j は、いま比べている札の番号です。取り出した札の1つ左から始めます。
```
  while (j ＞ 0 and a[j] ＞ tmp)
    a[j ＋ 1] ← a[j]
    j ← j － 1
  endwhile
```
右へ送る。tmp より大きい札を1つ右へ写して、j を左へ進めます。上の2つの理由のどちらかで、ここが止まります。
```
  a[j ＋ 1] ← tmp
endfor
```
差し込む。送れなくなったところが空いているので、そこへ取り出した札を置きます。＋ 1 が付く理由は、このあとで見ます。

挿入ソートを1行ずつ動かす

当サイトオリジナルの例題

ループ開始前

配列

▲ いま読んでいる▲ いま書いた

いま計算していること

まだ計算していません

変数の状態

トレース表（進めると1行ずつ積み上がります）

and の順番が大事

j ＞ 0 を先に書きます。逆にすると、j が 0 になったときに a[0] を見に行くことになります。存在しない要素です。

擬似言語の and は、左が偽なら右を見ません。だから j ＞ 0 が先なら安全です（G8-2）。

最後の1行

a[j ＋ 1] ← tmp の ＋ 1 を忘れないこと。while を抜けた時点で j は1つ行き過ぎているので、その1つ右に置きます。

3つの整列のちがい

方法	1周でやること	途中経過
バブル	隣どうしを比べて、そのつど交換	右端から確定していく
選択	最小を探して、1回だけ交換	左端から確定していく
挿入	1枚取り出して、正しい位置へ差し込む	左の何枚かが小さい順（位置はまだ動く）

試験では「途中経過を答えよ」という形でよく問われます。どの方法かが分かれば、途中の並びは決まります。

つまずきポイントまとめ

まちがえ方	正しい読み方
外側を 1 から回す	1枚目はすでに並んでいる。`2` から
`and` の順を逆にする	`j ＞ 0` が先。存在しない要素を見に行かない
最後に `a[j]` へ置く	`while` を抜けた `j` は行き過ぎ。`a[j ＋ 1]`
途中経過をバブルと同じだと思う	挿入の左はその範囲での順序だけ。あとで全員ずれる
送る向きを前からにする	うしろから。前からだと同じ値で埋まる

次に読む

A6	分割して並べる ─ マージソートとクイックソート
A5-1	交換して並べる ─ バブルソートと選択ソート
G8-2	and / or / not ─ 条件のつなぎ方
目次	基本情報技術者試験科目B 攻略ガイド