整列アルゴリズム（ソート）

背景・歴史

データを大きさの順や五十音順に並べ替える「整列（ソート）」は、コンピュータサイエンスの初期から、簡単そうに見えて効率よく解くのが難しい代表的な問題として盛んに研究されてきました。最も単純な考え方の一つである「バブルソート」は、すでに1956年には性能の分析が行われていたと言われています。その後も、より効率的な整列方法が次々と考案され、21世紀に入ってからも新しい整列アルゴリズム（2002年のTimsortなど）が開発され続けています。

なぜこの考え方が使われるようになったのか

データが整列されていると、後から目的のデータを探す（探索する）作業が格段に効率よく行えるようになります。例えば、辞書の言葉が五十音順に並んでいなければ、目的の言葉を探すのに非常に時間がかかってしまいます。また、ランキング形式でデータを表示したり、統計的な分析を行ったりする際にも、データがあらかじめ整列されていることが前提になる場面が多くあります。こうした理由から、整列は多くのプログラムで欠かせない基本的な処理として扱われています。

もう少し詳しく見てみる

代表的な整列アルゴリズムには、次のようなものがあります。

• バブルソート：隣り合う要素を比較し、順番が逆であれば入れ替える、という操作を繰り返す、理解しやすいが効率はあまり良くない方法。
• 選択ソート：まだ並べ終えていない部分から最小（または最大）の値を選び、順番に並べていく方法。
• クイックソート・マージソート：データを分割して整列し、それらを組み合わせることで、大量のデータでも高速に整列できる、実用的によく使われる方法。

どの整列アルゴリズムを使うかによって、扱うデータの量が増えたときにかかる時間が大きく変わります。単純な方法は理解しやすい一方、データ量が多くなると時間がかかりすぎることがあるため、実際のソフトウェアでは、より効率の良い整列アルゴリズムが使われています。

関連して知っておきたいこと

整列アルゴリズムの効率の違いは、計算量という考え方を使って比較されます。また、整列されたデータに対しては二分探索のような効率的な探索方法が使えるようになるため、整列と探索は密接に関係しあうアルゴリズムの分野です。