はじめに
この記事は 共通テスト手順記述標準言語 (DNCL) Advent Calendar 2025 の２日目の記事です。
バブルソートとは
Dさんが所属する４０人クラスには１０人１組の班がある。班長は毎日、班員のノートを回収し、出席番号順に並べ替えたうえで担任の先生に提出しなければならない。班長であるDさんは班員のノートをすべて回収した。そしてノートの山を並び替えようとした。
まず初めにDさんはノートの山を上から順に、隣り合う２冊同士の出席番号を比較していった。２冊のうち上にあるノートの出席番号が大きければ２冊を入れ替え、上のノートの番号が小さければ入れ替えずに次の２冊を比較した。この操作を山の上から下まで順に行うと、一番下に出席番号の大きいノートが移動してきた。
次に、もう一度上から順に隣り合う２冊同士の出席番号を比較して、上のノートの出席番号が大きければ２冊を入れ替えた。下から２冊目までを確認すると、２番目に番号の大きいノートが下から２冊目に移動した。
これを繰り返してノートを並べ替えたDさんは先生にノートを提出して家に帰った。
バブルソートを書いてみる
次の日、班長であるDさんは昨日と同じようにノートを回収し並べ替えていた。Dさんは毎日並べ替えの方法を考えるのが面倒に感じ、ノートを並べ替えるアルゴリズムを作ろうとした。
yama ← {34, 13, 8, 22, 33, 12, 32, 29, 25, 6}
satsusu ← 10
i を1からsatsusu - 1まで1ずつ増やしながら、
| jを0から satsusu - i - 1 まで1ずつ増やしながら、
| | もしyama[j] > yama[j+1]ならば
| | | temp ← yama[j]
| | | yama[j] ← yama[j+1]
| | | yama[j+1] ← temp
| | を実行する
| を繰り返す
を繰り返す
図１のアルゴリズムを使ってノートを並べ替えたDさんは、偶然にもノートが最初から出席番号順に並んでいたのに、ノートの山を上から下まで何回も確認したことを無駄に感じ、図１のアルゴリズムを改良したいと思った。
Dさんは上から順に２冊の出席番号を比べる時に入れ替えた回数を記憶して、１周比べ終えた時に並べ替えた回数が０回なら、ノートの山は並べ替えが完了していると判断することにした。この考えを元にDさんは図２のようなアルゴリズムを作成した。
yama ← {34, 13, 8, 22, 33, 12, 32, 29, 25, 6}
satsusu ← 10
i を1からsatsusu - 1まで1ずつ増やしながら、
| kaisu ← 0
|
| jを0から satsusu - i - 1 まで1ずつ増やしながら、
| | もしyama[j] > yama[j+1]ならば
| | | temp ← yama[j]
| | | yama[j] ← yama[j+1]
| | | yama[j+1] ← temp
| | | kaisu ← kaisu + 1
| | を実行する
| を繰り返す
|
| もし kaisu == 0 ならば
| | 繰り返しを抜ける
| を実行する
を繰り返す
図２のアルゴリズムを用いてノートを並べ替えたDさんは、先生にノートを提出して、家に帰った。
バブルソートの計算量について
次の日もノートを並べ替えていたDさんは、このバブルソートでは最悪で何回並べ替えないといけないのかが気になった。ノートをN冊並べ替えるときを考えると１周目にノートの山を上から下まで確認するのはN-1回、これで一番下に出席番号の大きいノートが移動する。２周目にノートを確認するのはN-2回、これで下から２番目に出席番号が２番目に大きいノートが移動する。３周目にはN-3回、......N-1周目には１回確認するので、全体で
(N-1) + (N-2) + (N-3) + ・・・ + 1 = \frac{N(N-1)}{2}回
確認することになる。つまり、ノートの冊数のおよそ２乗に比例して最悪の比較回数は増えていくのだ。