DNCLで挿入ソートを書いてみた

はじめに

この記事は 共通テスト手順記述標準言語 (DNCL) Advent Calendar 2025 の３日目の記事です。

挿入ソートとは

　Dさんが所属する４０人のクラスには１０人１組の班がある。班長は毎日、班員のノートを回収し、出席番号順に並べ替えたうえで担任の先生に提出しなければならない。班長であるDさんはいつものように班員からノートを回収し、ノートを出席番号順に並べ替えようとした。
　Dさんは情報の授業で習った挿入ソートを思い出したので、これを使って並べ替えようとした。教科書を確認すると「挿入ソートとは、既に並び替えが終わっている部分に、新しいノートを正しい位置へ差し込んでいくことで並べ替える方法である。」と書かれていた。

　Dさんはまず、回収したノートの山の一番上を「既に並び替えが終わった部分」と考えた。そして、上から２番目のノートの出席番号と１番上のノートの出席番号を比べて正しい位置に差し込み、この２冊を「並び替えが終わった部分」とした。次に３番目のノートの出席番号を見て、１番目と２番目のノートのどこに差し込めばいいかを確認して適切な位置に差し込んだ。
これを繰り返してノートの山を並べ替えたDさんは、ノートを先生に提出して家に帰った。

挿入ソートを書いてみる

　次の日も、班長であるDさんは班員のノートを回収し、並べ替えていた。Dさんは毎回並び替えの方法を考えるのが面倒だと感じ、アルゴリズムとして図１にまとめた。
　回収したノートに書かれている出席番号を上から順に格納した配列yama（添え字は１から始まる。）は、添え字が上から何番目かを表し、値がそのノートの出席番号を表している。

図１

yama ← {34, 13, 8, 22, 33, 12, 32, 29, 25, 6}
satsusu ← 10
i を 2 から satsusu まで 1 ずつ増やしながら、
|  key ← yama[i]
|  j ← i - 1
|  j が 1 以上 かつ yama[j] > key の間、
|  |  yama[j + 1] ← yama[j]
|  |  j ← j - 1
|  を繰り返す
|  yama[j + 1] ← key
を繰り返す

図１のアルゴリズムにのっとってノートを並べ替えたDさんは、先生にノートを提出して家に帰った。

挿入ソートの計算量について

　別の日もノートを並べ替えていたDさんは、ノートの冊数が変わることで挿入ソートの比較回数や交換回数はどれくらい変わるのかを考えた。「並べ替えが完了した部分」が１冊の場合、比較回数は最大で１回、２冊の場合は、最大で２回、......N-1冊の場合は最大でN-1回となる。そのため、N冊のノートを並べ替えるときは全体で、最悪

1 + 2 + 3 + ・・・ + (N-1) = \frac{N(N-1)}{2}回

かかることになる。つまり、挿入ソートの比較回数はノートの冊数のおよそ２乗に比例して増える。一方で、既にほぼ出席番号順に並んでいる山を並べ替えるときは、ほとんどノートをずらさなくて良いので、少ない回数で並び替えが完了する。
　班長へ出す前に、班員同士である程度ノートを並び替えてくれていたら、並べ替えは楽かもしれない、と思うDさんであった。