ソートはなぜ何種類もあるのか──データが2倍で手間は4倍？比較回数で見るO記法
並べ替えの方法が何種類もあるのは、データの量や並びで速さが変わるからです。選択ソートは個数が2倍で比較が約4倍、マージソートは約2.5倍。O記法を比較回数の実測で読み、使い分けも整理します。
この記事のポイント
- 選択ソートは個数が2倍で比較回数が約4倍、マージソートは約2.5倍
- O記法は細かい係数を無視し、個数が増えたときの増え方の形だけを見る
- 「アルゴリズムを整える」で5つのソートの比較回数を同じデータで比べられる
- Q.
- ソートのアルゴリズムはなぜ何種類もあるの？
- A.
- データの量や並び方、必要なメモリによって、速い方法が変わるからです。たとえばほぼ整列済みのデータは挿入ソートが速く、大量のデータはマージソートのような方法が向きます。どれか1つが常に最良とは言えないため、場面に応じて使い分けます。
名簿を点数の高い順に並べ替える。10人なら、手でも一瞬です。ところが同じ作業を1,000人でやろうとすると、急に途方もなく時間がかかるように感じます。人数は100倍なのに、手間が100倍で済むのか、それとももっと膨らむのか。
結論を先に書きます。
並べ替えの方法によって、データの量が増えたときの手間の増え方が違います。選択ソートは個数が2倍になると比較の回数が約4倍に、マージソートは約2.5倍になります。 増え方が違うので、どの方法を使うかで大量のデータを扱うときの待ち時間が大きく変わります。これが、ソートに何種類もの方法がある理由の核心です。
個数が2倍になると、比較は何倍になるか
実際に数えてみます。このサイトの「アルゴリズムを整える」と同じ数え方（要素どうしを比べる回数を1回と数える）で、ランダムな数字を並べて、個数を倍々にしてみました。
| 個数 | 選択ソート | マージソート |
|---|---|---|
| 10 | 45 | 23 |
| 20 | 190 | 65 |
| 40 | 780 | 170 |
| 80 | 3160 | 417 |
選択ソートは、「残りの中から一番小さいものを探して左端に置く」を繰り返す方法です。比較の回数は、データの並びに関係なく n×(n−1)÷2 で決まります。10個なら45回、20個なら190回。個数が10から20に2倍になると、比較は190÷45で約4.2倍です。20から40では約4.1倍、40から80では約4.05倍と、倍率は4に近づいていきます。
マージソートは、半分に分けてそれぞれ並べてから、整列済みの2つの列を先頭から比べて合わせる方法です。個数が2倍になると、比較は約2.8倍、約2.6倍、約2.5倍と、2倍より少し多い程度で増えます。マージソートの数字は乱数で作った1回分の実測なので、並びが変わると多少ずれます。選択ソートのほうは、毎回同じ数になります。
この「増え方の形」を書き表すのが、O記法です。選択ソートは O(n²)、マージソートは O(n log n) と書きます。O(n²) は個数が2倍で4倍、O(n log n) は2倍より少し多い、という形を表します。
O記法は、細かい数を捨てて形だけを見る
O記法には、約束事があります。細かい係数や足し算の小さな項を無視して、個数が増えたときの増え方の形だけを見るという点です。
選択ソートの比較回数は正確には n(n−1)÷2 ですが、これを O(n²) と書きます。n が大きくなると、n² の部分が圧倒的に効いてくるからです。個数が1,000なら、n² は1,000,000、n log₂n は約9,966です。この差は100倍あまりです。
個数が10のときは、n²が100、n log₂nが約33で、差は小さく見えます。ところが1,000個になると差は大きく開きます。「小さいデータでは違いが目立たないが、大きくなるほど効いてくる」。これがO記法で比べる意味です。
ちなみに、比較で並べ替える方法には、速さの限界があります。10個の並べ方は10!＝3,628,800通りあり、1回の比較で可能性を最大でも半分にしか絞れないので、どんな方法でも、最悪の並びでは少なくとも22回の比較が必要です（log₂(3,628,800)≒21.8の切り上げ）。上の表のマージソートの23回は、この限界にかなり近い数字です。
それでも別の方法が残っている理由
では、いつもマージソートを使えばよいのでしょうか。そうとも言えません。ソートの方法ごとに、得意・不得意があります。
| 方法 | 得意なこと | 弱点・注意点 |
|---|---|---|
| バブルソート | 仕組みが単純。交換がなければ途中で終えられる | 平均・最悪は O(n²) |
| 選択ソート | 交換の回数が少ない（多くても n−1 回） | 比較の回数は並びによらず O(n²) |
| 挿入ソート | ほぼ整列済みのデータでは比較が少ない（最良 O(n)） | 逆順に近いと O(n²) |
| クイックソート | 平均で O(n log n)。作業用の領域が小さい | 基準の選び方が悪いと最悪 O(n²) |
| マージソート | 最悪でも O(n log n)。同じ値の順番を保つ（安定） | 作業用の配列が n 個ぶん必要 |
たとえば、毎日少しずつ追加される名簿を、すでに並んだ状態に差し込むなら、挿入ソートが向いています。メモリが乏しい機器なら、作業用の配列が要らない方法が候補になります。「同点の人は元の名簿順のままにしたい」なら、安定な方法を選びます。
つまり、ソートの方法が何種類もあるのは、データの量・並び・メモリ・安定性という条件が現場ごとに違うからです。実際のプログラミング言語に用意されている並べ替えの機能は、こうした条件を踏まえて、複数の方法を組み合わせて作られていることもあります。
動かして、回数を比べる
文章だけだと実感しにくいので、同じデータで5つの方法を動かして、比較の回数を見比べてみてください。アルゴリズムを整えるは、バブル・選択・挿入・クイック・マージの5つを棒グラフで1手ずつ動かし、比較と交換の回数を並べて表示します。データを「ほぼ整列済み」「逆順」「同じ値が多い」に変えると、得意な方法が入れ替わる様子も見えます。
基本情報技術者試験で O 記法を聞かれても、やることは同じです。「個数が2倍になったら、手間は何倍か」を考えます。2倍なら O(n)、4倍なら O(n²)、2倍より少し多いなら O(n log n)。その見当がつけば、まず困りません。
