ソートアルゴリズム比較・計算量まとめ｜安定性・特徴一覧

はじめに

ソートアルゴリズムにはたくさんの種類があり、それぞれに計算量・安定性・メモリ使用量・実装の難しさなどの特徴があります。

「結局どれを使えばいいの？」「学校の課題で比較表を作りたい」というニーズに応えるため、本記事では主要なソートアルゴリズム 8 種を一覧で比較します。

各アルゴリズムの詳しい解説や C 言語での実装例、計算量の数式による導出は個別記事にまとめています。

計算量・安定性の比較表

アルゴリズム	平均計算量	最悪計算量	最良計算量	空間計算量	安定	詳細
バブルソート	$O(N^2)$	$O(N^2)$	$O(N)$	$O(1)$	◯	→ 解説
選択ソート	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$	×	→ 解説
挿入ソート	$O(N^2)$	$O(N^2)$	$O(N)$	$O(1)$	◯	→ 解説
シェーカーソート	$O(N^2)$	$O(N^2)$	$O(N)$	$O(1)$	◯	→ 解説
シェルソート	$O(N^{1.25})$ 程度	$O(N^2)$※	$O(N \log N)$	$O(1)$	×	→ 解説
マージソート	$O(N \log N)$	$O(N \log N)$	$O(N \log N)$	$O(N)$	◯	→ 解説
クイックソート	$O(N \log N)$	$O(N^2)$	$O(N \log N)$	$O(\log N)$	×	→ 解説
ヒープソート	$O(N \log N)$	$O(N \log N)$	$O(N \log N)$	$O(1)$	×	→ 解説

※ シェルソートはギャップ列の選び方によって計算量が変わります。表は Shell の元の数列での値です。

用語

• 平均計算量: ランダムな入力に対する平均的な比較回数のオーダー
• 最悪計算量: どんな最悪な入力でもこれ以下に収まるオーダー
• 最良計算量: 既にソート済みなど、最も都合の良い入力でのオーダー
• 空間計算量: 入力配列以外に必要な追加メモリのオーダー
• 安定(stable): 同じ値の要素同士の相対順序がソート後も変わらない性質

各アルゴリズムの特徴

バブルソート(Bubble Sort)

• 隣接する 2 要素を比較して入れ替える操作を繰り返す、最もシンプルなソート
• 教育目的でよく使われるが実用上は遅い
• ほぼ整列済みの配列なら早期終了の最適化で $O(N)$ になる

→ バブルソートの詳しい解説

選択ソート(Selection Sort)

• 未ソート部分から最小値を探して先頭と入れ替える
• 比較回数は常に $\frac{N(N-1)}{2}$ で入力に依存しない
• 交換回数は最大でも $N-1$ 回と少ない
• 安定ではない

→ 選択ソートの詳しい解説

挿入ソート(Insertion Sort)

• ソート済み部分の正しい位置に未ソートの先頭要素を挿入する
• ほぼ整列済みのデータでは非常に高速($O(N)$ に近づく)
• 小規模データやハイブリッドソートの内側で使われる

→ 挿入ソートの詳しい解説

シェーカーソート(Cocktail Shaker Sort)

• バブルソートを左右両方向に走らせる改良版
• 末尾の極小値が先頭付近にあるケースでバブルソートより速い
• 「双方向バブルソート」とも呼ばれる

→ シェーカーソートの詳しい解説

シェルソート(Shell Sort)

• 挿入ソートを「離れた要素」にも適用するように拡張したアルゴリズム
• gap(間隔)を徐々に縮めていくことで遠い要素の交換を効率化
• 実装が短い割に高速で、組み込み環境でも使われる

→ シェルソートの詳しい解説

マージソート(Merge Sort)

• 分割統治法による $O(N \log N)$ ソート
• 安定ソートで、最悪でも $O(N \log N)$ を保証
• 追加メモリ $O(N)$ が必要なのが弱点
• 連結リストとの相性が良い

→ マージソートの詳しい解説

クイックソート(Quick Sort)

• ピボットを基準に分割を再帰する分割統治法
• 平均は $O(N \log N)$ だが、最悪 $O(N^2)$ になることもある
• インプレース・キャッシュ効率が良く、実測では多くの場合最速
• 多くの言語の標準ソートで使われる(introsort としてヒープと併用)

→ クイックソートの詳しい解説

ヒープソート(Heap Sort)

• 二分ヒープというデータ構造を利用した $O(N \log N)$ ソート
• 最悪計算量も $O(N \log N)$、追加メモリ $O(1)$ という安定した性能
• 実測ではクイックソートより遅いが、最悪計算量が要求される場面で活躍

→ ヒープソートの詳しい解説

どれを使うべきか

シーン	おすすめ
学習・教育目的	バブル / 挿入 / 選択
データ数が小さい(数十程度)	挿入ソート
安定性が必要	マージソート
速度重視・一般用途	クイックソート(または標準ライブラリのソート)
最悪計算量を保証したい	マージソート / ヒープソート
メモリ制約が厳しい	ヒープソート / クイックソート(in-place)
ほぼソート済みのデータ	挿入ソート / シェーカーソート

比較計算量の覚え方

ソートの計算量はテストや面接で頻出です。覚え方のコツを 3 つ挙げます。

1. 「単純な 3 つ」は $O(N^2)$: バブル・選択・挿入
2. 「分割統治の 2 つ」は $O(N \log N)$: マージ・クイック
3. 「ヒープを使うやつ」も $O(N \log N)$: ヒープソート

そのうえで例外を覚えます。

• 選択ソートだけは最良計算量も $O(N^2)$(常に全要素を比較するため)
• クイックソートだけは最悪計算量が $O(N^2)$(ピボットの選び方依存)
• マージソートだけは追加メモリ $O(N)$ が必要

まとめ

ソートアルゴリズムは、計算量だけでなく安定性・メモリ使用量・実装の単純さなど、複数の観点で比較する必要があります。

実用上は標準ライブラリのソートを使うのが基本ですが、その内部で使われているアルゴリズムを理解すると、性能特性に関する直感が身につきます。

各アルゴリズムの数式を用いた詳細な計算量解析は、それぞれの個別記事で行っているのでぜひあわせてご覧ください。