ソートアルゴリズム比較 — バブルソート・マージソート・クイックソート

ソートアルゴリズムは、同じ要素を小さい順から大きい順のように、決まった順序へ並べ替える方法です。先に短く答えるなら、バブルソートは単純ですが大きなリストにはたいてい遅すぎて、マージソートは安定して $O(n \log n)$ の性能を出し、クイックソートは分割がある程度バランスよく行われると実用上とても高速です。

大事なのは「どのソートが最強か？」ではなく、「どんな条件で最適か？」という問いです。バブルソートは局所的な交換を学ぶのに向いており、マージソートは分割統治をはっきり示し、クイックソートは最悪時の保証がなくても平均的には速くなりうる理由を教えてくれます。

ソートアルゴリズムがすること

たとえば $[5, 1, 4, 2]$ のようなリストが与えられたとき、アルゴリズムは同じ値を順番に並べて返す必要があります。

$$[1, 2, 4, 5]$$

一見すると簡単そうですが、アルゴリズムごとにそこへ到達する方法はかなり異なります。主な違いは次のとおりです。

• 要素をどう動かすか
• 比較や交換をどれくらい使う傾向があるか
• 追加のメモリをどれくらい必要とするか
• 入力の悪いパターンにどれくらい弱いか

バブルソート: 隣同士を何度も交換する

バブルソートはリストを順に見ていき、順序が逆になっている隣接要素を交換します。1回最後まで走査すると、未整列部分の中で最大の要素が末尾まで「浮かび上がり」ます。

$[5, 1, 4, 2]$ では、最初の1周は次のようになります。

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

その後、交換が不要になるまで、残りの未整列部分に対して同じことを繰り返します。

バブルソートは主に学習用として役立ちます。一般に時間計算量は $O(n^2)$ なので、リストが大きくなると比較回数は急速に増えます。教室での小さな例なら問題ありませんが、本格的なソート処理では通常あまり適した選択ではありません。

マージソート: 分割して整列し、最後にマージする

マージソートは分割統治の考え方を使います。リストをより小さな部分に分け、それぞれを整列し、最後に整列済みの部分をまとめていきます。

$[5, 1, 4, 2]$ なら、わかりやすく書くと次のようになります。

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

それぞれの半分を整列します。

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

そして、2つの整列済み部分をマージします。

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

マージソートの大きな強みは予測しやすさです。通常の解析では、実行時間は平均だけでなく $O(n \log n)$ になります。主なコストはメモリで、配列ベースの一般的な実装ではマージ時に追加領域を使います。

クイックソート: ピボットを基準に分割する

クイックソートも分割統治を使いますが、やり方は異なります。ピボットを1つ選び、それより小さい要素を片側に、大きい要素を反対側に置き、その後で両側を再帰的に整列します。

$[5, 1, 4, 2]$ に対してピボットを $4$ にすると、分割の一例は次のようになります。

$$[1, 2] \;|\; 4 \;|\; [5]$$

こうすると左右の部分はかなり小さくなるので、残りの整列はすぐ終わります。

クイックソートが実用上よく速いのは、多くの実装がその場で分割を行い、ピボットがうまくリストを分ければ問題サイズを素早く小さくできるからです。ただし、この条件は重要です。もしピボットの選び方が何度も悪く、片側が極端に小さく、もう片側がほぼ全部という状態が続くと、最悪計算量は $O(n^2)$ になります。

バブルソート vs マージソート vs クイックソート

アルゴリズム	基本の考え方	典型的な時間	最悪時間	追加メモリ
バブルソート	隣接要素を繰り返し交換	$O(n^2)$	$O(n^2)$	少ない
マージソート	分割し、半分ずつ整列してマージ	$O(n \log n)$	$O(n \log n)$	一般的な配列実装では多め
クイックソート	ピボットを基準に分割	多くの場合 $O(n \log n)$	$O(n^2)$	マージソートより少ないことが多い

実用面で1つだけ覚えるなら、こうです。バブルソートは学習用のアルゴリズム、マージソートは安定して予測しやすい選択肢、クイックソートはピボット処理がうまい実装なら実用上の速度で有力な選択肢です。

同じリストで見る1つの具体例

同じリストを使います。

$$[5, 1, 4, 2]$$

バブルソートは局所的な順序の乱れを少しずつ直していきます。全体構造を一度に見ているわけではないので、何回も走査が必要になることがあります。

マージソートはまず問題を小さな整列済み部分に分け、その後でそれらを結合します。この構造こそが、リストが大きくなっても性能が安定しやすい理由です。

クイックソートは早い段階で強い分割を作ろうとします。分割が十分にバランスしていれば、その後の作業量は急速に小さくなります。

だからこそ、学生は1つのリストが各手法でどう動くかを見ると、計算量の数字を覚えやすくなります。数字はただのラベルではありません。アルゴリズムがどう無秩序を減らしていくかを表しています。

ソートアルゴリズム比較でよくある間違い

クイックソートは常に最速だと思い込む

クイックソートは実用上速いことが多いのであって、どんな場合でも最速と保証されているわけではありません。ピボットの振る舞いが悪いと大きく性能を落とします。

$O(n \log n)$ のアルゴリズムを同じものとして扱う

マージソートとクイックソートは平均的な増え方が同じでも、メモリ使用量、最悪時の保証、実装上の細部では同じではありません。

書きやすいからという理由でバブルソートを使う

コードが書きやすいことと、用途に合っていることは別です。小さなデモならバブルソートで十分ですが、より大きな実際の入力では、たいてい不要な作業が多くなります。

入力モデルを忘れる

こうした比較は通常、一般的な入力に対する比較ベースのソートを前提にしています。もしデータに特別な構造があるなら、計数ソートのような非比較ソートによって判断がまったく変わることがあります。

それぞれのソートアルゴリズムはいつ使うか

バブルソートは主に、学習、手順の追跡、ごく小さな例で、性能よりわかりやすさを重視するときに使われます。

マージソートは、一貫した $O(n \log n)$ の挙動が重要で、追加メモリを許容できるときに使われます。実装によっては、連結リストや安定ソートが重要な場面にも自然に適しています。

クイックソートは、実用上の速度が重要で、実装に良いピボット戦略や保護策があるときに使われます。多くの標準ライブラリのソート戦略は、教科書どおりの単純な版ではなく、クイックソートの考え方に安全策を組み合わせています。

違いをすばやく覚える方法

動きで覚えるとよいです。

• バブルソートは隣同士を直す
• マージソートは整列済みの半分を作る
• クイックソートはピボットを中心に分ける

このイメージは、3つの名前と3つの式を丸暗記するより役に立ちます。

自分でも試してみよう

リスト $[7, 3, 6, 1]$ を使って、バブルソートの1回の走査、マージソートの1回の分割とマージ、クイックソートの1回のピボット分割をたどってみてください。各場合でリストの変化の仕方がなぜ違うのか説明できれば、概念はしっかりつかめています。