はじめに
この記事は 共通テスト手順記述標準言語 (DNCL) Advent Calendar 2025 の１０日目の記事です。
DNCLでカウントソートを書いてみたので、共テ風に書きます。
カウントソートとは
Dさんが所属する４０人のクラスには１０人１組の班がある。班長は毎日、班員のノートを回収し、出席番号順に並び変えた上で担任の先生に提出しなければならない。班長であるDさんは班員のノートをすべて回収した。ノートを出席番号順に並び替えようとしたところで、Dさんは情報の授業で習った カウントソート を思い出したので、これを用いて１０冊のノートを並び替えようとした。
まず初めにDさんは、机の上のどこに何番のノートを置くのかを１番から４０番について図１のように決めた。これは、並べるノートは１０冊だが１０人の出席番号がわからないため、何番であっても並べられるようにするものである。
次にDさんは、集めたノートを上から手に取り、図２のようにノートに書かれた出席番号を見て対応する場所にノートを置いた。
Dさんは最後に、１番の場所から順にノートが置いてあるかを確認し、もしノートがあればかご入れていった。
こうしてノートの並び替えを終えたDさんは先生に班員のノートを提出し家路についた。
カウントソートを書いてみる
次の日、班長であるDさんは昨日と同じようにノートを回収し並べ替えをしていた。Dさんは毎日並べ替える方法を考えるのが面倒だと感じ、ノートを並び替えるアルゴリズムを作成しようと考えた。
各出席番号の位置にノートが置かれているかどうかを管理するために配列Tsukuenoueを用意する。この配列の添え字（１から始まる。）はクラスの出席番号であり、その要素は出席番号に対応する各位置に置かれたノートの冊数である。
例えば、図３の状況では、配列Tsukuenoueは図４のようになる。図３で２番と５番にノートがあるため、図４で要素Tsukuenoue[2]と要素Tsukuenoue[5]はともに１となる。また、３番の位置にはノートがないため、図４で要素Tsukuenoue[3]は０となる。さらに、図４で要素Tsukuenoue[27]は２なので、２７番の人がノートを２冊提出したことがわかる。
この考え方に基づき、Dさんは配列Tsukuenoueと回収したノートの冊数が代入された変数satsusu、ノートに書かれている出席番号を要素にもつ配列Kaisyu（添字は１から始まる。）そしてクラスの人数が代入された変数ninzuを用いて、机の上の出席番号と対応した位置にノートを並べるアルゴリズムを作成した（ここでは、並べた数を記録することを並べるという）（図５）。
（01）Tsukuenoue = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
（02）Kaisyu = [34, 13, 8, 22, 33 ,12, 32, 29, 25, 6, 12]
（03）satsusu = 11
（04）ninzu = 40
（05）iを１からsatsusu + 1まで１ずつ増やしながら繰り返す:
（06）└ Tsukuenoue[Kaisyu[i]] = Tsukuenoue[Kaisyu[i]] + 1
仮に回収したノートの数が変わったとしても、配列Kaisyuと変数satsusuを適切に設定すれば、このアルゴリズムを用いることができる。１２番と１３番のノートがさらに１冊ずつ追加された場合、（02）行目を例えばKaisyu = [34, 13, 8, 22, 33 ,12, 32, 29, 25, 6, 12, 12, 13]に、（03）行目をsatsusu = 13に変更して図５のアルゴリズムを用いると、要素Tsukuenoue[12]は３となる。
次にDさんは、机の上に並べたノートを１番から順に確認し、もしノートがあればかごに入れていくアルゴリズムを作ることにした。
Dさんはかごの中にあるノートの出席番号を記録した配列Kagoを用意する。この配列の添字（１から始まる。）はかごの上から何冊目にあるかを表しており、その要素はノートに書かれた出席番号である。
例えば 要素Kago[1] = 6 であればかごの一番上には６番のノートがあることを表す。
Dさんは最初に０という要素をノートの冊数を表す変数satsusuだけもった配列Kagoを用いて、机の上のノートをかごに入れるアルゴリズムを作成した（図６）。
（01）Tsukuenoue = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
（02）Kaisyu = [34, 13, 8, 22, 33 ,12, 32, 29, 25, 6, 12]
（03）satsusu = 11
（04）ninzu = 40
（05）iを１からsatsusu + 1まで１ずつ増やしながら繰り返す:
（06）└ Tsukuenoue[Kaisyu[i]] = Tsukuenoue[Kaisyu[i]] + 1
（07）kago = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
（08）c = 1
（09）iを１からninzu + 1まで１ずつ増やしながら繰り返す:
（10）| もしTsukuenoue[i] > 0ならば:
（11）| | jを０からTsukuenoue[i]まで１ずつ増やしながら繰り返す:
（12）| | | Kago[c] = i
（13）└ └ └ c = c + 1
Dさんは図６のアルゴリズムを用いてノートを並べ替えた後、ノートを先生に提出し、家に帰った。
カウントソートの計算量
一昨日、昨日とノートをきちんと出席番号順に並べて先生に提出したDさんは、その腕を買われて学年職員室に提出される学年全員のノートを並べ替えるように言われた。実は、ノートをきちんと並べ替えて提出していたのはDさんのクラスのDさんの班だけだったのである。
ノートには組と出席番号のほかに、学籍番号が書かれている。先生から学年全員の３００人分のノートを受け取ったDさんは昨日作ったのアルゴリズムを用いて学籍番号を基準に並べ替えようとした。
昨日のアルゴリズムはノートがＮ冊あるとき、ノートの山を上から下まで１周確認する間に山から机の上にＮ回移動させ、ノートを机の上からかごの中にＮ回移動させるため、およそ２Ｎ回ノートを移動させる必要がある。Dさんは2 * 300より６００回移動させることを考え、すぐに終わると思った。
しかし、昨日はクラスメート４０人分の出席番号に対応する位置を確保するだけでよかったので机の上で行うことができたが、３００人分の学籍番号に対応する位置を机の上で確保することは困難である。悩んだ末、Dさんは教室の机を後ろに下げ、空いた床に３００人分の位置を確保し、ノートを並び替えた。
並び替えを終えたDさんは、教室の机を元に戻し、３００人分のノートを先生に提出した後、「筋トレした方がいいかな」と思いながら家に帰った。