なぜソートアルゴリズムを知るべきか？
ソートはコンピュータサイエンスにおいて最も基本的かつ重要な操作です。データベースクエリ、検索エンジン、レコメンドシステムなど、ほぼすべてのソフトウェアでソートが使用されています。コーディングテストでもソートは必須テーマであり、ソートアルゴリズムを理解すれば、分割統治法、ヒープ、安定性といった核心概念も自然に身につきます。
この記事では、最もよく使われる7つのソートアルゴリズムを時間計算量、安定性、空間計算量の観点から比較し、それぞれの動作原理を説明します。
一目で比較
| アルゴリズム | 最良 | 平均 | 最悪 | 空間 | 安定性 |
|---|---|---|---|---|---|
| バブルソート | O(n) | O(n²) | O(n²) | O(1) | 安定 |
| 挿入ソート | O(n) | O(n²) | O(n²) | O(1) | 安定 |
| 選択ソート | O(n²) | O(n²) | O(n²) | O(1) | 不安定 |
| マージソート | O(n log n) | O(n log n) | O(n log n) | O(n) | 安定 |
| クイックソート | O(n log n) | O(n log n) | O(n²) | O(log n) | 不安定 |
| ヒープソート | O(n log n) | O(n log n) | O(n log n) | O(1) | 不安定 |
| カウンティングソート | O(n+k) | O(n+k) | O(n+k) | O(k) | 安定 |
1. バブルソート（Bubble Sort）
隣接する2つの要素を比較し、順序が間違っていれば交換する方式です。泡が浮かび上がるように、大きな値が配列の末尾に移動していきます。
動作原理：
- •配列の先頭から末尾まで隣接要素を比較
- •順序が間違っていれば交換
- •1回の走査ごとに最大の未整列要素が正しい位置に移動
- •交換がなくなるまで繰り返す
時間計算量： 最良 O(n)、平均・最悪 O(n²)
実装が単純で教育目的でよく使われますが、性能の問題から実務ではほとんど使われません。
2. 挿入ソート（Insertion Sort）
カードゲームで手札を整理する方法と同じです。新しい要素を、すでに整列された部分の適切な位置に挿入します。
動作原理：
- •2番目の要素から開始
- •現在の要素を整列済み部分と比較
- •適切な位置を見つけて挿入
- •すべての要素に対して繰り返す
時間計算量： 最良 O(n)、平均・最悪 O(n²)
ほぼ整列されたデータに対して非常に効率的で、小規模データセットでは実際に高速です。JavaのArrays.sort()は小さな配列に対して挿入ソートを使用しています。
3. 選択ソート（Selection Sort）
配列から最小値を見つけ、先頭と交換する過程を繰り返します。
動作原理：
- •未整列部分から最小値を探す
- •未整列部分の先頭要素と交換
- •整列済み部分のサイズを1増やす
- •すべての要素が整列されるまで繰り返す
時間計算量： 常に O(n²)
交換回数がO(n)と少ない利点がありますが、比較回数が常にO(n²)のため、データの状態に関係なく遅いです。
4. マージソート（Merge Sort）
分割統治法（Divide and Conquer）の代表的な例です。配列を半分に分け、それぞれを整列し、統合する過程を再帰的に行います。
動作原理：
- •配列を半分に分割（Divide）
- •各部分配列を再帰的に整列（Conquer）
- •整列された2つの部分配列を1つに統合（Merge）
時間計算量： 常に O(n log n)
安定的で予測可能な性能を保証します。追加メモリO(n)が必要という欠点がありますが、連結リストのソートではO(1)の追加空間で実装可能です。
5. クイックソート（Quick Sort）
ピボットを基準に小さい値と大きい値を分離する分割統治アルゴリズムです。実務で最もよく使われるソートアルゴリズムの一つです。
動作原理：
- •ピボット要素を選択
- •ピボットより小さい要素は左、大きい要素は右に分割
- •各部分を再帰的に整列
時間計算量： 最良・平均 O(n log n)、最悪 O(n²)
平均的に最も高速な汎用ソートアルゴリズムです。キャッシュ効率が良く、インプレースソートが可能です。ピボット選択戦略により最悪のケースを回避できます。
6. ヒープソート（Heap Sort）
最大ヒープ（または最小ヒープ）データ構造を利用したソートです。ヒープから最大値を取り出す過程を繰り返します。
動作原理：
- •配列を最大ヒープに変換（Build Heap）
- •ヒープのルート（最大値）を配列末尾に移動
- •ヒープサイズを縮小し、ヒープ特性を復元（Heapify）
- •ヒープが空になるまで繰り返す
時間計算量： 常に O(n log n)
追加メモリなしでO(n log n)を保証します。優先度キューと密接に関連しており、ヒープソートを理解すれば優先度キューの問題も簡単に解けるようになります。
7. カウンティングソート（Counting Sort）
比較ベースではないソートアルゴリズムです。各値の出現回数を数えて整列します。
動作原理：
- •各値の出現回数をカウント配列に格納
- •カウント配列の累積和を計算
- •元の配列を逆順に走査し、正しい位置に配置
時間計算量： O(n + k)、kは値の範囲
値の範囲(k)が要素数(n)に比べて大きくない場合に非常に効率的です。O(n log n)の限界を超える線形時間ソートが可能です。
どの状況でどのソート？
ほぼ整列されたデータ → 挿入ソート
- •最良の場合O(n)で非常に高速です。
安定性が必要な場合 → マージソート
- •同じ値の相対的な順序が保証されます。
平均的に最も高速 → クイックソート
- •キャッシュ効率が良く、実務で最もよく使われます。
メモリ制限がある場合 → ヒープソート
- •追加メモリO(1)でO(n log n)を保証します。
値の範囲が限定的な場合 → カウンティングソート
- •線形時間O(n+k)でソート可能です。
AlgoNoteで直接確認しましょう
文章で読むだけでなく、目で見れば理解がはるかに早くなります。AlgoNoteでは各ソートアルゴリズムが一段階ずつどのように動作するか視覚的に確認できます。速度を調整し、データを変えながら実験してみてください。