ソートアルゴリズム入門 — 計算量で選ぶ7つの並べ替え手法

「データを並べ替える」というありふれた処理にも、数多くのアルゴリズムが存在します。それぞれ得意・不得意があり、扱うデータ量や性質によって最適な選択は変わります。本記事では代表的な7手法を、計算量という共通のものさしで整理します。

計算量（オーダー記法）とは

アルゴリズムの速さを比較するとき、実行時間そのものではなく「データ件数 n が増えたときに、処理量がどう増えるか」で評価します。これをオーダー記法（O記法）と呼びます。

アルゴリズム	平均計算量	最悪計算量	安定性	特徴
バブルソート	`O(n²)`	`O(n²)`	安定	隣接交換を繰り返す。理解しやすいが遅い。
選択ソート	`O(n²)`	`O(n²)`	不安定	最小値を選んで先頭へ。交換回数が少ない。
挿入ソート	`O(n²)`	`O(n²)`	安定	ほぼ整列済みのデータに非常に強い。
シェルソート	約`O(n^1.3)`	`O(n²)`	不安定	挿入ソートを離れた間隔で改良。
マージソート	`O(n log n)`	`O(n log n)`	安定	分割統治。最悪でも安定して速い。
クイックソート	`O(n log n)`	`O(n²)`	不安定	実用上は最速級。ピボット選択が肝。
ヒープソート	`O(n log n)`	`O(n log n)`	不安定	追加メモリ不要で最悪も保証。

安定ソート（stable sort）とは、同じ値の要素どうしの元の順序が保たれる性質を指します。たとえば「点数が同じなら登録順を維持したい」といった場面で重要になります。

マージソートは、データを半分ずつに分割し、整列済みの小さな列を併合（マージ）しながら全体を整えます。常に O(n log n) を保証する一方、併合用の追加メモリを必要とします。

クイックソートは、基準値（ピボット）より小さい / 大きいグループに分けて再帰的に整列します。平均的には極めて高速ですが、ピボット選びが偏ると最悪 O(n²) に陥ります。多くの標準ライブラリは、両者やヒープソートを組み合わせたハイブリッド方式を採用しています。

実務での結論： 自前実装より、まずは言語標準の sort を使うのが基本です（多くが最適化済み）。アルゴリズムの理解は、データ量の見積もりやボトルネック分析、面接対策、そして「なぜ遅いのか」を説明できる力につながります。

ソートアルゴリズムは、計算量・安定性・メモリ使用量という複数の軸で評価されます。「速いソート」が常に最適とは限らず、データの性質と要件に応じた選択が重要です。まずは挙動を実際に目で見て、それぞれの個性をつかむことから始めてみてください。

計算量（オーダー記法）とは何ですか？

アルゴリズムの速さを実行時間そのものではなく、データ件数 n が増えたときに処理量がどう増えるかで評価する考え方です。O(n²) は n が10倍になると処理が約100倍に増え、O(n log n) は実用的な高速ソートの目安、O(n) はデータ件数に比例する評価を表します。

安定ソート（stable sort）とは何ですか？

同じ値の要素どうしの元の順序が保たれる性質を持つソートのことです。たとえば「点数が同じなら登録順を維持したい」といった場面で重要になります。バブルソート・挿入ソート・マージソートは安定、選択ソート・クイックソート・ヒープソートは不安定です。

用途に応じてどのソートを選べばよいですか？

件数が少ない／ほぼ整列済みなら挿入ソート、同値の順序保持など安定性が必要ならマージソート、平均性能重視でとにかく速くしたいならクイックソート、メモリが厳しく最悪性能の保証が欲しいならヒープソートが向いています。実務ではまず言語標準の sort を使うのが基本です。