データ構造のソート（並べ替え）アルゴリズム徹底比較：計算量と分類の基礎

ソート（並べ替え）アルゴリズムには200種類以上の手法が存在します。本記事では、その中から代表的な手法を厳選し、それぞれの特徴や時間計算量を比較して解説します。ソートの手法は、大きく分けて「比較ベースのソート」と「非比較ベースのソート」の2つに分類できます。

比較ベースのソートとは

バブルソート、選択ソート、挿入ソート、マージソート、クイックソート、ヒープソートなどが、代表的な比較ベースのソートです。これらが「比較ソート」と呼ばれる理由は、要素同士の値を比較しながら、複数のフェーズ（パス）を経て順番に並べていく仕組みだからです。以下の表に、各アルゴリズムの時間計算量をまとめました。

非比較ベースのソートとは

一方、基数ソート（ラディックスソート）、バケットソート、計数ソート（カウンティングソート）などは、非比較ベースのアルゴリズムに分類されます。これらは、ソートの過程で2つの要素を直接比較することなく並べ替えを行う点が大きな特徴で、比較ソートとは仕組みが根本的に異なります。以下に、解析の種類ごとの計算量の違いを示します。

その他の観点からのソート分類

インプレースソートとアウトオブプレースソート

ソートアルゴリズムは、追加のメモリ使用量によっても分類できます。ソート処理のために余分な記憶領域を必要としないものは「インプレース（in-place）ソート」と呼ばれます。クイックソートやヒープソートがその代表例です。一方、マージソートは統合時に一時的な作業配列が必要となるため、「アウトオブプレース（out-place）ソート」に分類されます。

オンラインソートとオフラインソート

また、ソート処理の実行中に新しい要素を受け入れられるかどうかという観点もあります。処理の途中で新たな要素を追加し、それを適切な位置に組み込めるアルゴリズムは「オンラインソート」と呼ばれます。前述の手法の中では、挿入ソートがオンラインソートの代表例です。

まとめ

このように、ソートアルゴリズムは時間計算量だけでなく、メモリ効率や逐次的な入力への対応可否など、さまざまな観点から評価できます。データ量やメモリ制約、入力の与えられ方などの条件に応じて、最適なアルゴリズムを使い分けることが重要です。