前のページ 1/5 次のページ

ソート(sort)は、データの集合を一定の規則に従って並べることである。日本語では整列(せいれつ)と訳される。(以前は分類と訳していた時もあったが、この訳は間違いであり、もう使われていない。)

主にコンピュータソフトにおけるリストに表示するデータに対し、全順序関係を定義して一列に並べることを指す。また、単に「ソート」といった場合、値の小さい順に並べる昇順(しょうじゅん/ascending order)を指すことが多い。また、その反対に値を大きい順から並べることを降順(こうじゅん/descending order)という。

対象となるデータのデータ構造や、必要な出力によって使われるアルゴリズムは異なる。

◆ 概要

効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム(探索やマージ)の最適化にとっても重要である。また、ソートされたデータの方が人間にとっても読みやすい。形式的には、その出力は以下の2つの条件を満たさなければならない。

# 設定された順序(大抵昇順or降順)に対して、逆になるような順序の出力があってはならない。

# 出力は入力の並べ替えでなければならない。

情報工学や計算機科学の黎明期から、ソートは単純な問題でありながら効率的に解くことが難しく、そのためもあって盛んに研究されてきた。例えばバブルソートについては、早くも1956年には解析が行われている[外部リンク] Bubble Sort: An Archaeological Algorithmic Analysis Owen Astrachan。多くの人は既に解決済みの問題と考えているが、現在も新たなソートアルゴリズムが発明されている(例えば、ライブラリソートが最初に発表されたのは2004年である)。様々なアルゴリズムがあり、アルゴリズムという概念を学習するのに最適であるため、情報工学や計算機科学での入門的題材として広く親しまれている。それには例えば、O記法、分割統治法、データ構造、乱択アルゴリズム、計算量解析、時間と空間のトレードオフ、下限などが含まれる。

◆ ソートアルゴリズムの分類

計算機科学では、ソートアルゴリズムを次のように分類する。

・ 入力されるリストの項目数(n)に基づいた計算量による分類。典型的なソートアルゴリズムでは、最善で O(n log n)、最悪で Ω(n²) である。理想は O(n) である。抽象キーの比較演算のみを使うソートアルゴリズムでは、最悪で Ω(n log n) の比較が必要となる。

・ In-placeアルゴリズムの場合、スワップ回数で計算量を求め、それによって分類する。

・ メモリ使用量(およびその他の計算資源の使用量)による分類。一部のソートアルゴリズムはIn-placeであるため、入力リストの格納域以外には O(1) または O(log n) の領域しか必要としない。これを内部ソートと呼ぶ。一方、他のアルゴリズムではデータを一時的に記憶しておく領域が必要である。これを外部ソートと呼ぶ。

・ 再帰の有無による分類。一部のアルゴリズムは再帰が必須だったり、再帰不可能だったりするが、それ以外はどちらでも実装可能である(例えばマージソート)。

・ 安定性の有無。安定ソート参照。

・ 比較ソートか否か。比較ソートでは、2つの個々の項目を比較演算で大小判定することを基本とする。比較ソートには後述するが存在する。

・ 汎用手法による分類。挿入、交換、選択、マージなどがある。交換ソートにはバブルソートやクイックソートが含まれる。選択ソートにはシェーカーソートやヒープソートが含まれる。

◆ソートアルゴリズムの一覧

配列に格納されたn個のデータをソートする場合について、各アルゴリズムの性能を示す。

計算時間の表記に用いている記号 O についてはランダウの記号を参照。

以下の表で、n はソートすべきデータ要素数である。平均実行時間と最悪実行時間は時間計算量を示している。このとき、ソートキーの長さは一定と仮定しており、比較や交換といった操作は定数時間で行われるとする。メモリ使用量は、入力データの格納域以外に必要となる領域を示している。これらは、いずれも比較ソートである。