はじめに
この記事は 共通テスト手順記述標準言語 (DNCL) Advent Calendar 2025 の５日目の記事です。
クイックソートとは
Dさんが所属する40人のクラスには、10人1組の班がある。班長は毎日、班員のノートを回収し、出席番号順に並べ替えた上で担任の先生に提出しなければならない。
班長であるDさんは、いつものように班員10人分のノートを回収したが、出席番号の順番はばらばらである。Dさんは情報の授業で学んだクイックソートを使えば、効率よくノートを出席番号順に並べ替えられるのではないかと考えた。
Dさんはまず、ノートの山の中から1冊を選び、そのノートに書かれた出席番号を基準として使うことにした。この基準となる出席番号を基準値と呼ぶことにする。
次にDさんは残りのノートを順に確認し、「基準値より小さい出席番号のノート」と「基準値以上の出席番号のノート」の２つの山に分けた。これらの山を「基準値より小さい出席番号のノートの山」「基準値としたノート」「基準値以上の出席番号のノートの山」の順に並べれば、全体がおおよそ出席番号順に並んでいると見ることができる。さらに、２つの山にもそれぞれに基準値となるノートを決め、各山を２つの山に分けて並べ替える。
この操作を繰り返してノートを出席番号順に並べ替えたDさんは、先生にノートを提出した後、家に帰った。
クイックソートを書いてみる
次の日、班長であるDさんは昨日と同じようにノートを回収し並べ替えていた。Dさんは毎日並べ替える方法を考えるのが面倒に感じ、ノートを並べ替えるアルゴリズムを作成しようと考え、図１のアルゴリズムを作った。
ノートの山に書かれた出席番号を要素に持つ配列yamaを用いる。また、並べ替えを行う範囲の左端をl、右端をrで指定することにする。
関数 クイックソート(yama, l, r)を
| もし l < r ならば
| | pivot ← yama[l]
| | i ← l + 1
| | j ← r
| |
| | i <= j の間繰り返す
| | | もし yama[i] < pivot ならば
| | | | i ← i + 1
| | | そうでなく もし yama[j] ≥ pivot ならば
| | | | j ← j - 1
| | | そうでなければ
| | | | temp ← yama[i]
| | | | yama[i] ← yama[j]
| | | | yama[j] ← temp
| | | | i ← i + 1
| | | | j ← j - 1
| | | を実行する
| | を繰り返す
| |
| | temp ← yama[l]
| | yama[l] ← yama[j]
| | yama[j] ← temp
| | クイックソート(yama, l, j - 1)
| | クイックソート(yama, j + 1, r)
| を実行する
と定義する
yama ← {34, 13, 8, 22, 33, 12, 32, 29, 25, 6}
satsusu ← 10
クイックソート(yama, 0, satsusu - 1)
図１のアルゴリズムを使ってノートを並び替えたDさんは、先生にノートを提出した後、家に帰った。
クイックソートの計算量について
数日後Dさんは学年全体のノートを並べ替える手伝いを頼まれた。学年には３００人の生徒がおり、ノートの冊数も３００冊と多い。
クイックソートでは、基準値を用いてノートを２つの山に分け、その後それぞれの山を同じように２つに分けていき並べ替える。うまく分割できると１回の分割で全体をほぼ半分ずつに分けることができる。この時、
- １回の分割でノートをおよそN回確認する
- 分割の回数はおよそlog2N回
となるため、全体の比較回数はおよそNlog2Nとなる。一方で、基準値の選び方が偏り、毎回ほとんど半分に分けられなかった場合には、比較回数はおよそN2に近づく。
クイックソートは基準値の選び方によって比較回数が大きく変わってしまうことを理解したうえで、Dさんはノートを並び替えて先生に提出した。