はじめに
この記事は 共通テスト手順記述標準言語 (DNCL) Advent Calendar 2025 の１日目の記事です。
選択ソートとは
Dさんが所属する４０人クラスには１０人１組の班がある。班長は毎日、班員のノートを回収し、出席番号順に並べ変えた上で担任の先生に提出しなければならない。班長であるDさんは班員のノートをすべて回収した。そしてノートの山を並べ替えようとした。
まず初めにDさんは１０冊すべての出席番号を確認し、出席番号が最も小さいノートを山の一番上に移動させた。次に、残りの９冊すべての番号を確認し、その中で出席番号が最も小さいノートを一番上のノートの次に移動させた。
これを繰り返して上から出席番号が小さくなるように並べ替えたDさんは先生に班員のノートを提出し家に帰った。
選択ソートを書いてみる
次の日、班長であるDさんは昨日と同じようにノートを回収し並べ替えていた。Dさんは毎日並べ替える方法を考えるのが面倒に感じ、ノートを並べ替えるアルゴリズムを作成しようと考えた。
yama ← {34, 13, 8, 22, 33 ,12, 32, 29, 25, 6}
satsusu ← 10
i を0から satsusu - 2 まで1ずつ増やしながら、
| j を i+1 から satsusu - 1 まで1ずつ増やしながら、
| | もし yama[i] > yama[j] ならば
| | | temp ← yama[i]
| | | yama[i] ← yama[j]
| | | yama[j] ← temp
| | を実行する
| を繰り返す
を繰り返す
図１のアルゴリズムを作成したDさんはノートの山の上から i 番目が一番大きい出席番号のときは、i 番目より下のノートと毎回入れ替えないといけないことに気づいた。ノートを毎回交換するのは大変なので上から i 番目にふさわしい、最小の出席番号のノートの位置ichiを記憶して、山を一通り確認してから i 番目とichi番目を入れ替えることにした。
yama ← {34, 13, 8, 22, 33 ,12, 32, 29, 25, 6}
satsusu ← 10
i を0から satsusu - 2 まで1ずつ増やしながら、
| ichi ← i
| j を i+1 から satsusu - 1 まで1ずつ増やしながら、
| | もし yama[ichi] > yama[j] ならば
| | | ichi ← j
| | を実行する
| を繰り返す
|
| temp ← yama[i]
| yama[i] ← yama[ichi]
| yama[ichi] ← temp
を繰り返す
Dさんは図２のアルゴリズムを用いてノートを並べ替えた後、ノートを先生に提出し、家に帰った。
選択ソートの計算量について
翌日もノートを並べ替えていたDさんは、より効率のいい並べ替え方はないだろうかと考えていた。というのも、選択ソートではまだ順番が決まっていないすべてのノートの出席番号を確認した上で最小の番号のノートを上に移動させる。N冊のノートを並べ替えるときに、１番上を決定するにはN冊、２番目を決定するにはN-1冊、３番めを決定するにはN-2冊......というように全体で
(N-1) + (N-2) + ・・・ + 1 = \frac{N(N-1)}{2}回
ノートを確認することになるため、出席番号の比較回数はノートの冊数のおよそ２乗に比例して増えていくのだ。