アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)

ソートアルゴリズムとは

データの集合を大小関係等の規則によって整列させるアルゴリズムを指します。プログラミングにおいてデータのソートは非常に重要で頻繁に使われます。そのため長い年月をかけて、様々なアルゴリズムが研究されています。

前述のとおりソートアルゴリズムは様々な種類がありますが、代表的なものからいくつかを紹介していこうと思います。紹介するソートアルゴリズムは以下の通りです。

• バブルソート
• 選択ソート
• 挿入ソート
• シェルソート
• クイックソート
• マージソート
• ヒープソート
• バケットソート
• 基数ソート

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

ソートアルゴリズムはいくつかの方法で分類することができます。

安定ソート

安定ソートとは、同等なデータについて、ソート前の順序がソート後も保持されるソートアルゴリズムを指します。

例えば、氏名と年齢からなる以下のようなデータについて考えます。

ソート前のデータ

年齢昇順でソートすると、「山田」「佐藤」の年齢が25で同じデータですが、ソート後の順序はどのようになるでしょうか。このような場合にソート前の順序「山田」「佐藤」の順で並ぶことが保証されるソートを、安定ソートと呼びます。

安定ソート後のデータ

内部ソート/外部ソート

ソートを実行する際に、ソート対象のデータの格納領域以外に、O(1) か O(log n) の領域しか必要としないソートを内部ソートと呼びます。

内部ソートの例として、バブルソートがあります。バブルソートは要素の交換を繰り返しながらソートを行います。必要となるデータ領域は、格納領域のほかには、交換の際の O(1) のみです。よって内部ソートに分類されます。

同じく内部ソートの例として、クイックソートが挙げられます。クイックソートは再帰的な呼び出しを用います。そのため O(log n) の外部領域を必要としますが、これは分類上、内部ソートとされます。

外部ソートは上記以外の例、すなわちソート対象のデータ格納領域以外に O(n) 以上の外部領域を必要とするソートアルゴリズムを指します。例えばマージソートが一例です。マージソートはマージの際に、最大 n/2 の外部領域を必要とします。つまり、O(n) の外部領域を必要とするため、外部ソートとなります。

計算量

ソート対象のデータ数 n を基準とした計算量でアルゴリズムを分類できます。要は n が増加したときに、どれだけ実行時間が増えるかの目安です。計算量は、最悪と平均をそれぞれ考慮する必要があります。

計算量が小さいほうが、基本的には性能のよいアルゴリズムとなります。これはソート以外のアルゴリズムでも当てはまるものです。主だった、計算量の大小関係は以下の通りです。

O(1) < O(log n) < O(n) < O(n log n) < O(n^1.5) < O(n²)

一般的にソートアルゴリズムでは、O(n log n) が高速で、O(n²) のアルゴリズムは低速とされます。あとは条件次第で使い分けます。

アルゴリズム一覧